Massive Algorithms: Solution to Max-Counters by codility

Solution to Max-Counters by codility | Code Says

Lesson 2 - Counting Elements:

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

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,

max counter − all counters are set to the maximum value of any counter.

A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

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.

For example, given integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4

the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

http://www.martinkysel.com/codility-maxcounters-solution/

The idea is to perform the specified operation as stated. It is not required to iterate over the whole array if a new value is set for all the values. Just save the value and check it when an increase on that position is performed.

vector<int> solution(int N, vector<int> &A) {

    vector<int> sol;

    int current_max = 0;

    int last_increase = 0;

    for(int i=0; i<N;i++){

        sol.push_back(0);

    }

    for(unsigned int i=0; i<A.size();i++){

        if (A[i] > N) {

            last_increase = current_max;

        } else {

            sol[A[i]-1] = max(sol[A[i]-1], last_increase);

            sol[A[i]-1]++;

            current_max = max(current_max, sol[A[i]-1]);

        }

    }

    for(int i=0; i<N;i++){

        sol[i] = max(sol[i], last_increase);

    }

    return sol;

}

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

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

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

http://codility-lessons.blogspot.com/2014/07/lesson-2maxcounters.html
http://jimii.github.io/blog/2014/09/19/codility-counting-elements-maxcounters/
Read full article from Solution to Max-Counters by codility | Code Says

Solution to Max-Counters by codility | Code Says

Labels

Popular Posts