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

×

FDIVGAME - Editorial

3
4

PROBLEM LINK:

Contest
Practice

Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Easy

PREREQUISITES:

Game theory, Combinatorial game theory, Sprague-Grundy theorem

PROBLEM:

A game is played by two players with $N$ integers $A_1, A_2, \ldots, A_N$. On his/her turn, a player selects an integer, divides it by $2$, $3$, $4$, $5$ or $6$, and then takes the floor. If the integer becomes $0$, it is removed. The last player to move wins. Which player wins the game?

QUICK EXPLANATION:

The solution uses the Sprague-Grundy theorem. Define $G(n)$ as the following (recursively):

$$G(n) = \begin{cases} 0 & \text{if $n = 0$} \\ 1 & \text{if $n = 1$} \\ 2 & \text{if $n \in \{2,3\}$} \\ 3 & \text{if $n \in \{4,5\}$} \\ G(\lfloor n/12 \rfloor) & \text{if $n \ge 6$} \end{cases}$$

If the bitwise XOR of $G(A_1), G(A_2), \ldots, G(A_N)$ is $0$, then the second player wins (Derek), otherwise the first player wins (Henry).

EXPLANATION:

This is an example of an impartial game played under normal play condition, so the Sprague-Grundy theorem applies. The Sprague-Grundy theorem states that every such game is equivalent to a nimber. We can look at each $A_i$ as a game independent of the other values, and the game itself as the sum of these $N$ games. So, the theorem implies that every integer $A_i$ can be replaced by a pile of nim of a certain size, and winning positions are preserved, i.e., winning positions are converted into winning positions, and losing positions are converted into losing positions.

To be more specific, we will convert the game into a game of nim with $N$ piles, where the size of the $i$th pile is the nimber that is equivalent to $A_i$. Let's call this size $G(A_i)$. The proof of the theorem implies that $G(n)$ is equal to the smallest nonnegative integer that is not equal to $G(n')$ for any $n'$ that is a successor of the game, i.e. $n' \in \{\lfloor n/2\rfloor, \lfloor n/3\rfloor, \lfloor n/4\rfloor, \lfloor n/5\rfloor, \lfloor n/6\rfloor \}$. In other words, $G(n)$ is the minimum excluded value of the set $\{G(\lfloor n/2\rfloor), G(\lfloor n/3\rfloor), G(\lfloor n/4\rfloor), G(\lfloor n/5\rfloor), G(\lfloor n/6\rfloor) \}$. Since the integer $0$ is always removed, we can set $G(0) = 0$.

But recall that a nim position is winning if and only if the bitwise XOR of the sizes of the piles is nonzero! Thus, in the original game, the first player is winning if the bitwise XOR of the numbers $G(A_1), G(A_2), \ldots, G(A_N)$ is not zero. Thus, we can answer the problem if we can compute $G(n)$ for any $n$.

If you're unfamiliar with Sprague-Grundy theorem, we will explain in the appendix why the original game is equivalent to the nim game with pile sizes $G(A_1), G(A_2), \ldots, G(A_N)$.

Computing $G(N)$

We can easily compute $G(N)$ by definition:

def G(n):
    if n == 0:
        return 0
    else:
        return mex({G(n/2), G(n/3), G(n/4), G(n/5), G(n/6)})

def mex(s):
    value = 0
    while s contains value:
        value++
    return value

Unfortunately, this is very slow, because each call to $G(n)$ needs five recursions! This easily blows up quickly, and you'll find that it takes a really long time even for $G(10^8)$. For $G(10^{18})$ there's no hope.

We can optimize this by memoizing $G(n)$, that is, storing previously computed values so they only need to be computed once. This solution actually makes computing a single value of $G$ easier; $G(10^{18})$ now finishes instantly! Sadly though, doing this $N = 100$ times for $T = 1000$ cases is still too slow. So how do we compute $G$ much more quickly?

