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

Question Name: MaxCounters

A straightforward solution is easy as following. But the expected worst-case time complexity cannot be guaranteed.

1 2 3 4 5 6 7 8 9 10 |
def solution(N, A): result = [0]*N for command in A: if 1 <= command <= N: result[command-1] += 1 else: result[:] = [max(result)]*N return result |

We could use lazy-write to improve the performance. When receiving the max_counter command, we record the current-max value, but do not change the list content. Only when we are going to return the list or increace a specific element, we will apply the stored value to the corresponding element(s).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
def solution(N, A): result = [0]*N # The list to be returned max_counter = 0 # The used value in previous max_counter command current_max = 0 # The current maximum value of any counter for command in A: if 1 <= command <= N: # increase(X) command if max_counter > result[command-1]: # lazy write result[command-1] = max_counter result[command-1] += 1 if current_max < result[command-1]: current_max = result[command-1] else: # max_counter command # just record the current maximum value for later write max_counter = current_max for index in range(0,N): if result[index] < max_counter: # This element has never been used/updated after previous # max_counter command result[index] = max_counter return result |

java, 100%

First of all, thanks for sharing your solution. If some comments are there to help the readers, it would be much better.

Your solution could pass all the test. But as far as I see, it does not have time complexity O(N+M), even though the Codilty system said so. The time complexity should be O(N*M), as new int[N] uses O(N).

Essentially, your solution is an optimized version of my first solution. Actually it could be optimized further, as shown in https://codility.com/demo/results/demoDEYNRS-38A/ . This optimized Python solution uses less time in all test. ( Even though it is quicker, it failed in one test because of TIMEOUT ERROR. I do not know why, and I am trying to contact Codility.)

I guess the problem in this solution is this line: result = [maxVal]*N. This basically makes the solution a O(M*N), doesn’t it (a new array of N elements might be created in each loop iteration if the commands all increase the counter, maybe this is the reason of the failure)? Strange that codility accepts it as an O(M+N). Maybe array/list instantiation in python is somehow optimized so that it is faster than iterating over an old list and setting element?

Yes, I agree with you. It is O(M*N). Codility estimate the complexity. And no estimation in the world is perfectly accurate.

Just get the confirmation from Codility team. Your solution is not O(N+M). It passed the tests by chance, because:

“Java has a substantial overhead to start the virtual machine. We use a bit more liberal timeouts for programs in Java” – From Codility Team

Hmmm.. Could you explain why your solution is O(N+M) then and mine is not?

For my solution, inside the two for loops, there are only either comparison (if) or single cell assignment. So the two for loops are O(M) and O(N) respectively. Totally, it’s O(N+M).

For your solution, in the first loop, there is a statement as “counters = new int[N];”, which is O(N). And the loop funs for M times. So it’s time complexity is O(N+M+N*number_of_max_counter_operations). In worst case, it’s O(N*M).

Thank you for making it clear for me, as I have some issues with estimating time complexity:)

Though I am a bit confused, about assigning “new int[N]”, as I thought it does not iterate through all elements to allocate memory for each of them and assign separately:) I assumed that memory is allocated for the whole array. Please, check that.

Sorry for my code, though judging by it, I would like to point out on one thing. Lets assume that we have a worst case scenario and all operations are max_counter, then operation “counters = new int[N];” will be performed only once, for the last element. That makes time complexity, according to your formula (which I did not know, really thank you for that), it will be O(N+M+N*1) => O(N+M);

The real worst case scenario is when each update operation is followed by max_counter. In that case time complexity will be O(N+M+N*N/2), according to your formula again. That makes complexity O(N^2), not O(N*M). Although I do not think that it requires O(N) to allocate memory for an array, I might be wrong.

I am not trying to prove that my solution is 100% perfect and works everywhere, I was just a bit confused by your judgement based on Codlity reply and your assumptions that it passes all tests by chance.

Yeah, you are right, it is O(N) for declaring array with N length. Thank you.

That means in the worst case scenario my solution will be performed at O(N^2).

Yeah! Discussion is greatly helpful to all of us! To err is human.

Enjoy Coding! And welcome to discussion on any solution here!!!

PS: please add a few description words with your code next time. So that we could know what’s happening~ Thanks!

Yes, thank you for the blog and solutions.

I am still learning stuff, and this blog is very helpful.

Yes, my mistake, I understand, should have added comments, as I forgot myself what is going on in my code:)

Comment does matter. It helps a lot when you are communicating with others. And it will help you a lot when you come back to read your own code after days.

