Hi, @anon89186870 –
Let’s simplify our discussion by assuming Jafar, the player who wants the maximum score at the end, goes first.
When the number of turns is odd, your logic CORRECTLY has Jafar select the cell with the maximum value. (This is correct since an odd turn count means Jafar has the last move. Every time his opponent moves the ball one box to the left or right, Jafar is able to return the ball to the original maximum-value box.)
But when the number of turns is even, Jafar’s opponent moves last. Jafar tries to put the opponent in the position so that the move Almir makes is into the box with the highest possible value.
Your logic selects the cell adjacent to the maximum-value cell. (You pick the smaller of the two adjacent cells to account for Almir’s behavior.) But if Jafar plays optimally, there are times when it’s better to start in a different cell.
For example, if the boxes have these values…
1 1 4 3 5 100 2 1 1
…your logic has Jafar start by putting the ball in 100. His opponent then moves the ball to the box labeled 2 (since 2<5). Jafar keeps moving the ball back to 100, but his opponent keeps returning it to 2, and that’s the final result your solution returns.
But Jafar can optimize by starting the ball in box 3. His opponent, trying to minimize the score, moves the box to 4, but Jafar just moves it back to 3. In the end (since Almir takes the last turn), the ball ends up in 4.
4 > 2, so Jafar was smart to start in box 3.
So reconsider your logic in this part of your code…
else{
if ((maxi != (list.size() - 1 ))&& (maxi != 0)) {
writer.println(Math.min(list.get(maxi - 1), list.get(maxi + 1)));
} else if (maxi == (list.size() - 1)) {
writer.println(list.get(maxi - 1));
} else {
writer.println(list.get(maxi + 1));
}
As a hint: when the turn count is even, Jafar doesn’t care about the box with the maximum value. He is trying to find the starting box in which the result of Almir’s choice is maximized.
Here is the BOXGAM97 problem statement, for reference for other readers (I know you’ve already read this, Abbyankit):