Let's look at the sequence $G(0), G(1), G(2), G(3), \ldots$ first. Here is the sequence: $$\begin{array}{r|rrrrrrrrrrrrrrr} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline G(n) & 0 & 1 & 2 & 2 & 3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 \end{array}$$ To write it more compactly, let's express it as a sequence of runs:
$$\begin{array}{r|r} \text{$n$ range} & G(n) \\ \hline [0,1) & 0 \\ [1,2) & 1 \\ [2,4) & 2 \\ [4,6) & 3 \\ [6,12) & 0 \\ [12,24) & 1 \\ [24,48) & 2 \\ [48,72) & 3 \\ [72,144) & 0 \\ [144,288) & 1 \\ [288,576) & 2 \\ [576,864) & 3 \\ [864,1728) & 0 \\ [1728,3456) & 1 \\ [3456,6912) & 2 \\ [6912,10368) & 3 \\ [10368,20736) & 0 \end{array}$$ Where $[x,y)$ denotes the set $\{n \in \mathbb{Z} : x \le n < y\}$. Notice something interesting if we express the range bounds another way: $$\begin{array}{r|r} \text{$n$ range} & G(n) \\ \hline [0,1) & 0 \\ [1,2) & 1 \\ [2,4) & 2 \\ [4,6) & 3 \\ [6,12) & 0 \\ [1\cdot 12,2\cdot 12) & 1 \\ [2\cdot 12,4\cdot 12) & 2 \\ [4\cdot 12,6\cdot 12) & 3 \\ [6\cdot 12,12\cdot 12) & 0 \\ [1\cdot 12^{2},2\cdot 12^{2}) & 1 \\ [2\cdot 12^{2},4\cdot 12^{2}) & 2 \\ [4\cdot 12^{2},6\cdot 12^{2}) & 3 \\ [6\cdot 12^{2},12\cdot 12^{2}) & 0 \\ [1\cdot 12^{3},2\cdot 12^{3}) & 1 \\ [2\cdot 12^{3},4\cdot 12^{3}) & 2 \\ [4\cdot 12^{3},6\cdot 12^{3}) & 3 \\ [6\cdot 12^{3},12\cdot 12^{3}) & 0 \end{array}$$ Hmmm. It seems that the sequence $\{G(n)\}$ actually follows a simple pattern! Namely:

  • $G(0) = 0$
  • If $n \in [12^k, 2\cdot 12^k)$, then $G(n) = 1$.
  • If $n \in [2\cdot 12^k, 4\cdot 12^k)$, then $G(n) = 2$.
  • If $n \in [4\cdot 12^k, 6\cdot 12^k)$, then $G(n) = 3$.
  • If $n \in [6\cdot 12^k, 12\cdot 12^k)$, then $G(n) = 0$.

But is this true in general? And how do we prove that? Well, it turns out that you can easily prove this by induction:

  • For the base case, you can easily compute $G(n)$ for $n < 12$ by hand to see that the statement is correct.
  • For the first case, assume $n\in [12^k, 2\cdot 12^k)$. Then $\lfloor n/2 \rfloor \in [6\cdot 12^{k-1}, 12\cdot 12^{k-1})$, and $G(\lfloor n/2 \rfloor) = 0$ by induction, which implies that $G(n) \ge 1$. On the other hand, $G(\lfloor n/j \rfloor)$ cannot be equal to $1$ because $\lfloor n/j \rfloor$ is always in the range $[2\cdot 12^{k-1}, 12\cdot 12^{k-1})$, and by induction $G(\lfloor n/j \rfloor) \not= 1$. This implies that $1$ is the minimum excluded value, and $G(n)$ is actually $1$.
  • For the second case, assume $n \in [2\cdot 12^k, 4\cdot 12^k)$. Then we can similarly show that $G(\lfloor n/2\rfloor) = 1$ and $G(\lfloor n/4 \rfloor) = 0$, which implies that $G(n) \ge 2$. On the other hand, $G(\lfloor n/j \rfloor)$ cannot be equal to $2$ because $\lfloor n/j \rfloor$ is always in the range $[4\cdot 12^{k-1}, 2\cdot 12^k)$, and by induction $G(\lfloor n/j \rfloor) \not= 2$. This implies that $2$ is the minimum excluded value, and $G(n)$ is actually $2$.
  • The third and fourth cases can be proven with similar arguments as above.

So now we have another way to compute $G(n)$:

def G(n):
    if n == 0:
        return 0
    k = 0
    while 12**(k+1) > n: // '**' is exponentiation
        k += 1
    q = n / 12**k
    if q < 2:
        return 1
    if q < 4:
        return 2
    if q < 6:
        return 3
    return 0

