Maximum Coins

Hard
0/120
Average time to solve is 16m
27 upvotes
Asked in companies
PayPalDunzoProtium

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5 4
3 6 8 2
5 2 4 3
1 1 20 10
1 1 20 10
1 1 20 10
Sample Output 1:
73
Explanation for Input 1:
Alice will collect coins 3 + 2 + 20 + 1 + 1 = 27 coins.
Bob will collect coins 2 + 4 + 10 + 20 + 10 = 46 coins.
So total coins will get connected are 27 + 46 = 73 coins.
Sample Input 2:
1
4 1
3 
6
7
8
Sample Output 2:
24
Explanation for Input 2:
As, initially both are at (0,0) so either Alice or Bob can pick up 3 coins. Similarly is the case with every coin. So total 24 coins will get picked.
Hint

Think of brute force and try to generate all the possibilities.

Approaches (4)
Recursive Brute Force

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.
Time Complexity

O(9^N), where N is the number of rows and M is the number of columns of the matrix. 

 

As we are making 9 function calls for a particular row.

Space Complexity

O(N), where N is the number of rows and M is the number of columns of the matrix. 

 

As, we are using stack for recursion and recursion depth will be equal to number of rows.

Code Solution
(100% EXP penalty)
Maximum Coins
Full screen
Console