Problem

A game for one player is played on a board consisting of N consecutive squares, numbered from 0 to N - 1. There is a number written on each square. A non-empty array A of N integers contains the numbers written on the squares. Moreover, some squares can be marked during the game. 

At the beginning of the game, there is a pebble on square number 0 and this is the only square on the board which is marked. The goal of the game is to move the pebble to square number N - 1.

During each turn we throw a six-sided die, with numbers from 1 to 6 on its faces, and consider the number K, which shows on the upper face after the die comes to rest. Then we move the pebble standing on square number I to square number I + K, providing that square number I + K exists. If square number I + K does not exist, we throw the die again until we obtain a valid move. Finally, we mark square number I + K. 

After the game finishes (when the pebble is standing on square number N - 1), we calculate the result. The result of the game is the sum of the numbers written on all marked squares.

For example, given the following array: 

    A[0] = 1

    A[1] = -2

    A[2] = 0

    A[3] = 9

    A[4] = -1

    A[5] = -2

one possible game could be as follows:

·         the pebble is on square number 0, which is marked;

·         we throw 3; the pebble moves from square number 0 to square number 3; we mark square number 3;

·         we throw 5; the pebble does not move, since there is no square number 8 on the board;

·          we throw 2; the pebble moves to square number 5; we mark this square and the game ends. 

The marked squares are 0, 3 and 5, so the result of the game is 1 + 9 + (−2) = 8. This is the maximal possible result that can be achieved on this board.

Write a function: 

    function solution(A);

that, given a non-empty array A of N integers, returns the maximal result that can be achieved on the board represented by array A. 

For example, given the array

    A[0] = 1

    A[1] = -2

    A[2] = 0

    A[3] = 9

    A[4] = -1

    A[5] = -2 

the function should return 8, as explained above.

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [2..100,000];

·         each element of array A is an integer within the range [−10,000..10,000]. 

Note

The marking of a square is different from the number that is already there. Consider a mark as a tick, made by the player. The numbers that are already on the squares are the numbers in the array. The squares are indexed from 0 to N-1 and the array is also indexed from 0 to N-1. Do not confuse between the indexes and the numbers that are already on the squares.

One of the assumptions in the problem description is:

·         N is an integer within the range [2..100,000]; 

This means that the smallest value for N is 2 for index 0 and index 1.

The given example can be understood as follows: 

For example, given the following array:

    A[0] = 1

    A[1] = -2

    A[2] = 0

    A[3] = 9

    A[4] = -1

    A[5] = -2 

one possible game could be as follows:

·         the pebble is on square number 0, which has the number 1, and is then marked;

·         we throw 3; the pebble moves from square number 0 to square number 3, which has the number 9; we then mark square number 3;

·         we throw 5; the pebble does not move, since there is no square number 8 (of 3+5) on the board;

·         we throw 2; the pebble moves to square number 5, which has the number -2; we then mark this square, and the game ends.

The squares are zero based index (numbered). The marked squares are 0, 3 and 5 for this particular game; so the result of the game is 1 + 9 + (−2) = 8. This happens to be the maximal possible result (sum) that can be achieved on this board. 

If the values for K were 1, 1, 2, 2 then the sum would have been 1 + -2 + 9 + (-2) = 6, which is less than 8.

The maximum value for K is 6. 

The different values for K are 1, 2, 3, 4, 5, 6 for similar but smaller problems, in this dynamic programming.

Only particular numbers are on particular squares for different games of the same set of the given array A. For example, with the given data above, 9 cannot be on square number 3 and then 1 be on square number 3 for a different game, with the same set for array A.

Illustration

The given example is used for illustration of the dynamic programming algorithm. Imagine the board as follows:

 Having the number of squares to be 6 and the number of faces of the die to be 6, should be considered as coincidence. The dynamic programming table (2D) is as follows:

 The two-dimensional array is first created with all cells initialized to 0. Remember that the first square of the game always has A[0]. The 2D array is called dp, for Dynamic Programming. So, dp[0][1] is always A[0], for any given array.

