PROBLEM LINK:Author: Kevin Atienza DIFFICULTY:Easy PREREQUISITES:Game theory, Combinatorial game theory, SpragueGrundy 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 SpragueGrundy 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 ( EXPLANATION:This is an example of an impartial game played under normal play condition, so the SpragueGrundy theorem applies. The SpragueGrundy 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 SpragueGrundy 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:
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}{rrrrrrrrrrrrrrrr}
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:
But is this true in general? And how do we prove that? Well, it turns out that you can easily prove this by induction:
So now we have another way to compute $G(n)$:
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)$:
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 nimIf you're unfamiliar with SpragueGrundy 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 wellknown 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.
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:
Time Complexity:$O(N\log A_\max)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 28 May '16, 16:12

Short problem analysis for all SNCKQL16 problems: https://aleigorithms.wordpress.com/2016/05/31/snackdownonlinequalifier2016/ answered 01 Jun '16, 01:49

Is this classified as an 'easy' problem? I thought it was pretty hard and of course I've never heard of the SpragueGrundy theorem. answered 31 May '16, 21:45

@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". :) answered 31 May '16, 22:42

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? :) answered 01 Jun '16, 00:55

calculating G(n) was the tough part... if u know spragueGrundy theorem.. answered 01 Jun '16, 01:42

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 answered 01 Jun '16, 14:11

can someone explain how grundy numbers are calculated for this problem?? answered 01 Jun '16, 15:19

answered 01 Jun '16, 18:44
