Last Updated: 17 Oct, 2021
Coins and Rows
Moderate
Asked in company
Ninja and his friend is playing a matrix game in which a matrix having 2 rows and N columns. Each cell of the matrix has some gold coins. Initially, Ninja will start from the cell (1,1) and will move to cell (2, N) which the following moves:
1. Move Right - From cell (i,j) to cell (i,j+1).
2. Move Down - From cell (i,j) to cell (i+1,j).
Ninja will pick the coins from each cell he visits. Now, it’s his friend’s turn. He also performs the moves to reach (2, N) from (1,1). But he can collect only the coins that Ninja hasn’t picked.
The score of the game is the total coins picked by Ninja’s Friend. Ninja will try to minimize the score while his friend will try to maximize the score. Find the score of the game if both the players play optimally.
You are given a matrix ‘M’ of size 2*N. Your task is to find the score of the game if both players play optimally.
For Example
If the given matrix is ‘M’ = [ [1,3, 9] , [3,5,1 ].The path taken by
Ninja is 1,3,9,1 and the path taken by his friend is 1,3,5,1. So the total coins picked by his friend is 3+5 =8.
So, the score is 8.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N’ denoting the number of columns in the matrix.
The next two lines contain N elements representing row 1 and row 2 of the matrix.
Output Format:
For each test case, print an integer corresponding to the score of the game if both players play optimally.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N<= 10^5.
1 <= M[i][j] <=5 * 10^3.
Time limit: 1 sec
Approaches
If we observe a pattern in the path opted by Ninja,the path will be to this type given in the image below.It consist of a prefix of first row and the suffix of second row.
So,the second player(Ninja’s Friend) have either collect the coins from the suffix of first row or the prefix of the second row.But Ninja is playing first,so will try to pick the coins in such a way that his friends gets the minimum amount of coins.
There can be ‘N’ total different paths that can Ninja opt.So,we will iterate all these paths and find the minimum score his friend can achieve.
Algorithm:
- Declare two integers ‘SUFFIX_SUM’ and ‘PREFIX_SUM’ to store the sum of coins.
- Set ‘SUFFIX_SUM’ and ‘PREFIX_SUM’ as 0.
- For i in range 0 to ‘N’-1:
- Set ‘SUFFIX_SUM’ as ‘SUFFIX_SUM’ + M[0][i].
- Set ‘ANS’ as INT_MAX.
- For i in range 0 to ‘N’-1:
- Set ‘SUFFIX_SUM’ as ‘SUFFIX_SUM’ - M[0][i].
- ‘SCORE’ is the coin Ninja’s Friend can pick if Ninja switches the row at i’th index.
- Set ‘SCORE’ as the maximum of ‘PREFIX_SUM’ and ‘SUFFIX_SUM’.
- Set ‘ANS’ as the minimum of ‘ANS’ and ‘SCORE’.
- Set ‘PREFIX_SUM’ as ‘PREFIX_SUM’ + M[1][i].
- ‘ANS’ is the score if both players play optimally.
- Return ‘ANS’.
Similar problems