Different games for the same given array occurs, column by column (in the table). In column 1, if the first throw is 1, then the pebble is placed in square number 1. The running sum is 1 + -2 = -1. This sum is recorded in dp[1][1]. There are two options for square number 2, still for column 1. If from square number 0, a two was thrown, then 0 from array A, would be recorded on cell number 2 (column 1). The running sum would be 1 + 0 = 1. Square number 2 could also be arrived at, from square number 1, with a throw of one. In that case, the running sum would be -1 + 0 = -1. The greater of these two numbers, 1 or -1, has to be chosen to be recorded in cell dp[2][1], in the table. 1 is chosen. 

Square number 3 can be arrived at in three different ways. From square number 2, if a throw of 1 is made, then the running sum would be 1 + 9 from array A. The 1 is from dp[2][1]. That running sum is 10. From square number 1, if a throw of 2 is made, then the running sum would be -1 + 9 from array A. The -1 is from dp[1][1]. That running sum is 8. From square number 0, if a throw of 3 is made, then the running sum would be 1 + 9 from array A. The 1 is from dp[0][1]. That running sum is 10. The greatest of these three numbers, 10, 8 or 10, has to be chosen to be recorded in cell dp[3][1], in the table. 10 is chosen.

Square number 4 in column 1 can be arrived at in four different ways. From square number 3, if a throw of 1 is made, then the running sum would be 10 + -1 = 9. From square number 2, if a throw of 2 is made, then the running sum would be 1 + -1 = 0.  From square number 1, if a throw of 3 is made, then the running sum would be -1 + -1 = -2. From square number 0, if a throw of 4 is made, then the running sum would be 1 + -1 = 0. The greatest of these four numbers, 9, 0, -2 or 0, has to be chosen to be recorded in cell dp[4][1]. Nine is chosen. 

Square number 5 in column 1 can be arrived at in five different ways. From square number 4, if a throw of 1 is made, then the running sum would be 9 + -2 = 7. From square number 3, if a throw of 2 is made, then the running sum would be 10 + -2 = 8.  From square number 2, if a throw of 3 is made, then the running sum would be 1 + -2 = -1. From square number 1, if a throw of 4 is made, then the running sum would be -1 + -2 = -3. From square number 0, if a throw of 5 is made, then the running sum would be 1 + -2 = -1.  The greatest of these five numbers, 7, 8, -1, -3 or -1, has to be chosen to be recorded in cell dp[5][1]. Eight is chosen.

The rest of the columns are similarly produced. However, the results begin at i=K and not at i=0 (for the rest). For example, in column 2, i=2 and K=2. The analysis goes downwards. The zeros on the right sides of the rows are the zeros that were there at initialization. Column 2 means the first die number thrown was 2; column 3 means the first die number thrown was 3; column 4 means the first die number thrown was 4; and so on. In the code below, the variable, p is used in subtracting backwards, vertically in a column, making sure i=K is not crossed. 

The N squares are numbered from 0 to N-1, applying the variable, i. The following table shows the addition in each column.

Remember that the result in each cell is as if the game had to end at that cell. In dynamic programming, the result in each cell is as if the algorithm had to end at that cell. 

Consider another given array,

    D = [0, -4, -5, -2, -7, -9, -3, -10]; 

The result table is:

The main difference between this table and the previous one is that N=8, which is more than 6. This means the addition in each column should not descend more than 6 indexes, continuously. In other words, addition should be within a range of 6 indexes, continuously, because the numbers of the die are from 1 to 6. The following table shows the addition in each column: 

The reader should re-do the additions for all these columns, on his/her own. 

The candidate should note that with dynamic programming, the value in each cell has to be the result (or partial result), as if the algorithm had to end at that cell, with the philosophy of breaking down the main problem, into smaller similar problems. The question for this problem is to obtain the maximum value in the last row. So, for this table, the answer is -12, and for the previous table the answer is 8.

