LOJ 1004 - Monkey Banana Problem

Tags : Dynamic Programming, Memoization

We will be given a diamond shaped array's number of columns, the monkey can climb down only to any of 2 adjacent blocks below, which can also be interpreted as, a block can be updated by summing max value found among the 2 adjacent blocks from upper row. We have to find out the maximum amount of Banana it can consume when he reaches the last block. In other words, we have to find out the maximum cumulative sum can be obtained by traversing in the above mentioned way.

Helpful Resources

• Memoization - WikiPedia

• Memoization (1D, 2D and 3D) - GeeksForGeeks

• What is Dynamic Programming ? - educative.io

• Dynamic Programming, Memoization, Tabulation - freeCodeCamp.org (Video)

Solution

To solve this we must construct a matrix (array/linked list/any similar data structure) to take inputs. We can take inputs in any preferred indexing as long as we can easily determine by ourselves which 2 blocks are adjacent from upper row for a particular block. For example:

Here in this kind of indexing, the 2 adjacent blocks from upper row for block B_{R C} is, B_{(R-1) C} & B_{(R-1) (C-1)} (i.e.: block_{2 1}'s adjacent blocks from upper row are block_{1 1} and block_{1 0} where block_{2 0} has only block_{1 0} ). Remember, we need to avoid negative index.

We will take another matrix of the same dimension to store the max possible value can be reached for each particular block. Now we just simply start updating the values for each block from its upper row and ultimately will obtain the max possible value for end block.

In our implementation,

adjacent blocks from upper row for block[row][column]
= { block[row-1][column], block[row-1][column-1] }
* for block[row][0], adjacent block = block[row-1][0] only

maxBanana[row][column]
= ( maximum( block[row-1][column], block[row-1][column-1] ) )
+ actualBanaMatrix[row][column]

The matrix for cumulative sum looks like this:

As we can see, the end block has the answer.

The above implementation is accepted.

Caution : Remember to use fast I/O for your preferred language as per the suggestion from the problem statement and find out what may disrupt them, so we can avoid it.

Notes:

• You can take input in any pattern, a different pattern will have different indices to point out the adjacent blocks. Compare and update according to your implementation.
• You can use linked list/vector/an implementation of similar data structure, too. Just remember that the read/write time should be constant.
• You can solve this problem by a recursive implementation. Memory limit for this particular problem is 64 MB, so stacks from recursion states won't throw Memory Limit Exceeded exception.

Solution in C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //Enabling fast I/O
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int testCases, numberOfColumns;

    cin >> testCases;
    for (int i = 1; i <= testCases; i++)
    {
        cin >> numberOfColumns;
        int bananaMatrix[2 * numberOfColumns - 1][numberOfColumns]; //Input matrix
        int maxBanana[2 * numberOfColumns - 1][numberOfColumns];    //Memoized matrix

        memset(maxBanana, 0, sizeof(maxBanana));       //Setting 0 to all cell, will update for maximum
        memset(bananaMatrix, 0, sizeof(bananaMatrix)); //Setting 0 to all cell, will update for inputs

        //Input for upper triangle
        for (int row = 0; row < numberOfColumns; row++)
            for (int column = 0; column <= row; column++)
                cin >> bananaMatrix[row][column];

        //Input for lower triangle
        int shiftedPosition = 1;
        for (int row = numberOfColumns; row < (numberOfColumns * 2) - 1; row++)
        {
            for (int column = shiftedPosition; column < numberOfColumns; column++)
                cin >> bananaMatrix[row][column];
            shiftedPosition++;
        }

        /*
        Now we memoize the maxBanna array.
        We will start from the 2nd row (array[1][*]).
        We will check which ever 2 adjacent blocks from up can give more banana and update from the max.
        */

        //Memoizing the upper triangle to store max value
        maxBanana[0][0] = bananaMatrix[0][0];
        for (int row = 1; row < numberOfColumns; row++)
        {
            for (int column = 0; column <= row; column++)
                if (column == 0)//Caution for negative indexes.
                    maxBanana[row][column] = maxBanana[row - 1][column] + bananaMatrix[row][column];
                else
                    maxBanana[row][column] = max(maxBanana[row - 1][column], maxBanana[row - 1][column - 1]) + bananaMatrix[row][column];
        }

        //Memoizing the lower triangle to store the max value
        shiftedPosition = 1;
        for (int row = numberOfColumns; row < (numberOfColumns * 2) - 1; row++)
        {
            for (int column = shiftedPosition; column < numberOfColumns; column++)
                maxBanana[row][column] = max(maxBanana[row - 1][column], maxBanana[row - 1][column - 1]) + bananaMatrix[row][column];
            shiftedPosition++;
        }
        cout << "Case " << i << ": " << maxBanana[2 * numberOfColumns - 2][numberOfColumns - 1] << "\n";
    }

    return 0;
}

Tutorial source