Solution to Frog-River-One by codility

19 Jan


Question Name: FrogRiverOne

If coding with C, bitmap is preferred to store which positions are covered.

57 Replies to “Solution to Frog-River-One by codility

  1. 100 / 100 FrogRiver PHP

    • First of all, thanks for sharing your solution!

      Secondly, if you want to post code in the comment, please place the code inside a <pre> … </pre> block.

      Finally, you could move your second if block into the first one to get a little improvement.

      PS: when you consider to submit your code, it will be better if the solution is using a different method or algorithm. Difference on programming language does not mean much to the readers.

  2. Here is my solution. Got 100/100:

    • Sorry, when I tried it on Codility. Some error happened:
      Solution.cs(10,21): error CS1061: Type int[]' does not contain a definition for Distinct’ and no extension method Distinct' of type int[]’ could be found. Are you missing `System.Linq’ using directive?

      Could you please help me to fix it?

  3. Here is my Java solution:

  4. Thank you Sheng for solutions. Your website is very helpful. I am new in Python, so using your tutorials…
    Just want to share my first attempt to resolve this task with “if element not in covered_a” which had fail of performance and second one which stole from you to improve it.

  5. lean and mean:

  6. JavaScript version

    • Thanks for Sharing,

      I am learning software development, and I am a little confuse with
      count[index] = true;

      I understand that with this code you prevent that some element is repeat it in the array, but how does it work?

  7. PHP – 100% / 100%

  8. UPDATE by victor zhong on February 19, 2015 at 7:58 am:
    why my code lost indent…..

  9. Sets again:

    • It works. While from my point, there are some suggestions about this solution.

      On one hand, set is kind of too much for such a small question, especially consider the array is perfectly fit in such case.

      On the other hand, after the for loop, we’d better to have a “return -1” statement and/or a comment “Not reachable.”

      • I understand the concerns. However, this is a set problem in disguise and I presume that implementation yields the fastest computing time.

        Also, the “return -1” statement after the loop will never be reached. The only case that could return -1 is if set(A) does not contain all the leaves, which is being taken care of at the start.

        • These two solution should not have any noticeable difference in computing time, in practice.

          The “return -1” statement is my personal preference on coding style. Your code is neither bug nor bad 🙂

          Finally, thanks for being an active contributor.

  10. Hi Sheng, I apologize if the question is not very productive. But I’m a Python learner and I don’t get the part where you assign the value -1, X times to the “covered_time” list and then you test “if covered_time[A[index]-1] != -1”.
    Would python return an out of range error when the element you get from A[index] translates to a position greater than X (the size of the list)?

  11. Ruby 100%

  12. Here’s my C++ solution, got 100%:

    • There are some test cases where this program terminates:

      Your test case: [0, [0]]
      Output (stderr):
      Segmentation Fault
      RUNTIME ERROR (tested program terminated unexpectedly)

      Your test case: [0, [0, 5, 1, 4, 2, 3]]
      Output (stderr):
      Segmentation Fault
      RUNTIME ERROR (tested program terminated unexpectedly)

      Detected some errors.

  13. EDIT by Admin: Java solution.

  14. C# 100%

  15. Sorry but I think this case is not covered by this code.

    • There is an assumption in the problem: each element of array A is an integer within the range [1..X]. But your test case breaks it.

  16. Hi Sheng,

    You mentioned bitmap in C. I just want to make a comment here: variable length array is only allowed in C99… BTW, you can’t use C++ STL bitset either, since it also requires a const size_t to initialize the length.

    My 2cents!

    • Well. in the most “native” C, I would use an int pointer, allocate the memory when need, and manipulate it mannually as bitmap.

  17. Javascript

  18. JS solution 100%

  19. Solution using Java HashSet

  20. FrogRiverOne: Python (simple and sleek)

  21. Here my solution in Java. It works 100% but the time complexity is O(N) or O(N * log(N))

  22. The solution of mohammad is really good and elegant. 50% shorter than the last solution in java for example. Is it python2? if you use enumerate() you can access the index of the for and don’t have to calculate the max(pos.values())

    something like:

  23. My C++ solution.

  24. Another Java solution:

    • I recommend adding one more condition, which causes no error for numbers in table A greater than X.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!