9
\$\begingroup\$

My problem is quite similar to the question found here, except I am attempting to answer the question in Python.

Given an array of N counters, all initialized to 0, and an array A representing a series of operations, find the final state of the counters. Each entry in A should be interpreted as follows:

  • If 1 ≤ A[k]N, then increase the counter at A[k] by 1.
  • If A[k] = N + 1, then set all counters to current maximum value.
def solution(N, A):
    # write your code in Python 2.7
    counters = [0] * N
    max_count = 0
    for x in A:
        if 1 <= x and x <= N:
            counters[x-1] += 1
            if counters[x-1] > max_count:
                max_count += 1
        else:
            counters = [max_count] * N
    return counters

Nothing I can come up with allows me to do this in \$O(N + M)\$ time. I get rid of any max() functions going through the list by keeping track of it, but for the life of me I don't know how one is supposed to update N different variables M times (worst case scenario) without it being \$O(N * M)\$.

I am asking this question because I am uncertain what this question even asks is possible without having N processors to bring the \$O(N)\$ by itself stage of updating the counter array down to \$O(1)\$ through parallelization. Since the other question hasn't been answered, I guess what I want to know is if there is a data structure or some other heuristic that will get this down to \$O(M + N)\$.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ The code basically uses a dictionary object to keep a running histogram between occurrences of an entry of N+1, then updating counter only when the max_counter operation is applied. After the last max_counter operation, it just uses the naive approach. Quite ingenious, actually. \$\endgroup\$ Nov 18, 2014 at 3:18
  • 1
    \$\begingroup\$ Duplicate? How about fizzbuzz? ;) \$\endgroup\$ Nov 18, 2014 at 3:37
  • 1
    \$\begingroup\$ @ optical_anathema: yes, the dictionary idea is what I hinted at as M * log(M) and it was my first approximation; then I realised that a small constant amount of extra work per increment would work as well: counters[x-1] = max(counters[x-1], last_max_count) + 1 which gets rid of the log(M) of the dictionary search. That's the same as bainikolaus' code on that page, and I don't think it can be improved in any way except for renaming m and minValue. \$\endgroup\$
    – DarthGizka
    Nov 18, 2014 at 3:51
  • 1
    \$\begingroup\$ Which solution is faster depends on the sizes involved: small M compared to biiig N, or the other way around. I bet that Codility have at least one biiig N case for flushing out naive algorithms, and this slightly favours the map (dictionary) approach. In languages like C/C++ the max() operation is virtually free (CMOV), and the last_max_count method is much leaner overall, meaning the map<> method is not competitive in C++. That's also one reason why it is hard to think fruitfully about optimisation without having some hard facts and good bounds on the sizes involved. \$\endgroup\$
    – DarthGizka
    Nov 18, 2014 at 4:03
  • 1
    \$\begingroup\$ P.S.: perhaps the difference becomes clearer if I point out that the counter array already is one big bleeding frequency counter. Using a map/dictionary on the sequences between 'max_count fillings' only introduces an additional log(M) cost for the search. For gigantic input sizes the map/dictionary would again win because of locality of access compared to a huge, sparse counter array that is too big for any of the CPU caches. \$\endgroup\$
    – DarthGizka
    Nov 18, 2014 at 4:17

1 Answer 1

9
\$\begingroup\$

What hurts your performance is filling the array with max_count. So don't do it. Imply it. The trick is all there, and it makes this slightly different from trying to execute a literal transcription of the problem.

Spelling out the details would rob pundits of the enjoyment of puzzling...

I don't know about Codility, but elsewhere the tasks can often be solved with efficient coding of a naive algorithm (especially in C/C++) instead of solving the puzzle algorithmically. Sometimes I try the 'raw firepower' solution as well, if it promises an interesting challenge. But only after finding the real solution, since each puzzle is basically about finding a specific trick that goes beyond the naive algorithm.

Given that people do these challenges for the puzzle value I think it would defeat their purpose if we posted complete solutions.

P.S.: the sketched solution reduces runtime only to M * log(M) + N or M * C + N but that should be sufficient (and enough of a hint).

\$\endgroup\$
1
  • \$\begingroup\$ I can't upvote (not enough reputation:), but you got it. Thank you for your input. \$\endgroup\$ Nov 18, 2014 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.