my code is passing only one test case !
Optimal game strategy
okay bhaiya Its clear from question whenever PIYUSH picks then there will be even number of elements so I make him pick the bigger one and whenever NIMIT picks there are odd number of elements so I let him pick the one that’s max from both sides but I add it whenever PIYUSH picks so can get the total
Who said that
In starting n can be both odd or even , And piyush makes the first move always I guess.
within if else of even odd check there is one more if else
which are acting as pointer to keep check which element is bigger if its ‘i’ that means from starting so increment i++ otherwise if from last so decrement j =j-1;
mentioned in question always even
So u are always picking maximum element ?
yes picking max on piyush turn and adding the value returned but when picking max for nimit so just move pointer
Picking the greatest always won’t help ,say
4
100 1000 10 90
Here I will pick 90 first so that opponent don’t get access to 1000 and he will pick 100 then I pick 1000
and he picks 10 so answer is 1090
So this means its not always the greatest we pick .’
logic:
Remember both A and B are equally smart and we want A to get maximum.
if coins are indexed from i to j and both have to choose one out of two ends.
case 1: if A chooses a[i], now opponent can choose either a[i+1] or a[j] whatever is maximum out of two. which means A will get Minimum in his next chance based on opponent choice.
case 1.a: if opponent choose a[i+1], player will chose either a[i+2] or or a[j]
case 1.b: if opponent choose a[j], player will chose either a[i+1] or or a[j-1]
So A will get minimum out of case 1.a and case 1.b…as opponent is equally smarter and choose such a coin which give him maximum but minimum to player A.
case 2: if A chooses a[j], now opponent can choose either a[i] or a[j-1] whatever is maximum out of two. which means A will get Minimum in his next chance based on opponent choice.
case 2.a: if opponent choose a[i], player will chose either a[i+1] or or a[j-1]
case 2.b: if opponent choose a[j-1], player will chose either a[i] or or a[j-2]
So A will get minimum out of case 2.a and case 2.a…as opponent is equally smarter and choose such a coin which give him maximum but minimum to player A.
This will give you a recursive case in which final answer is max(case1,case2)
4
1 2 3 4 then for this test case answer should have been 7
How
If we pick 4 then he will pick 3 and then we will pick 2 so ans is 6
If we pick 1 then he picks 4 and then we pick 3 so here ans is 4
so max(4,6) is 6 so ans is 6
and in above exampe you pick 90 so he could be clever too and pick 10 not 100
Even if he pick 10 ,we will get access to 1000
okay sorry that will still make u get 1000 i am not able to get this problem
does this involve backtracking ?
No it doesn’t
Go through this approach
okay I modified my solution now only one test case is failing which was the only one earlier getting passed plz help me bhaiya
now I am not playing greedy.
Hey @coderajay03
Mentioned the changes in comments : https://ide.codingblocks.com/s/362660
We did so
Because other player also plays optimally 
1 Like