In addition to comments, a few sentences, about why you are posting your code here, are really appreciated.

You are more than welcome! Enjoy coding!

I did not really bother about Donald Knuth’s statement “Premature optimization is the root of all evil” until I tried out codility. I managed to get it 100% correct and 60% perf. on the first try, but getting it to 100% perf. meant breaking the correctness.

C++, 100%

https://codility.com/demo/results/demoPHDVVG-UFJ/

Btw, this is a great website.

Your solution is great! It provides us another idea to solve this challenge: replay the increase(X) values following the last maxCounter(). Thanks!!!

FYI: you forgot to comment out one cout at line 10.

PS: Thanks for visiting my blog! So happy to see it be helpful to others!

Can you tell me why this solution failed the performance test? Thanks in advance!

(https://codility.com/demo/results/demoV6MRWN-MY5/)

Please refer to my post. It explains everything about the right solution.

PHP – O(N + M) – 100% / 80%

https://codility.com/demo/results/demoKC2FYJ-JWD/

Can’t get more performance with that way

So I started to do it in the way that I am finding last max counter and then increase particular fields

But I got some Correctness problems

~~https://codility.com/c/run/demo7UZSUV-T8N~~Admin: your second solution is here: https://codility.com/demo/results/demo7UZSUV-T8N/

I cannot open the second URL. And in most cases, I cannot help you to debug.

For your first solution, the performance issue is the line #10. Please use lazy write as shown in my post.

I found and read your second solution. I cannot understand it fully. But it definitely has some bugs. After you got a max_counter instruction, you may increase the value $result[$inc-1]++ without updating it to max_counter.

Please ask question only after you read all the blog post and all the comments.

C++ 100% solution.

At the start a have a for loop to consolidate all numbers greater than N into one number. So if N = 5 and the vector like this { 7,8,9,1,2,3,4,7,7,8,9,5,6} this will be reduced to {1,2,3,4,7,5,6}. The reason I did the reduced vector was because I was maxing the counter in the forloop that incremented each counter!

Admin: in the original post, Simon used a different function signature. I modified it so that, every reader could use it directly in Codility.com.I solved this in the C programming language. When I faced this test at the first time, what frustrated me was the structure declaration of the result, that is;

I could easily notice that C is a pointer to a dynamic array (the counter), but L was not so clear. However, after a few trial and errors, I guessed that L is the length of the array. I’m not one hundred percent sure about this, but anyway I managed to get 100/100 score with the complexity of O(N + M). I think it would be better if Codility was a little more friendly, but we know that we can not blame them.

The code I posted is somewhat broken. Here I will add the URL what I did;

https://codility.com/demo/results/demoKZGHHC-KEP/

Yes, it is unclear in the question statement. I encourage you to contact them to fix it. The staff in codility.com is nice and helpful. 🙂

I e-mailed the staff in codility.com as suggested, and confirmed that C stands for the counter and L for the length. I also heard that they have a roadmap to fix this and make it more clear.

Thanks again for your recommendation!

You got it! I had some similar issue and emailed them. Therefore I know it is nice communicating with codility.com 🙂

Enjoy coding!

Ruby 100%

I slight variation on your solution using list comprehension. Took me a while to work out that I couldn’t use max() in the first loop to get the max_val without sacrificing performance. Still so much to learn!

Your solution is pretty Pythonic!

Hi there,

I am still a little bit puzzled:

The task is :

” … if A[K] = N + 1 then operation K is max counter…”

Why do you write

and not:

Thanks in advance!

Because the problem says: “each element of array A is an integer within the range [1..N + 1].” If the condition “1 <= command <= N" failed, the command MUST be N + 1.

JavaScript, 100%… I’m so sorry, I don’t know that use to crayon highlight syntax.

Totally fine! You were very close to the right formation. You began the code with a pre tag, but ended it with a “code” tag, which is wrong. You should use pre tag at both the beginning and the end. Or code tag in both places. Please read the “Guideline for Comments” on the right column of the blog for more information.

Thanks for sharing!!!

This is another Java solution with some comments as suggested earlier:

C++ solution:

This is my Python solution:

Fails performance test for large data sets… Any idea ?

Please read the post before asking questions 🙂

Wow, your python solution is brilliant!

Hey!

I tried a solution similar to your first one, tried to improve performance using a frequency map instead. Somehow it fails even the correctness tests. This was a first attempt so I don’t bother about performance that much. Can you help me see where is the failure in this?

https://codility.com/demo/results/training739NPC-XNZ/

I did not see any reason to use FreqTable.