PROBLEM LINKSAuthor: Abdullah Al Mahmud DIFFICULTY:easy PREREQUISITES:Combinatorial Game Theory, Sprague Grundy Theorem Go through these tutorials to understand or refresh the above topics 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 EXPLANATIONThrough 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 So our algo to determine if (a,x) is winning or not in the case of a single game is pretty simple.
Computing Grundy function g(a,b) If b = a*k for some k All its next positions are [(a, a*(k1)), (a, a*(k2)), ..., (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*(k1) + r), (a, a*(k2) + 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. 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. SOLUTIONSSetter's Solution: GAMEAAM.cpp
This question is marked "community wiki".
asked 20 Jan '14, 01:28

You can also see quick and nice explanation of http://codeforces.com/profile/maksay here http://codeforces.com/blog/entry/10450#comment158377 answered 20 Jan '14, 04:10
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.
(20 Jan '14, 09:42)

@vaka,Hi,can you tell me what is the complexity of this algorithm??is it O(logn) for each pair?? answered 20 Jan '14, 13:22
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).
(20 Jan '14, 14:24)
1
Yes..I thought the same also..thank you.And thanks for writing nice editorials which explain the stuffs very nicely :)
(20 Jan '14, 18:41)

"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!! answered 21 Jan '14, 03:05
2
"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
(21 Jan '14, 09:17)
1
@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 Pposition is a losing position and a Nposition is a winning position.
(21 Jan '14, 09:31)

nice editorial