PROBLEM LINKS
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
