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

Question Name: PassingCars

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def solution(A): west = 0 # The number of west-driving cars so far passing = 0 # The number of passing for index in xrange(len(A)-1,-1,-1): # Travel the list from the end to the beginning if A[index] == 0: # A east-driving car passing += west if passing > 1000000000: return -1 else: # A west-driving car west += 1 return passing |

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

NOTmoving. 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.

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

Thanks for sharing your solution, especially for the detailed and great comments!

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?

Because the challenge requires: The function should return −1 if the number of passing cars exceeds 1,000,000,000.

Wow, I’m legitimately embarrassed that I missed that.

Thanks for your help

That is fine. And you are welcome!

Hello Sheng,

My solution gets 100% correct but 20% performance, what can i do to improve this?

Thanks for your help!

Please read my post. Your solution is right, but not efficient.

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.

Thanks for being a active contributor and helper 😉

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!

This solution doesn’t work for input starts with 1 at 0th index

i.e A ={1,0}; output should be 1.

For input [1, 0], the output should be 0.

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!

Java 100% Correctness

Thanks for sharing!

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.

Ruby 100%

C# 100%

Solution in C#, almost identical to the one above, but with some comments to explain my logic.

private static int solution(int[] A) // this solution scored 100%

{

int passingCars = 0;

int carsGoingEast = 0;

for (int i = 0; i it will pass by all the cars that have been determined to be going east

passingCars += carsGoingEast;

if (passingCars > 1000000000) return -1;

}

}

return passingCars;

}

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) ?

Please read my post before asking any question. The answer is there. Thanks!

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%!

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.

like this:

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.

Thanks for your support and explanation!

Javascript Solution 100%

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.

You are absolutely right. The space complexity is O(N). We could simply improve it by using xrange.