PROBLEM LINK:Setter Alei Reyes DIFFICULTY:Easy Medium PREREQUISITES:Observations, Game Theory, Grundy Numbers, Sprague Grundy Theorem PROBLEM:Treat the number of free moves for a pawn as pile of stones. The game hence reduces to, we can remove at most $2$ stones from $i'th$ pile and transfer it to $(i+1)'th$ pile. Stones moved from last pile are lost. We need to tell who wins given the starting configuration. QUICKEXPLANATION:Key to AC Correlation to Grundy numbers, applying Sprague Grundy theorem, and getting that only piles at even indices (starting from end) matter. A number of observations are needed.
With respect to above, the solution is simply XORSUM of grundy numbers all such alternate piles. The first player loses iff the XORSUM is $0$. An explicit formula can be seen as EXPLANATION:The question was more on observation side. Hence, we will try to prove the observations in the main editorial. Calculation of answer from there, as shown in quick explanation, is trivial. 1. Reducing the problem into game of piles and stones. This step is the basic foundation of our solution. Make sure to read it carefully. Lets focus on $i'th$ pawn in initial configuration. Calculate how many moves it can move. We can treat this as number of stones on the $i'th$ pile. More formally, in our reduction to game of piles and stones, we say that, $i'th$ pile has $K$ stones if the $i'th$ pawn can move $K$ steps in initial/given configuration. As an example, for below configuration
Our piles will be $(3,2,1)$ as first pawn can move $3$ steps before getting blocked, the second pawn can move only $2$ steps before being blocked by first pawn and so on. Now, we need to define the operations. A player can move a pawn at most $2$ steps. Say we are considering $i'th$ pawn. An operation on it will reduce number of steps this pawn can move by at most $2$, and increase number of steps $(i+1)'th$ pawn can move by same amount. This is, equivalent to moving at most $2$ stones from $i'th$ pile to $(i+1)'th$ pile. Note that, if current pile is last pile, the stones are removed from the game (as there is no pawn after the last pawn to move on those free cells in original version). 2.If we have a game where we can remove at most $K$ stones per turn, the grundy numbers for that pile repeat at $A_i\%(K+1)$ Refer to example $2$ in the prerequisite link of Grundy Numbers. Our proof is similar. Say we have a pile of $N$ stones, and can remove exactly $1$ stone from it. Grundy number takes values from $0$ (if the first player immediately loses) else $mex(Position_i)$ where $Position_i$ is set of all possible game positions. Lets analyze this for $N=1$ to $N=4$. At $N=0$, first player loses. Grundy number is, hence, $0$. At $N=1$, he wins, hence the Grundy Number takes value of $1$. At $N=2$, the first player is bound to lose. This is same game position as have $0$ stones at start. Hence, Grundy is equal to $0$. For $N=3$, the first player wins by removing $1$ stone, as then player $2$ cannot win no matter what. See the pattern. $GrundyNum=0,1,0,1,....$. Lets take example where we can remove at most $2$ coins now. This is the situation in our current problem. Grundy numbers for a pile with $0$ coins is $0$, pile of $1$ coins is $1$. for a pile of $2$ coins, player $1$ wins by removing $2$ stones  this is a new gaming move/position, hence grundy number is $mex(0,1)=2$. At $N=3$, no matter what he does, the second player can win by removing $1$ or $2$ stones depending on what move player $1$ does. Hence, at $N=3$, player $1$ always loses, and its Grundy number is $3$ (position equivalent to pile with $0$ coins). If we further work up examples for higher $N$, we see that $GrundyNum=0,1,2,0,1,2,0,1,2...$ which is basically $N\%3$ As an exercise, can you work on a formal, or at least intuitional proof for it? The answer is, as usual, in my Chef Vijju's Corner :D. 3. Starting from end, only alternate piles matter Lets say our piles are $(2,4,5,1,3)$. I claim that, piles at position $2$ and $4$, i.e. with stones $4$ and $1$, don't matter. Rest of the piles matter. Let me denote the pile at $i'th$ position by $Pile_i$. Say I moved $2$ stones from $Pile_2$ to $Pile_3$, i.e. from Pile with $4$ stones to Pile with $5$ stones. The opponent can simple copy my move, and move those two stones from $Pile_3$ (one with $5$ stones initially) to $Pile_4$ (the one with $1$ stones initially). More formally, if we move stones from nonsignificant piles, the opponent will simply put them back to a significant pile, which makes it equivalent to us putting stones from first significant pile to the next ourselves. Also, another interesting question. What if we become stubborn, and keep removing stones only from non significant piles? (Hint: Think in terms of who gets to make the last move). An alternative perspective is this Its a game of Nim in alternate piles, starting from last pile. In case a player moves on the insignificant piles, the winning player can simply copy his move and remove those stones from Nim piles by moving them to next insignificant pile, or eliminating them completely if current pile is last pile. This keeps configuration of Nim piles same, and hence losing player is still in losing position. Let me summarize the various intuitions on why we are ignoring the insignificant piles 
4. Wrapping it up Once you see it in a perspective of a game of NIM in alternate piles, the problem becomes trivial. We simply start from end, and XOR the grundy numbers of every pile (which is $A_i \%3$) as in accordance to Sprague Grundy Theorem. If the final XORSUM is $0$, player $1$ loses, else he wins. What is more difficult in the question is, getting the perspective. I will admit that once you get that its a game of NIM on alternate piles, its easy to prove things. But the real question is, how to get this observation in first place? For starters, I feel doing game theory questions based on Grundy numbers regularly is the way to go. This was just a game of nim on alternate piles, we never know what next twist is waiting for us there. :) SOLUTION$Time$ $Complexity=O(N)$ CHEF VIJJU'S CORNER :D1. Proof on Grundy Numbers 2. Answer to the interesting observation in section 2. 3. Derive Grundy numbers for a single pile, with stones from $N=1$ to $N=10$ if you are allowed to remove only $2$, $4$ or $5$ stones at once. Can we get a nice recurrence for it? Why/Why not? 4.Setter's Notes 5. Tester's Explanation for Alternate Piles with an example 6. An alternate intuition on insignificant piles 7. Related Problems
This question is marked "community wiki".
asked 20 Jan, 19:20

