**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;
}
```