You are not logged in. Please login at www.codechef.com to post your questions!

×

GAMEAAM - Editorial

4
1

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

This question is marked "community wiki".

asked 20 Jan '14, 01:28

vaka's gravatar image

2★vaka ♦♦
253131822
accept rate: 16%

edited 20 Jan '14, 17:57

nice editorial

(21 Jan '14, 19:49) akkistar2★

link

answered 20 Jan '14, 04:10

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

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 ♦♦2★

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

link

answered 20 Jan '14, 13:22

orchidmajumder's gravatar image

3★orchidmajumder
3584815
accept rate: 0%

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) vaka ♦♦2★
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) orchidmajumder3★

"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!!

link

answered 21 Jan '14, 03:05

vaibhavatul47's gravatar image

3★vaibhavatul47
4326
accept rate: 0%

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) dawnavd4★
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 P-position is a losing position and a N-position is a winning position.

(21 Jan '14, 09:31) vaka ♦♦2★

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.

link

answered 02 Sep '14, 12:23

hellman's gravatar image

4★hellman
11
accept rate: 0%

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.

(02 Sep '14, 12:30) hellman4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,875
×3,828
×323
×60
×11

question asked: 20 Jan '14, 01:28

question was seen: 5,184 times

last updated: 02 Sep '14, 12:30