Lesson 2: MaxCounters (Max Counters)

This is an interesting question in that a straight-forward answer won't get 100% because of performance efficiency.

For instance, the simple implementation as below will get only the score of 77%

 


--------------------------------------------
A Simple Solution
--------------------------------------------
struct Results solution(int N, int A[], int M) 

{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;

    int max = 0;
    
    int i, j;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            for (j = 0; j < N; j++){
                result.C[j] = max;
            }
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            result.C[op]++;
            if (result.C[op] > max){
                max = result.C[op];
            }
        }
    }

    return result;
}


The problem in performance efficiency seems caused by the inefficient implementation regarding the 'max counter' operation,
as the above implementation always go through the whole array to update the values when a 'max counter' operation is given.


Let's use flags so to remember if the slot has not been applied any 'increase' operation since the last 'max counter' operation, to avoid updating the whole array every time a 'max counter' operation is issued.

In the below implementation, we simply clear the flag array and remember the current max value.

The code also checks if the slot is updated since the last 'max counter' operation when an 'increase' operation is issued to the slot. If it is updated, the code simply increment the value in the slot. If not, the code updated the slot with 'maxAtTheLastMaxCntOp'.

The score is increased to 88%. So we still need more optimization.

--------------------------------------------
A Better Solution (1)
--------------------------------------------

struct Results solution(int N, int A[], int M) 

{

    struct Results result;

    result.C = calloc(sizeof(int), N);

    result.L = N;

    int* flg = alloca(sizeof(int) * N);

    memset(flg, 0x00, sizeof(int) * N);

    

    int max = 0;

    int maxAtTheLastMaxCntOp = 0;

    

    int i;

    for (i = 0; i < M; i++){

        int op = A[i];

        //if the op is max counter.

        if (op == N + 1){

            maxAtTheLastMaxCntOp = max;

            memset(flg, 0x00, sizeof(int) * N);    

        }

        //if the op is increase(x)

        else {

            //op is beweetn 1 to N, but the index for the array C 

            //is between 0 and (N-1). Decrease op to adjust it.

            op--; 

            if (flg[op] == 1){

                result.C[op]++;

            }

            else {

                result.C[op] = maxAtTheLastMaxCntOp + 1;

                flg[op] = 1;                

            }

            

            if (result.C[op] > max){

                max = result.C[op];

            }

        }

    }

    

    //apply the 'max counter' operation

    //to the slot(s) where it should be applied. 

    int j;  

    for (j = 0; j < N; j++){

        if (flg[j] == 0){

            result.C[j] = maxAtTheLastMaxCntOp;

        }

    }

    return result;

}

So the flag strategy didn't work much for better performance efficiency. What can we do now? One may notice that it is enough to check if the current value of the slot before applying an 'increase' operation is alwa below the 'maxAtTheLastMaxCntOp' value,

since if any 'increase' operation is applied to the slot already, the value in the slot should be at least equal to the 'maxAtTheLastMaxCntOp' value.

In the below implementation, finally we get the score of 100%.

--------------------------------------------
A Better Solution (2)
--------------------------------------------
struct Results solution(int N, int A[], int M) 
{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;
    
    int max = 0;
    int maxAtTheLastMaxCntOp = 0;
    
    int i;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            maxAtTheLastMaxCntOp = max;
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            if (result.C[op] < maxAtTheLastMaxCntOp){
                result.C[op] = maxAtTheLastMaxCntOp + 1;
            }
            else {
                result.C[op]++;
            }     
            //update the max value if necessary.
            if (max < result.C[op]){
                max = result.C[op];
            }
        }
    }
    
    //apply the 'max counter' operation
    //to the slot(s) where it should be applied. 
    int j;  
    for (j = 0; j < N; j++){
        if (result.C[j] < maxAtTheLastMaxCntOp){
            result.C[j] = maxAtTheLastMaxCntOp;
        }
    }
    return result;
}