Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Maximum Coins

Hard
0/120
Average time to solve is 16m
26 upvotes
Asked in companies
ZS AssociatesSamsungPaypal

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 )
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.
Full screen
Console