Coin Game | Codestudio Solution with Explanation
Problem Statement
Suggest Edit
a) Both players play in alternate turns and they can remove only one coin in their turn.
b) Any player can remove coins only from either of the two ends of ‘ARR’.
There can be more than one set of coins with maximum value.
a) Consider 3 coins are placed with values [10, 20, 30]: Wong removes 30, then Strange removes 20, then Wong removes 10. Now all coins are taken, and Wong has coins with value 40 and he wins.
b) Consider 1 coin is placed with value [100]: Wong removes the coin and no other coin is left. So, Wong wins with value 100.
a) The game only ends when NO MORE COIN IS LEFT to play with.
b) If a game ends in a draw, Wong is declared the winner.
The first line of input contains an integer 'T', which denotes the number of the test cases. Then the test case follows.
The first line of every test case contains an integer ‘N’ representing the size of the array.
The second line of every test case contains ‘N’ single space-separated integers representing the array elements.
For each test case, print a single integer representing the maximum value of coins you can get for a winning case.
Print the output of each test case in a separate line.
You do not need to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= N <= 10 ^ 3
1 <= ARR[i] <= 10 ^ 7
Where ‘ARR[ i ]’ denotes the value for ‘ith’ element of the array ‘ARR’.
Time Limit: 1 sec.
2
5
5 1 3 2 4
5
6 8 9 2 1
8
16
For the First test case, Wong can win by making moves [5, 2, 1].
For the first time Wong will take coin with value ‘5’ from [5, 1, 3, 2, 4]
Then for the next turn Strange will take the coin with value ‘4’ from [1, 3, 2, 4]
Then for the next turn Wong will take the coin with value ‘2’ from [1, 3, 2]
Then Strange will take the coin with value ‘3’ from [1, 3]
At last Wong will take the coin with value ‘1’ from [1]
For the Second test case, Wong can win by making moves [6, 9, 1].
For the first time Wong will take coin with value ‘6’ from [6, 8, 9, 1, 2]
Then for the next turn Strange will take the coin with value ‘8’ from [8, 9, 1, 2]
Then for the next turn Wong will take the coin with value ‘9’ from [9, 1, 2]
Then Strange will take the coin with value ‘2’ from [1, 2]
At last Wong will take the coin with value ‘1’ from [1]
2
3
1 2 3
4
63 22 56 94
4
150
int maxCoins(vector<int> arr, int n){ vector<vector<int>>dp(n,vector<int>(n,0)); for(int g=0; g<n; g++){ for(int i=0,j=g; j<n; j++,i++){ if(g==0){ dp[i][j]=arr[i]; } else if(g==1)dp[i][j]=max(arr[i],arr[j]); else{ int val=arr[i]+min(dp[i+2][j],dp[i+1][j-1]); int vall=arr[j]+min(dp[i+1][j-1],dp[i][j-2]); dp[i][j]=max(val,vall); } } } return dp[0][n-1]; }
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.