You are not logged in. Please login at www.codechef.com to post your questions!

×

ADAPWNS - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Alei Reyes
Tester- Pranjal Jain
Editorialist- Abhishek Pandey

DIFFICULTY:

Easy- Medium

PRE-REQUISITES:

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.

QUICK-EXPLANATION:

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.

  • 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)$
  • Grundy number of overall game is XOR of all piles, as per Sprague Grundy theorem.
  • Lets reverse the piles, so that its easier to denote and understanding. In this new pile, starting from first pile (the last pile in original configuration), only alternate piles matter. This is because, moving on moving stones from other piles, opponent can simply shift them to next pile by mirroring our move. As an example, say our piles were $(2,3,1)$. Reverse them. We get $(1,3,2)$. Any stone we move from the middle pile to last pile, is discarded by the opponent by mirroring our move on last pile.

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-

View Content

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-

...P..P.P....

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 pre-requisite 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 non-significant 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 -

  • If the losing player makes move on these piles, then winner can simply mirror it and move the piles to next insignificant pile, or even eliminate them if current pile was last pile.
  • If a player moves on these insignificant piles, then the other player gets to remove the stones, or move them to next insignificant pile. Hence, the other player is guaranteed another move.

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

Setter

View Content

Tester

View Content

$Time$ $Complexity=O(N)$
$Space$ $Complexity=O(N)$

CHEF VIJJU'S CORNER :D

1. Proof on Grundy Numbers-

View Content

2. Answer to the interesting observation in section 2.-

View Content

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-

View Content

5. Tester's Explanation for Alternate Piles with an example-

View Content

6. An alternate intuition on insignificant piles-

View Content

7. Related Problems-

This question is marked "community wiki".

asked 20 Jan, 19:20

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 21 Jan, 01:14

admin's gravatar image

0★admin ♦♦
19.8k350498541


Fantastic editorials!

link

answered 21 Jan, 01:42

mindjolt's gravatar image

5★mindjolt
223
accept rate: 0%

Thank you :)

(21 Jan, 10:39) vijju123 ♦♦5★

I guess I have to read about grundy numbers first :)

link

answered 21 Jan, 18:02

semantycs's gravatar image

3★semantycs
294
accept rate: 11%

The way of denoting piles for tester and setter is different.. causing confusion..other than that the editorial is great.

link

answered 21 Jan, 20:56

subash23's gravatar image

4★subash23
1
accept rate: 0%

Hey,

If I recall right, both of them used "Distance this pawn can move" as number of stones on that pile. Can you point where you feel its different? :)

(22 Jan, 11:58) vijju123 ♦♦5★

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.

link

answered 22 Jan, 00:00

abhi_uchiha's gravatar image

4★abhi_uchiha
1
accept rate: 0%

And also what will happen if we apply Sprague Grundy Theorem not alternative but for all piles.

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) vijju123 ♦♦5★

thanks @vijju. i think i understand what you were trying to say about alternative thing.

(22 Jan, 19:02) abhi_uchiha4★

@vijju What do you mean by non-significant piles, and with respect to which player ,current or the opponent ?

link

answered 22 Jan, 02:18

sudhanshu6324's gravatar image

4★sudhanshu6324
1
accept rate: 0%

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) vijju123 ♦♦5★

One of the sections of argument above says: When you make a move on an insignificant pile, your opponent is always guaranteed a move.

But the argument doesn't seem relevant. One could say: "When you make a move on a pile of three or more, your opponent is always guaranteed a move." The logic doesn't seem to help.

In some sense what matters is that after a move from an alternating zeros position of the form 0,x,0,y,0,z,0 then a mirroring move will return to one of these alternating zeros positions.

When on a winning strategy, the idea of mirroring the opponent's move after a move from an insignificant pile is certainly correct. But seems to be tricky to find the reason.

link

answered 22 Jan, 03:47

john_smith_3's gravatar image

6★john_smith_3
59517
accept rate: 26%

But seems to be tricky to find the reason.

I very much agree to that. Only for this reason, ADAPWNS was the second last editorial written (more difficult problems had their editorials ready beforehand) because I needed more time to get an intuition.

My intuition was that, once all stones are on those insignificant piles, the player who makes first move on those piles has to lose, as his opponent will always have a move of putting stones on next insignificant pile/eliminating them (if its the last pile). Thats true even if that pile has $< 3$ stones.

Your mirroring point seems correct. :)

(22 Jan, 12:03) vijju123 ♦♦5★

And yes, I am always taking feedback/alternate explanations which can better the editorial. After interacting with one of the contestants, I added section $6$ in my bonus corner. In case you also have anything else, please let us all know - everyone is always welcome to discuss any alternate solutions especially if they can be better than my explanation :)

(22 Jan, 12:05) vijju123 ♦♦5★

8. Related Editorial-
AMR16J-Editorial

link

answered 22 Jan, 04:10

aryanc403's gravatar image

6★aryanc403
2.5k1516
accept rate: 10%

1

I liked that editorialist ;)

(22 Jan, 12:07) vijju123 ♦♦5★
1

Reading that editorial is in my wishlist. And one day I will read it. :P

(22 Jan, 14:19) aryanc4036★

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) vijju123 ♦♦5★

Best and easiest method to earn karma seen so far. xD
Because you don't get karma for editorial. So you have decided to remove tutorial from it and published it as another post. XD

(22 Jan, 14:39) aryanc4036★

No, not moved to another post. Remove is remove.

(22 Jan, 15:28) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×317
×247
×60
×13

question asked: 20 Jan, 19:20

question was seen: 1,090 times

last updated: 22 Jan, 19:02