Maximum Coins

Posted: 20 Sep, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :
If the matrix is 
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of input contains two single space-separated integers 'N' and 'M' representing the number of rows and columns of the matrix respectively.

The next 'N' lines contain 'M' single space-separated integers each representing the coins in a row of the matrix.
Output Format:
The only line of output contains a single integer i.e. The minimum coins that can be collected by Alice and Bob. 
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 5
1 <= N <= 10^2
1 <= M <= 10^2
0 <= MAT[i][j] <= 10^3

Time Limit: 1 sec
Approach 1

Intuition:

The idea is to do both traversals concurrently. We start first from (0, 0) and second traversal from (0, m-1) simultaneously. The important thing to note is, at any particular step both traversals will be in the same row as in all possible three moves, row number is increased. Since variation in y could occur in 3 ways i.e bottom, bottom right, bottom right. So in total 9 combinations are possible among y coordinates.

 

Approach:  

  1. We will use recursion and define a helper function having parameters (MAT, ROW_NO, COL_NO1, COL_NO2, N, M), where ROW_NO is the row number at which Alice and Bob will present, COL_NO1 is the column number of Alice and COL_NO2 is the column number of Bob.
  2. From the function, initially we will call helper function which will take parameters (MAT, 0, 0, M-1, N, M), as initially Alice will be at (0,0) hence ROW_NO and COL_NO1 will be 0, and Bob will be at (0, M-1) hence COL_NO2 will be M-1.
  3. In helper function, firstly, we will check for the valid condition as no coordinates should get out of matrix dimensions.
  4. Then we will check whether we have reached the last row of the matrix , if we have then we should check whether both coordinates are at the end then we return the coins otherwise we should return minus infinity.
  5. Initialise the variable coins by minus infinity.
  6. Recur for all possible ways:
    1. (i, x) -> (i+1, x-1) or (i+1, x) or (i+1, x+1)
    2. (i, y) -> (i+1, y-1) or (i+1, y) or (i+1, y+1)
  7. Update the variable coins by the maximum value that is returned by recursion calls.
  8. Final answer would be MAT[i][x] + MAT[i][y] + COINS, if x is not equal to y, otherwise the final answer would be MAT[i][x] + COINS.
  9. Return the final answer.
Try Problem