This is much faster than before and is actually fast enough to solve the problem!

We can actually implement $G(n)$ another way by noticing that $G(n) = G(\lfloor n/12 \rfloor)$:

G_small = [0,1,2,2,3,3,0,0,0,0,0,0]
def G(n):
    return (if n < 12 then G_small[n] else G(n/12))

This has the same running time as the previous $G(n)$ but is easier to type!

The time complexity of computing $G(n)$ is is $O(\log_{12} n) = O(\log n)$, so the running time of the overall algorithm is $O(N \log A_\max)$, or more tightly, $O(\sum_{i=1}^N \log A_i)$.

Appendix: Equivalence to nim

If you're unfamiliar with Sprague-Grundy theorem, here we'll try to explain why the original game with the integers $[A_1, A_2, \ldots, A_N]$ is equivalent to the nim game with pile sizes $[G(A_1), G(A_2), \ldots, G(A_N)]$. Here, "equivalent" means that the first game is a winning position if and only if the second game is also a winning position.

Recall that in nim, a move consists of choosing a pile and removing a nonzero number of things from the pile. You can also look at it as choosing a pile and then replacing it with a strictly smaller pile. They're clearly equivalent, but thinking of it using the latter way will make it easier to understand this section.

Suppose we're playing nim with pile sizes $[a_1, a_2, \ldots, a_N]$. It's a well-known fact that this is a winning position if and only if $a_1 \oplus a_2 \oplus \ldots \oplus a_N$ is nonzero, where $\oplus$ denotes bitwise XOR. But why is this true? Here's why.

  • If $a_1 \oplus a_2 \oplus \ldots \oplus a_N = 0$, then any move will make the bitwise XOR nonzero. To see why, suppose your move was to reduce the $i$th pile from $a_i$ to $a_i'$. Then the new bitwise XOR will be equal to

    $$\begin{align*} & a_1 \oplus a_2 \oplus \ldots \oplus a_i' \oplus \ldots \oplus a_N\\ &= (a_1 \oplus a_2 \oplus \ldots \oplus a_i \oplus \ldots \oplus a_N) \oplus a_i \oplus a_i'\\ &= 0 \oplus a_i \oplus a_i'\\ &= a_i \oplus a_i' \end{align*}$$

    which is nonzero because $a_i \not= a_i'$.

  • If $a_1 \oplus a_2 \oplus \ldots \oplus a_N \not= 0$, then there exists a move that will make the bitwise XOR equal to $0$. To show this, let $x = a_1 \oplus a_2 \oplus \ldots \oplus a_N$, and let $k$ be the largest $1$ bit in $x$. Thus, there exists an $i$ such that the $k$th bit of $a_i$ is $1$. (Otherwise, the $k$th bit of $x$ cannot be $0$.) The move is to replace $a_i$ with $a_i \oplus x$. Clearly, doing that move will make the bitwise XOR $0$, but it's only a valid nim move if $a_i \oplus x < a_i$. But this is true because the largest bit where $a_i \oplus x$ and $a_i$ differ is the $k$th bit, the $k$th bit of $a_i$ is $1$, and the $k$th bit of $a_i \oplus x$ is $0$. Thus, $a_i \oplus x < a_i$!

Now that we know the strategy for nim, let's now prove why the original game is equivalent to the nim game $[G(A_1), G(A_2), \ldots, G(A_N)]$. Recall that $G(n) = \operatorname{mex}\{G(\lfloor n/2\rfloor), G(\lfloor n/3\rfloor), G(\lfloor n/4\rfloor), G(\lfloor n/5\rfloor), G(\lfloor n/6\rfloor) \}$, where $\operatorname{mex}(S)$ is the smallest nonnegative integer not in $S$.

Clearly, any move in the nim game $[G(A_1), G(A_2), \ldots, G(A_N)]$ corresponds to some move in the original game $[A_1, A_2, \ldots, A_N]$ because of the way $G(n)$ is defined: If $G(n) = v$, then every value $v' < v$ can be obtained as $G(\lfloor n/k\rfloor)$ for some $k\in \{2,3,4,5,6\}$. Thus, any move in the nim game can be simulated in the original game: Replacing $G(n)$ with a smaller value $v'$ is equivalent to dividing $n$ by $k$ so that $G(\lfloor n/k\rfloor) = v'$. Thus, we can also simulate a "winning strategy" in the nim game in the original game, if such a strategy exists. And if no such strategy exists, i.e., when $G(A_1)\oplus G(A_2)\oplus\ldots\oplus G(A_N) = 0$, then any move we make will yield a winning position for the next player.

