BOXGAM97 Editorial(Unofficial)

Two friends toss the coin and play k moves of a game. Let's denote two friends as X and Y.Given an array A of length N: N<=100. Player who wins toss can choose any Ai for each valid i, then players can move this index by 1 to left or right.Find the value of element at end of game if both players play optimally.
If K is odd then play who wins the toss will move at last. So if X wins then answer will be maximum element of Array and if Y wins then answer will be minimum element of Array. If X wins the toss and K is even then he knows that Y is going to make the last move so he choose such index so that min(A[i+1],A[i-1]) is maximum possible because Y will move this index to minimum of neighbour and X will undo it until last move when element will be min(A[i+1],A[i-1]). Same can be computed if Y wins the toss and K is even. Please left comment if you have any other approach or doubt. TIME COMPLEXITY:

As we scan array only one time complexity is O(N).

1 Like