Solution to Passing-Cars by codility

20 Jan

Question: http://codility.com/demo/take-sample-test/passing_cars

Question Name: PassingCars

52 Replies to “Solution to Passing-Cars by codility

  1. Hello Sheng, please I am trying to understand the reasoning behind this solution. I am still struggling to understand the prefix sum principle. If you don’t mind shedding light on this and how this was used to solve this problem, I would be grateful.
    Thanks

    • As far as I see, this blog is not a good place to discuss the idea of prefix sum principle. You would better to have an introduction book of algorithm to learn that. Or you could take an open course like Algorithms from Princeton University (https://class.coursera.org/algs4partI-004/).
      For the logic behind this solution, you could have a paper and pencil, and draw it as the solution did. Imaging that, all west-driving cars are NOT moving. And only all east-driving cars are moving. In most cases, you could get it.
      To be honest, you have to have a solid algorithm basis to do training by Codility. Anyway it is not a textbook for algorithms. Otherwise, it could help little.

  2. Since I like your solutions, I am posting mine here for anyone who might like to see a different solution.

  3. Hey Sheng / JG,
    My solution is almost identical to this, less the “if pairs > 1 billion” statement.
    Why is that statement necessary? I notice when I submitted my solution I had timeouts, but what specifically should have made me predict this before I submitted my code?

  4. Hello Sheng,
    My solution gets 100% correct but 20% performance, what can i do to improve this?
    Thanks for your help!

    • You should avoid using double “for” loop because it will lead worst time complexity of O(N^2) hence diminish the performance of the code severely. I recommend you to try think about how to reduce the loop, so that just one loop will do the job.
      Besides, I guess that checking A.Length will not work properly because we are not concerned about the length of the array (in fact, A.Length < 100,000) but the number of passing.

  5. C++ 11, 100%

    • Thanks a lot for your sharing.
      At the same, could you please pay some attention in the details like the input argument signature? In the original post, the parameter is:

      which is unworkable. I modified it.
      Enjoy coding!

      • #Hello Tejas, Your question is pretty genuine and It is a coincidence that I have been asking the same question to myself so below is my solution however, Codility gives me 30% here but as per my test cases below, I still feel my solution should be correct because A = [0,1] or A = [1,0] gives you 1 pair so it sould return 1 not 0 i believe. That is how we count the pairs actually:-

  6. The task itself was not very dificult, but the task description was a little bit cryptic to me. As a matter of fact, I think I couldn’t solve this task without the hint shown in this post.
    So I thought that it will be gratefully helpful that P and Q are more explicitly stated. That;
    P is an index of the array A which represent a car started to traveling to the east, and
    Q is an index of the array A which represent a car started to traveling to the west,
    so a pair of cars (0,1) means that a car A[0] started to the east and a car A[1] started to the west have been passing.
    Anyway, I submitted a survey to the Codility, and hope that they will continue to provide great lessons over and over.
    ps. Attached is the code I wrote. Is is basically same as others, but it’s in C.
    https://codility.com/demo/results/demoPJ2APK-GAN/
    UPDATE: The code I attached above is somewhat wrong. I am deeply sorry for your inconvenience. Please use next code instead.
    https://codility.com/demo/results/demo8UZ6J8-CGB/

    • Actually, if you find some description is not clear of misleading, you could contact Codility.com with email. They are very responsible and nice!

  7. Java 100% Correctness

      • No. The if-closure ends with a “return” statement. No matter it’s included within the loop or after, it will be executed at most once.
        In addition, we include the if-closure in the loop for an early termination, to improve the performance. Moving it after loop will make the performance worse.

  8. A slightly more pythonic solution, that does not call range():

    • Probably we should check the n_paires immediately after updating it. We could get some performance improvement.

  9. Ruby 100%

  10. C# 100%

  11. A solution using prefix sums which has only 80% at performance despite the fact that it is O(N) (as shown in the result page). Anyone knows what the reason might be?
    And also why it shows it’s O(N) and not O(2*N) ?

    • Bogdan,
      I did the same thing in python and got 100% and 100%. The only difference is a check for count > 1000000000 as count is incremented. I ran your code with this change and got 100% 100%!

  12. I found an interesting solution, 100% correct but only 40% performance. It starts from the maximum pair count (using combinations of N by 2), substracting not valid pairs in a O(N) step. However, the performance is only 40%. Any idea why ?

    • Overflow!
      N could be as large as 100,000. Therefore ((N – 1) * N) / 2 is 4999950000, which is larger than Int32.MaxValue in C#.

      • Yes, that’s why the count is a long var. And I cast it to int only if it is lower then 1,000,000,000 (the int max value is 2,147,483,647 so it should fit).
        The correctness test shows some wrong answers, not time exceeds, like
        “got -898714938 expected -1”.
        How can the code return big negative values? It looks like some overflows during the conversion.

      • Ah, yes, I found where is it the overflow: in C# if you make arithmetic operations over an int, the result would be also an int.
        So

        gets an overflow when N=100.000, no matter the function return type is a long.
        So, if we’re boxing the int into a long and perform the arithmetic operations over it, the solution is 100% on Performance test too.

  13. To those, who are having difficulty in understanding the logic, I will give a simple illustration on how the following logic comes. For this let us imagine this , whenever 0 comes , a monk is created and whenever 1 comes, a food is created. We can only count or to say our karma is good , when we serve the food to the monk .And the question is asking, how many times we have served the food to the monk. So, if there are two monks and one food, we need to serve the food to two monks and our karma is 2. Please look upon the illustration given in this image (https://drive.google.com/file/d/0B2GSXjlcPi0lckhCdmdZVXNuZkk/view?usp=sharing). So , by simply adding the times we served the food ( which is equivalent to the pair of car i.e 0,1), we will get total passing car. Please look upon the other illustration on how those counting is done ( https://drive.google.com/file/d/0B2GSXjlcPi0lT3otZ1N5ZXhoZlE/view?usp=sharing). I always have difficulty is understanding the problem and implementation, so I always imagine the problem in other way to properly find the solution.

  14. Javascript Solution 100%

  15. By calling range(len(A)-1, -1, -1), doesn’t this count as space complexity of O(N)? I know in Python 2.7 range() creates a list object.
    I am new to this algorithm stuff so I am honestly wondering what the answer is.

  16. my python solution 100%

  17. here it is in C 100%

  18. Here’s my VB solution which got 100%. However, I hate to burst everyone’s bubble, but the testing was inaccurate, because none of your solutions work correctly outside of their test cases. Try these arrays for example. [0,0,0,1,1,1,1] , [1,1,1,0,0,0,0]. Why do you get 12 for 1 and 0 for the other? Because it doesn’t work for leading 1’s in the array. I’m still trying to solve that even though it passed I’ve shown it has a major fallacy for leading 1’s.

    • First of all, I would say, to err is human. It’s totally possible that codility testing is defective. I found some and reported.

      However, back to your comment, I think you might misunderstood the problem. [0,0,0,1,1,1,1] should output 12, and [1,1,1,0,0,0,0] should result in 0. Let me do a translation 🙂
      [0,0,0,1,1,1,1]: -> -> -> <- <- <- <-, the number of pairs of passing cars is 12 [1,1,1,0,0,0,0]: <- <- <- -> -> -> ->, nobody will pass anyone else.

      Hope it helps!

  19. The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.
    In simple words,
    if we see car going to west mean that it can pair with
    all previously seen east cars. And also we need add previously
    passing_cars counter to get total count. (so prefix sum)

    so at point we see west going car in array,
    passing_cars[index] = passing_cars[index-1] + east_cars

  20. Posting just another solution here ;). Went the other way wasting some space complexity that was not necessary but yeah, that’s the only thing went through my mind at the time.

  21. Python solution – 100%. O(N)

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!