PROBLEM LINK : Game Of Greed
Author:padma00
Editorialist: padma00
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
Basic Dynamic-Programming link .
PROBLEM:
In the problem Kaneki and Touka are playing a game of choosing card and add the number written on the card to our sum and basically we have to check if Kaneki is able to do his sum more than sum of Touka and some points to be noted are
- Basic rule of the game is while choosing a card is player can choose either rightmost or leftmost card.
- Numbers written on the card are not necessarily distinct.
- First turn will be played by Kaneki.
- Both the players are supposed to play the game optimally.
- If tie is there Touka is the winner.
QUICK EXPLANATION:
Here to get final solution we will compair kaneki’s sum and Touka’s sum at each step by subtracting Touka’s sum into Kaneki’s sum.
EXPLANATION:
Let’s take two pointers left=0 ,right=n-1 where n is length of an array of cards,
here we know that first turn will be played by Kaneki so whenever Kaneki is playing this
(left+right)\bmod 2 != n\bmod 2
condition will satisfy and this is the way from which we can understand whose turn is this.
Players are playing optimally so kaneki will add the maximum of two cases (recursive statements)
first is taking leftmost + then what happens with remaining elements and
second is taking rightmost + then what happens with remaining elements
while touka’s turn she will also do the same but in different way so that at each step we are able to compute difference of the scores so she will choose the minimum of two cases(recursive statements) as taking minimum of this means in her perspective taking maximum among two options.
first is subtracting leftmost + then what happens with remaining elements
second is subtracting rightmost + then what happens with remaining elements
while doing all this left and right pointer will change and this process will stop when
left>right
and at the end we will be having resultant sum of both i.e kaneki’s score subtracted by Touka’s score and if resultant sum is strictly greater than Zero then Kaneki is the winner as his score was greater else Touka is the winner.
SOLUTIONS:
Editorialist's Solution
#include < bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll dp[1001][1001];
ll resultant_sum(ll left,ll right,vector< ll >&arr){
if(left > right){
return 0;
}
else if(dp[left][right]!=-1){
return dp[left][right];
}
// Touka's turn where ((left+right)%2==n%2)
else if((left + right)%2 == (n%2)){
ll case1 = -arr[left]+resultant_sum(left+1,right,arr);
ll case2 = -arr[right]+resultant_sum(left,right-1,arr);
dp[left][right]= min(case1,case2);
return dp[left][right];
}
//kaneki's turn where ((left+right)%2!=n%2)
else{
ll case1 = arr[left]+resultant_sum(left+1,right,arr);
ll case2 = arr[right]+resultant_sum(left,right-1,arr);
dp[left][right]=max(case1,case2);
return dp[left][right];
}
}
int main() {
ll tc;
cin>>tc;
while(tc--){
cin >> n;
vector< ll > arr(n);
for(ll i = 0 ; i < n ; i ++ ) {
cin >> arr[i];
}
ll left = 0,right = n-1;
memset(dp,-1,sizeof(dp));
ll sum =resultant_sum(left,right,arr);
if(sum>0){
cout << "Kaneki\n";
}
else{
cout << "Touka\n";
}
}
return 0;
}