We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
O(1) solution, passes all test cases. I'm pretty sure this beats the editorial solution, assuming that for N <= 1 billion, we can find floor(lg N) in O(1) time (python3 has a builtin "frexp" function that does this). For arbitrary N, there's a O(lg lg N) method to obtain floor(lg N), so that would be the complexity if we allowed arbitrarily large integers.
Explanation: first examine the nimber of every pile using the maximum excludant, e.g. smallest non-negative integer that is not equal to the nimber of any positions reachable from current position. It is easy to see that a pile of n stones has nimber L(n)=1+floor(lg n). Note also L(0)=0 by definition. The first few are
N=0123456789101112L=0122333344444
By the Sprague-Grundy theorem, cumulative XOR, which we denote X(N), of all nimbers tells you whether first person wins: if X(N)=0, first person loses, and otherwise first person wins. By inspection, we see that for any n>=0, X(2n+1)=1 and X(2n)=1^L(2n). This is always nonzero, so the first player can always win.
In order to win, the first player must choose some pile m and change the nimber of that pile from L(m) to X^L(m). For N odd, just choose m=1, take one stone, and that's the answer. For N even, it's trickier. The minimum stones taken corresponds (but is not equal) to the minimum positive value of L(m)-X(N)^L(m). By inspection, this can be chosen by setting L(m)=y=2**floor(lg X(N)). The minimum value of m that gives this nimber is m=2**(y-1). We need to remove the minimum number of stones from this pile of m so that the new nimber is X(N)^y. If the new nimber is one less than the old nimber, then there's only one option: remove half of m. Otherwise, we go down to the largest possible pile whose nimber is X(N)^y, which is given by 2**(X(N)^y)-1.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
A stones game
You are viewing a single comment's thread. Return to all comments →
O(1) solution, passes all test cases. I'm pretty sure this beats the editorial solution, assuming that for N <= 1 billion, we can find floor(lg N) in O(1) time (python3 has a builtin "frexp" function that does this). For arbitrary N, there's a O(lg lg N) method to obtain floor(lg N), so that would be the complexity if we allowed arbitrarily large integers.
Explanation: first examine the nimber of every pile using the maximum excludant, e.g. smallest non-negative integer that is not equal to the nimber of any positions reachable from current position. It is easy to see that a pile of n stones has nimber L(n)=1+floor(lg n). Note also L(0)=0 by definition. The first few are
By the Sprague-Grundy theorem, cumulative XOR, which we denote X(N), of all nimbers tells you whether first person wins: if X(N)=0, first person loses, and otherwise first person wins. By inspection, we see that for any n>=0, X(2n+1)=1 and X(2n)=1^L(2n). This is always nonzero, so the first player can always win.
In order to win, the first player must choose some pile m and change the nimber of that pile from L(m) to X^L(m). For N odd, just choose m=1, take one stone, and that's the answer. For N even, it's trickier. The minimum stones taken corresponds (but is not equal) to the minimum positive value of L(m)-X(N)^L(m). By inspection, this can be chosen by setting L(m)=y=2**floor(lg X(N)). The minimum value of m that gives this nimber is m=2**(y-1). We need to remove the minimum number of stones from this pile of m so that the new nimber is X(N)^y. If the new nimber is one less than the old nimber, then there's only one option: remove half of m. Otherwise, we go down to the largest possible pile whose nimber is X(N)^y, which is given by 2**(X(N)^y)-1.