Now that this problem is removed from Long challenge, Can someone tell me, how to solve this problem?
I spent like an entire day and couldn’t crack it (I lack GameTheory a lot). If possible please explain me the logic in simple terms, as I find Game theory to be hardest (for me ) to understand.
The solution is quiet simple
Look if a row is even then in that row chef can eat from starting to n/2
ex- n=6 ,1 3 4 5 6 8 in any case chef can eat only 1 3 4
the question stucks on the part when n is odd
if n=5 ,1 3 4 5 6 then chef can eat 1 3 and ramsay 5 and 6 but the one who will eat 5 will have max value so the one who start first will eat more.
now solution part
consider three rows
n=4 1,4,5,2
n=5,1,2,7,3,4
n=3,1,3,4
for first row chef can eat n/2 part and ramsay will eat n/2 so chef=1+4
for second row chef will eat 1+2 and ramsay 3+4 for sure but who will eat 7?(leave it for now)
for third row chef can eat 1 and ramsay 4 but who will eat 3?(leave it for now) now
you want to maximise for chef so have a vector put 7 and 3 in it.
now sort it in descending order since both of them are trying to maximise there value hence if chef takes 7 because its his chance first then ramsey will take 3 .
if sorted vector contain 7 6 5 4
then if chef start take 7 ramsey takes 6 after that chef takes 5 ramsey 4 conclusion
the logic is straight forward if row is even they cant do anything both of them can eat n/2 part
if row is odd then among multiple odd rows chef will try to eat the row in which the middle element is having higher value. If you are still having doubt you can ask
in such case where odd coins in row, then chef have to take the last(middle) coin and after that in another row rasmi take the last(middle) coin. chef have to look for bigger value of middle coin so ,he must choose that rows where middle coins are of bigger value.you have to take a vactor push_back middle coins in it an short in then reverse it after add (n+1)/2 part of your reversed vector in your total sum.