What is a better method to solve this prob?

Question

Here is the problem i am trying to solve,

You are given a table with 2 rows and N columns. Each cell has an integer in it. The score of such a table is denfined as follows: for each column, consider the sum of the two numbers in the column; the maximum of the N numbers so obtained is the score. For example, for the table

7 1 6 2
1 2 3 4

the score is max(7 + 1; 1 + 2; 6 + 3; 2 + 4) = 9. The first row of the table is fixed, and given as input. N possible ways to ll the second row are considered:

1; 2; : : : ; N
2; 3; : : : ; N; 1
3; 4; : : : ; N; 1; 2
|
N; 1; : : : ; ; N 1

For instance, for the example above, we would consider each of the following as possibilities for the second row.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Your task is to find the score for each of the above choices of the second row. In the example above, you would evaluate the following four tables,

7 1 6 2
1 2 3 4
7 1 6 2
2 3 4 1
7 1 6 2
3 4 1 2
7 1 6 2
4 1 2 3
and compute scores 9, 10, 10 and 11, respectively

Test data: N <= 200000
Time Limit: 2 seconds

Here is the obvious method:

Maintain two arrays A,B, Do the following n times

• add every element A[i] to B[i] and keep a variable max which stores the maximum value so far.
• print max
• loop through array B[i] and increment all the elements by 1, if any element is equal to N, set it equal to 1.

This method will have take O(n^2) time, the outer loop runs N times and there are two inner loops which run for N times each.

To reduce the time taken, we can find the maximum element M in the first row(in a linear scan), and then remove A[i] and B[i] whenever A[i] + N <= M + 1.
Because they will never be max.

But this method might perform better in the average case, the worst case time will still be O(N^2).

To find max in constant time i also considered using a heap, each element of the heap has two attributes, their original value and the value to be added. But still it will require a linear time to increment the value-to-be-added for all the elements of the heap for each of the n cases.
And so the time still remains O(N^2)

I am not able to find a method that will solve this problem faster than N^2 time which will be too slow as the value of N can be very large.
Any help would be greatly appreciated.

Answer 1

There is also an O(n) algorithm. Using the same observations as in a previous answer:

Now consider what happens to the column sums when you rotate the second row to the left (e.g. change it from 1,2,...,N to 2,3,...,N,1): Each column sum will increase by 1, except for one column sum which is decreased by N-1.

Instead of modifying all the column sums, we can decrease the one column sum by N, and then take the maximum column sum plus 1 to find the new maximum of the column sums. So we only need to update one column instead of all of them.

The column where the maximum appears can only move to the left or jump back to the column with the overall maximum as we iterate over the possibilities of the second row. Candidate columns are the ones that were the temporary maximum in a left to right maximum scan.

1. calculate all the sums for the first choice of the second row (1, 2, ..., N) and store them in an array.
2. find the maximum in this array in a left to right scan and remember the positions of temporary maxima.
3. in a right to left pass the sums are now decreased by N. If this decreasing process reaches the max column, check if the number is smaller than the overall maximum - N, in this case the new max column is the overall maximum column and it will stay there for the rest of the loop. If the number is still larger than the previous maximum determined in step 2, the max column will stay the same for the rest of the loop. Otherwise, the previous maximum becomes the new max column.

Taking the example input 7,1,6,2 the algorithm runs as follows: Step 1 calculates the sum 8,3,9,6 Step 2 finds the temporary maxima from left to right: 8 in col 1 and then 9 in col 3 Step 3 generates the results passing over the array from right to left

8 3 9 6 -> output 9 + 0 = 9
8 3 9 2 -> output 9 + 1 = 10
8 3 5 2 -> current max col is decreased, previous max 8 is larger and becomes current
           output 8 + 2 = 10
8 -1 5 2 -> output 8 + 3 = 11

Here is the algorithm in C:

#include <stdio.h>

int N;
int A[200000];
int M[200000];

int main(){
    int i,m,max,j,mval,mmax;

    scanf("%d",&N);

    for(i = 0;i < N; i++){
        scanf("%d",&A[i]);
        A[i] = A[i]+i+1;
    }

    m = 0;
    max = 0;
    M[0] = 0;

    for(i = 1;i < N; i++){
        if(A[i] > A[max]){
            m++;
            M[m] = i;
            max = i;
        }
    }

    mval = A[max] - N;
    mmax = max;

    for(i = N-1,j = 0;i >=0;i --,j++){
        printf("%d ", A[max]+j);

        A[i] = A[i] - N;

        if(i == max){
            if (A[i] < mval) {
                max = mmax;
            } else if(m > 0 && A[i] < A[M[m-1]]){
                max = M[m-1];
                m--;
            }
        }
    }

    printf("\n");

    return 0;
}