Strategy

Remember that the first square of the game always has A[0]. So, dp[0][1] is always A[0], for any given array. 

At the beginning of the solution() function, the two dimensional array is created, with the statement,

    vector<vector<int>> dp(N,vector<int> (6+1, 0));    //zeroth column is not used 

with all elements initialized to 0.

One of the assumptions in the problem description is:

·         N is an integer within the range [2..100,000]; 

This does not mean that the result for N=1 cannot be tested. The following code segment accounts for the case of N=1:

    if (N==1) {
        maxResult = dp[0][1];
        return maxResult;
    }

Smart Solution

The program is (read the code and comments, and then read the more explanation below): 

<script type='text/javascript'>
    "use strict";

    function solution(A) {
        let N = A.length;
    
        const rows = N;
        const cols = 6+1;
        const dp = [];
        for (let i = 0; i < rows; i++) {
            dp[i] = []; 
            for (let j = 0; j < cols; j++) {
                dp[i][j] = 0;    //initialize each cell to 0
            }
        }
        dp[0][1] = A[0];
        let maxResult;
        let lastK = -1;    //last K in last row

        if (N==1) {
            maxResult = dp[0][1];
            return maxResult;
        }

        //determine result for row start and row end cells
        for (let i=1; i<N; i++) {        
            for (let K=1; K<=6 && i-K>=0; K++) {    
                if (i==K) {
                    if (K==1) {
                        dp[0][1] = A[0];
                    }
                    else {
                        dp[i][K] = dp[0][1] + A[i];
                        lastK = K;
                    }
                }

                if (K==1) {        
                    let result = -2000000000;
                    for (let p=1; p<=i && p<=6; p++) {
                        if (dp[i-p][1] + A[i] > result) {
                            result = dp[i-p][1] + A[i]; 
                        }
                    }
                    dp[i][K] = result;
                    lastK = K;  
                }
        }
            //in-between values
            for (let K=2; K<=6 && i-K>0 && i>K; K++) { 
                let result = -2000000000;
                for (let p=1; p<=i-K && p<=6; p++) { 
                    dp[i][K] = dp[i-p][K] + A[i]; 
                    if (dp[i-p][K] + A[i] > result) { 
                        result = dp[i-p][K] + A[i];
                    }
                }
                dp[i][K] = result;
            }    
        }
    
        //Obtain highest result from last row
        maxResult = -2000000000;
        for (let q=1; q<=lastK; q++) {
            if (dp[N-1][q] > maxResult) {
                maxResult = dp[N-1][q];
            }
        }

        return maxResult;
    }
    
    const A = [1, -2, 0, 9, -1, -2 ];    //given
    const res = solution(A);    //calling
    document.write(res + '<br>');
 
</script>

For the example data, the output is: 

    8

At app.codility.com/programmers the scoring and detected time complexity for this solution(), using the particular test cases at app.codility.com/programmers, is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N)

The solution() function needs more explanation. For each index in N, there are two main for-loops, one followed by the other (in parallel). Each of these for-loops has a nested for-loop. The first main for-loop produces the left most value in a row and the right most value in the same row. The right most value in the last row, is the last K value, lastK, for the (one) game. The reader should read through this first main for-loop again, to know how the value at dp[0][1] and the values at dp[i][K] for each K, are obtained. The second main for-loop produces the values in-between the left most value and the right most value, for each row. The reader should read through the second main for-loop again, to know how these in-between values are produced. 

The assumptions in the problem description are:

·         N is an integer within the range [2..100,000];

·         each element of array A is an integer within the range [−10,000..10,000].

Recall that there is addition of numbers for each column. This means that the lowest result is not below: 

    -10,001 x 100,000 = -1,000,100,000

So the search for maximum number should begin from -1,000,100,000, though -2,000,000,000 has been used in the code above.

Thanks for reading.