GAMEAAM - Editorial

PROBLEM LINKS

Contest

Practice

Author: Abdullah Al Mahmud

Tester: Gerald Agapov

Editorialist: Praveen Reddy Vaka

DIFFICULTY:

easy

PREREQUISITES:

Combinatorial Game Theory, Sprague Grundy Theorem

Go through these tutorials to understand or refresh the above topics

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames

http://www.codechef.com/wiki/tutorial-game-theory

http://www.codechef.com/wiki/tutorial-coin-game

If you are totally new to these topics it is suggested you go through these notes http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf

EXPLANATION

Through out this problem we will consider number pairs of the form (a,b) such that a <= b. If the input contains a pair in reverse order we can just swap them. The game can be viewed as a directed graph where a pair denotes a node and each node has outgoing edges to all the pairs which can be obtained by the constraint in the problem. We consider (a,a) to be a losing position for all a, so the target of any player to reach a pair.

If we can solve the question for a single pair (a,b) we can use the Sprague Grundy Theorem to solve the composite game involving multiple such pairs by computing the grundy function g(a,b).

Solving a single game (a,b)

For a given position (a,b) we can move to the following positions (we will call this next positions)
(a, b - k*a) for all 1 <= k < floor(b/a) - 1
and (b%a, a)

i.e., if we are at position (5, 26) we can move to (5, 21), (5, 16), (5, 11), (5, 6), (1, 5)

A position (a,b) is winning if among all its next positions there exists at least one position which is losing position.
A position (a,b) is losing if all its next positions are winning positions, since no matter what the current player does the next player gets a winning position.

Since our graph is huge (numbers can be as big as 10^8) we can’t compute the win loss values of target position by exploring all possible paths to terminals. Even we can’t pre compute values for the same reason as the size of the graph is very huge. We shall look at an efficient way of finding out if a position (a, b) is winning or losing.

Let us define f(a,b) to be 0 if the position (a,b) is losing and 1 if it is winning.

We have already seen the next positions for a given (a,b) and it is a simple linear path always, we can exploit this to find out win loss values efficiently.

For a given (a,x) and x >= a we can group the number in the following way.

For all 0 <= i < a group i will contain all the number pairs [(a, a+i), (a, 2*a+i), (a, 3*a+i), (a, 4*a+i), (a, 5*a+i), …]

For a given element in the list it will be the next position of all other elements coming after that in the list. Additionally except for the case i != 0 (i,a) will be a next position for all the pairs in the list. This is illustrated in the diagram below.

when i=0 the node (i,a) will not be present in the graph. By our construction for a node (a,a*k+i) all its next positions have to occur in the sub graph shown above.

when i != 0

If f(i,a) = 1 then f(a, a+i) = 0 and for all k > 1 f(a, k*a+i) = 1 since they can move to (a, a+i).

If f(i,a) = 0 then f(a, a+i) = 1 and also for all k > 1 f(a, k*a+i) = 1 as all (a, a*k+i) have (i,a) as their next position.

when i = 0

we have f(a,a) = 0 by definition. So for all k > 1 f(a, k*a) = 1 since they can move to (a, a).

So our algo to determine if (a,x) is winning or not in the case of a single game is pretty simple.

f(a,x):
  if (x == a) return 0;
  if (x >= 2*a) return 1;
  return 1 - f(x%a, a);

Computing Grundy function g(a,b)

g(a,b) is defined as the minimum non negative number which is not present in the set {g(c,d) | (c,d) is next position to (a,b)}. Terminal nodes have values of 0. All other nodes can be given values based on the criteria since our graph representing the game is a directed acyclic graph. g(a,b) will be 0 if and only if it is a losing position.
Extending on the ideas to compute f(a,b) we can also compute g(a,b) efficiently.

If b = a*k for some k All its next positions are [(a, a*(k-1)), (a, a*(k-2)), …, (a,a)]. Since (a,a) is a terminal node g(a,a) = 0. The pairs are connected as shown in the figure above. So we can only give the grundy numbers to them in a linear order. g(a, 2a) = 1, g(a, 3a) = 2 and so on. So for g(a,b) = g(a, a*k) = k -1 = (b/a) - 1;

