Solution to Max-Counters by codility

19 Jan

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.

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

50 Replies to “Solution to Max-Counters by codility

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

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

  2. 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!

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

  3. Can you tell me why this solution failed the performance test? Thanks in advance!
    (https://codility.com/demo/results/demoV6MRWN-MY5/)

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

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

  6. 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!

  7. Ruby 100%

  8. 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!

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

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

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

  11. C++ solution:

  12. This is my Python solution:

    Fails performance test for large data sets… Any idea ?

  13. There doesn’t seem to be a 100% python solution posted. Both of Sheng’s solutions fail the performance test, when they are submitted to Codility. I managed to get 100% solution by not overwriting the list every time the N+1 max value command is issued. Instead two numbers are remembered the current max value and the previous max value, at the time of the last N+1 max value assignment command. This avoids the O(N) list creation time. Each array value is updated after all the commands from list A are run.

    • Thanks for your comment! However, I do not know how did you get the conclusion “Both of Shengโ€™s solutions fail the performance test”.

      For the first solution, I explicitly said, it’s bad in the worst-case. For the second one, I tried again on Codility and it still passes the Codility test.

      Finally, please read the “Guideline for Comments” for posting code. I cannot see your complete solution. With your incomplete post, I did not see much difference between your solution and mine.

  14. this seems to work 100%.
    https://codility.com/demo/results/trainingQ8JXGP-4K3/

  15. How about this

  16. this is my solution, similar with yours i think, but with a little tweak, how ever i got only 80 in performance, not sure why, can not find any other boost.

    • Please read the article fully. The key point of the solution is “lazy-write”. “space = i == N+1 and [maxCounter]*N or space” will lead to 80% in performance testing. Thanks!

  17. Here is my Java solution, 100%

  18. Thank you! Before I found your solution, I submitted 2 Java solutions to this problem and I managed to get 77% and 66% overall on this problem due to failures in the performance tests. Finally, after reading your Python solution I realized that I had an inefficiency in the else statement (line 15-18 in your code) – I didn’t need to set all the variables in the array to that value every time, just keep track of the variable. My third solution finally got 100% success. Here it is:

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!