I guess I have to read about grundy numbers first :) answered 21 Jan, 18:02

hello, can you please help me understand this alternative thing in more simpler way. I tried to understand this by myself but can't(no problem in understanding grundy numbers) And also what will happen if we apply Sprague Grundy Theorem not alternative but for all piles. answered 22 Jan, 00:00
Did not get time to test it, but I feel it should give wrong answer. Are you clear with the fact that, the opponent always gets a move if you move on insignificant piles?
(22 Jan, 11:59)
thanks @vijju. i think i understand what you were trying to say about alternative thing.
(22 Jan, 19:02)

@vijju What do you mean by nonsignificant piles, and with respect to which player ,current or the opponent ? answered 22 Jan, 02:18
The last pile is always significant. Now from last pile, take every alternating piles. These are the piles which actually determine game, as when all stones are on insignificant piles, the game is already decided. (The player forced to do a move on insignificant pile will always lose as opponent will always have a corresponding move.)
(22 Jan, 12:00)

8. Related Editorial answered 22 Jan, 04:10
1
I liked that editorialist ;)
(22 Jan, 12:07)
1
Reading that editorial is in my wishlist. And one day I will read it. :P
(22 Jan, 14:19)
May god give you patience. I was new then, I wrote a frickin tutorial on how to solve such Qs in middle of editorial. I think I should remove that part someday lol
(22 Jan, 14:30)
Best and easiest method to earn karma seen so far. xD
(22 Jan, 14:39)
No, not moved to another post. Remove is remove.
(22 Jan, 15:28)
