i really wanted to read this but the math part is all gibberish is there any way out with some kinda extension i have noticed this in lot of editorials on codechef
The formatting changed, so a lot of old editorials look like gibberish.
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!
I fixed the formatting.
5 Likes
Hi, thanks for reporting. It should be fixed now.
We are trying to fix most of the incompatibilities between the latex support of the old discuss and new discuss. If you find more such instances, please write to bugs@codechef.com with the Subject “Markdown/Mathjax error on Discuss”.
You can also access old posts in their original rendering on https://discussed.codechef.com. For example you can look at https://discussed.codechef.com/questions/81734/fdivgame-editorial for this particular editorial.
1 Like