MaxCounters codility understanding

Question

I have wanted to try some challenges on Codility and started from beginning. All assignments were relatively easy up to the one called MaxCounters. I do not believe that this one is especially hard although it is the first one marked as not painless.

I have read the task and started coding in C# language:

public static int[] maxPart(int N, int[] A){
    int[] counters = new int[N];
    for(int i = 0; i < A.Length; i++){
        for(int j = 0; j < counters.Length; j++){
            if(A[i] == counters[j] && (counters[j] >= 1 && counters[j] <= N )){
                counters [j] = counters [j] + 1;
            }
            if(A[i] == N + 1 ){
                int tmpMax = counters.Max ();
                for(int h = 0; h < counters.Length; h++){
                    counters [h] = tmpMax;
                }
            }
        }
    }
    return counters;
}

Having 3 loops of course makes it really slow, but lets leave it for later. My concern is how I understood this like this and all the other people see it like on this question here.

From the assignment's description.

it has 2 actions:

• increase(X) − counter X is increased by 1,
• max counter − all counters are set to the maximum value of any counter.

which occur under conditions:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

Both conditions are stated in the code above. Obviusly it is wrong but I am confused, and I do not know how could I understand it differently.

Why is this code wrong, what am I missing from task description?

One of the top rated answers looks like this:

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;
    int resetLimit = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            if (result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            } else {
                result[A[K] - 1]++;
            }

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            //for (int i = 0; i < result.Length; i++)
            //    result[i] = maximum;
            resetLimit = maximum;
        }
    }

    for (int i = 0; i < result.Length; i++)
        result[i] = Math.max(resetLimit, result[i]);

    return result;
}

This code results with 100% on Codility.

Question:

I would like to know how the author knew from the task to use result[A[K] - 1]? What would resetLimit represent?

Maybe I completely misunderstood the question due to my English I am not sure. I just can not go over it.

EDIT:

Based on my code provided, how did I misunderstood the assignment? Generally I am asking for explanation of the problem. Whether to explain what needs to be done, or take the code as correct result and provide and explanation why is this done this way?

Answer 1

In my opinion you somehow mixed the index of the counter (values in A) and the value of the counter (values in counter). So there is no magic in using A[i]-1 - it is the value X from the problem description (adjusted to 0-based index).

My naive approach would be, the way I understood the problem (I hope it makes clear, what your code is doing wrong):

public static int[] maxPart(int N, int[] A){
    int[] counters = new int[N];
    for(int i = 0; i < A.Length; i++){
        int X=A[i];
        if(X>=1 && X<=N){ // this encodes increment(X), with X=A[i] 
             counters [X-1] = counters [X-1] + 1; //-1, because our index is 0-based  
         }
         if(X == N + 1 ){// this encodes setting all counters to the max value
             int tmpMax = counters.Max ();
             for(int h = 0; h < counters.Length; h++){
                    counters [h] = tmpMax;
                }
            }
        }
    }
    return counters;
}

Clearly, this would be too slow as the complexity isO(n^2) with n=10^5 number of operations (length of the array A), in the case of the following operation sequence:

max counter, max counter, max counter, ....

The top rated solution solves the problem in a lazy manner and does not update all values explicitly every time a max counter operation is encountered, but just remembers which minimal value all counters must have after this operation in resetLimit. Thus, every time he must increment a counter, he looks up whether its value must be updated due to former max counter operations and makes up for all max counter operation he didn't execute on this counter

if(result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            }

His solution runs in O(n) and is fast enough.