## Editorial for COCI '21 Contest 1 #2 Kamenčići

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Notice that the state of the game is completely determined by only three numbers: - the leftmost pebble still in the game, - the rightmost pebble still in the game and - the number of red pebbles collected so far by the player whose turn it is. Using prefix sums on the number of red pebbles in the array, from these numbers, we can easily determine which player will win. Since and from each game state, we can make only two possible moves, a natural idea is to use dynamic programming. The state will be which will be if the current player can win, and otherwise. The number of red pebbles collected so far by the other player can be determined from the information of the state: , where we used to denote this number. The transition is defined as follows:

• , if
• , if
• , otherwise