 # EXPGAME - Editorial

## Contest

Author and Editorialist Vineet Paliwal
Tester Roman Rubanenko

# PROBLEM :

Given n piles of stones . In each turn you can remove a^a stones for some natural number a from one of the piles . Given two players
who alternately play their moves , the loser is the one who is unable to make a move. Given an initial configuration you have to predict the winner under the assumption of optimal play .

# EXPLANATION:

### Basic game theory Concept :

In case there is no pile of stones at all the first player loses . In case there are only a few piles , the problem can be solved iteratively .
The base state is when there are 0 stones in all the piles , when the first player loses . For all other states , the state is win for first player if a state which is win for the second player is reachable from it in one move otherwise it is a losing position .

Example : Suppose we have only 1 pile with N stones .

N = 0 : Second win ( base case )

N = 1 : N = 0 is reachable which is second win , hence this position is first win .

N = 2 : N = 1 is reachable , which is first win , hence this position is second win .

N = 3 : N = 2 is reachable , which is second win , hence this position is first win .

N = 4 : N = 3 and N = 0 are reachable , N = 0 is second win , hence this position is first win .
( Note only one of the positions reachable being second win is sufficient for the position to be first win ) .

N = 5 : N = 4 and N = 1 are reachable , N = 1 is first win and N = 4 is first win, hence this position is second win .
( Note when all reachable positions are first win , then the position is second win )

### Sprague Grundy Theorem :

We associate with each position of the game a number called the Grundy number of the position .
The Grundy number of a losing position is 0 . Any other value of grundy number denotes a winning position .
The grundy number of the position is the smallest number which is not a grundy number of the position reachable from it .
The grundy number of a combination of games is the xor of grundy numbers of all the games .

### Explanation :

Subtask 1 and 2 can be solved with Basic game theory .
For subtask 3 apply Sprague Grundy Theorem .

### TESTER’S SOLUTION

Could you please explain this part a bit more?
“For all other states , the state is win for first player if a state which is win for the second player is reachable from it in one move otherwise it is a losing position.”

@tvhong : I have added an example , it illustrates the above line . Let me know if you still have doubts .

@vineetpaliwal, Could you please explain the theorem in little detail ? More specifically this line, “The grundy number of the position is the smallest number which is not a grundy number of the position reachable from it”.

Could anyone explain this part in Tester’s solution a bit more? What is the purpose of “sg[]” array?

``````    `for (j = 1; deg[j] <= i; j++){
used[sg[i- deg[j]]] = o;//mark all reachble positions with 'o'
}```````

@top_coder12345 The meaning of that line can be written in pseudocode as-

``````int grundyNumber(position pos) {
moves[] = possible positions to which I can move from pos
set s;
for (all x in moves)
insert into s grundyNumber(x);
int ret=0;
while (s.contains(ret))
ret++;
return ret;
``````

}

For more details visit this link.

Can you explain how to deal with the second subtask where n=2 with basic game theory?

//