Unfortunately, some moves in the original game actually increase the $G$-value, and such moves don't have equivalents in the nim game! But that's no problem, because we can show that such moves don't matter:

  • If you're in a losing position and perform a move that increases the $G$-value, then the enemy can respond by replacing that new $G$-value with the original one. In other words, if $G(n) = v$ and you move so that the $G$-value becomes $v' > v$, then the enemy can move so it becomes $v$ again. Such a move exists by our definition of $G(n)$. But we're now in a position equivalent to the original one!
  • If you're in a winning position, then there's no point for you in moving so that the $G$-value increases. Simply follow the strategy in the equivalent nim game, and if the opponent performs a move that increases the $G$-value, just respond by replacing it back!

Time Complexity:

$O(N\log A_\max)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester

This question is marked "community wiki".

asked 28 May '16, 16:12

kevinsogo's gravatar image

7★kevinsogo
1.7k583142
accept rate: 11%

edited 06 Jun '16, 13:57

admin's gravatar image

0★admin ♦♦
19.5k348496535


12next »

Short problem analysis for all SNCKQL16 problems: https://aleigorithms.wordpress.com/2016/05/31/snackdown-online-qualifier-2016/

link

answered 01 Jun '16, 01:49

alei's gravatar image

7★alei
1815
accept rate: 0%

Editorialist Excellent explanation.....

link

answered 02 Jun '16, 15:57

chaitanya100's gravatar image

5★chaitanya100
11
accept rate: 0%

Is this classified as an 'easy' problem? I thought it was pretty hard and of course I've never heard of the Sprague-Grundy theorem.

link

answered 31 May '16, 21:45

tony_hager's gravatar image

5★tony_hager
412
accept rate: 0%

Yeah, I think it should be medium.

(31 May '16, 21:51) mightymercado4★

Between Player A and B,if SG Theorum says Player A wins,then does it means that its 100% guaranteed that player A will actually win or the Theorum just tell which player is mostly likely to win?

link

answered 31 May '16, 21:54

shadab_123's gravatar image

2★shadab_123
11
accept rate: 0%

2

It means that if both players play optimally then player A is guaranteed to win.

(01 Jun '16, 00:53) shikharid6★

@shadab_123 If SG theorem says Player A wins, then YES it's 100% guaranteed that player A actually wins! That's why it's "theorem". :)

link

answered 31 May '16, 22:42

disisbig's gravatar image

3★disisbig
11
accept rate: 0%

How can it be possible that code runs perfectly fine on Codechef's IDE but on submitting the same code for the particular problem it shows wrong answer. :/ What might be the reason for not accepting the answer? :)

link

answered 01 Jun '16, 00:55

ankitkumar031's gravatar image

2★ankitkumar031
1
accept rate: 0%

calculating G(n) was the tough part... if u know sprague-Grundy theorem..

link

answered 01 Jun '16, 01:42

shantanu101996's gravatar image

1★shantanu101996
101
accept rate: 0%

Hi I did exactly the short version of the problem. https://www.codechef.com/viewsolution/10227452 I still got WA during contest. Can someone please help? -My first time for any coding competition

link

answered 01 Jun '16, 14:11

salgarkarap's gravatar image

2★salgarkarap
1
accept rate: 0%

can someone explain how grundy numbers are calculated for this problem??

link

answered 01 Jun '16, 15:19

shkishan's gravatar image

2★shkishan
1
accept rate: 0%

edited 01 Jun '16, 15:41

@salgarkarap

  while(a>12){
    a=a/12;
  }

I think it should be: while(a>=12)

link

answered 01 Jun '16, 18:44

tony_hager's gravatar image

5★tony_hager
412
accept rate: 0%

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,029
×3,469
×265
×55
×51
×13

question asked: 28 May '16, 16:12

question was seen: 6,941 times

last updated: 15 Feb, 15:40