If b = a*k + r for k>=1 and 1<= r < a the next positions are [(a, a*(k-1) + r), (a, a*(k-2) + r), …, (a,a + r), (r,a)]. Again connectivity among the pairs is as shown in the figure. The value of g(r,a) governs the grundy value of other numbers in the list.

If g(r,a) = 0 i.e., it is a losing position, then g(a, a+r) = 1 g(a, a+2r) = 2 … g(a, b) = g(a, a*k + r) = k = floor(b/a)

If g(r, a) != 0 then g(a, a+r) = 0 and we can give values to the pairs in a linear order as before but the value g(r, a) cannot be assigned to any position as (r, a) is a neighbor to all of these.
If g(r, a) = 2 the we will have g(a, a+r) = 0, g(a, a+2r) = 1, g(a+3r) = 3, g(a+4r) = 4, … refer to tester’s solution to how to simply compute this.

Once we can compute the grundy number for a single game all we need to do is find the grundy numbers of all the games and xor them together. If the result is 0 second player wins and if it is 1 the first player wins.

The single game happens to be a well studied game and goes by the name Euclid Game. There even exists a closed form solution for finding the grundy number for a given single game. Refer to http://www.sciencedirect.com/science/article/pii/S0012365X06003505. Setter’s solution uses this.

SOLUTIONS

Setter’s Solution: GAMEAAM.cpp

Tester’s Solution: GAMEAAM.cpp

4 Likes

You can also see quick and nice explanation of http://codeforces.com/profile/maksay here
http://codeforces.com/blog/entry/10450#comment-158377

1 Like

@vaka,Hi,can you tell me what is the complexity of this algorithm??is it O(logn) for each pair??

“A position (a,b) is winning if among all its next positions there exists at least one position which is losing position. A position (a,b) is losing if all its next positions are winning positions”.
Please explain!!

To simplify things, we can see that one pair (a, b) is equal to a stack of numbers. A player can subtract any number from the top number (but the result should stay positive) or a player can remove the top number.

E.g. for (5, 28) it will be:

28/5 = 5 -> (5, 3)

5/3 = 1 -> (2, 3)

3/2 = 1 -> (2, 1)

2/1 = 2 but at this last step we can’t subtract 2 from 2, so this value should be decremented.

The stack is (1, 1, 1, 5). I think from this vision it’s easier to calculate the Sprague-Grundy function.

Thanks Praveen for linking to maksay’s comment. The essential idea is the same. I have now updated the editorial. My previous editorial was very complicated and unclear, so rewrote it from scratch and hence the delay in publishing.

Yes. It is just like gcd, look at tester’s solution. in each call to grundy(a, b) you do constant amount of work and make a recursive call to grundy(b%a, a).

Yes…I thought the same also…thank you.And thanks for writing nice editorials which explain the stuffs very nicely :slight_smile:

1 Like

“Winning position” means a position from which person who move next can win.

“Losing position” means a position from which person who move next will lose, there is no way to win from this position.

So clearly a position (a,b) is winning if among all its next position there exists at least one position which is losing, because then you can convert position (a,b) to a losing position for your opponent and win the game.
And if all next position are winning then, no matter what move to choose you would give a winning position to you opponent, which mean you can never win hence it is a losing pos

2 Likes

@dawnavd has explained it correctly. If you are new to game theory please go through http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf this. In that document a P-position is a losing position and a N-position is a winning position.

1 Like

nice editorial

This game with stacks looked very simple for me (I knew nothing about the game “nim” or Grundy function) so I struggled with it. I tried to solve simplified versions (e.g. all stacks of height 1 = the game of “nim”) and even more simplified, with 3 numbers. But the results got complicated quickly.

How the hell XOR can be guessed here?.. But yeah, even if one guesses XOR for height-1 game, there’s no obvious way to solve the full game without knowledge of Grundy’s function.