EXPGAME - Editorial

editorial
, , , , , ,
1

PROBLEM LINKS :

Practice

Contest

Author and Editorialist Vineet Paliwal
Tester Roman Rubanenko

DIFFICULTY :

Easy-Medium

PREREQUISITES :

Basic Game Theory , Zero-sum game , Impartial game , Sprague Grundy Theorem .

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 .

SETTER’S SOLUTION

TESTER’S SOLUTION

2

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.”

3

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

4

@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”.

5

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'
     }`
6

@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.

7

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