Recently a friend and I have been discussing a problem we saw somewhere:
Alice and Bob are playing a game where they have n piles of stones. In one move one can pick a particular pile and remove all other. Then they have to split the chosen pile into exactly n piles with at least one stone each. One who doesn't have a move loses.
The constraint were: n <= 1e6, a[i] <= 1e18,
Initially I thought that the setup is very similar to a Sprague-Grundy problem. I can consider calculating the grundy values of a few number, and try finding a pattern relating to n. First of all calculating the grundy values are difficult to find in itself. I have to consider the transition: splitting the number into all possible multisets of size n, xoring the grundy values of the individual elements together and taking the mex amongst all possible multisets. This is in and of itself is a huge task to accomplish. However let's say we do it somehow. But I don't think these are the correct grundy values for the problem. Picking a pile is not independent of the other piles. Hence xoring is wrong. I have calculated the grundy values for a problem in which I split a pile into n piles. One who cannot have a valid move loses.
I wonder if this is even solvable by the Sprague-Grundy theorem? Can anyone please help me solve this problem? I welcome people to comment why or why not my initial setup for solving it by grundy values is correct or not.
After writing a brute force, it is found that if f(x) represents a first player playing on x, lose is 1 and win is 0.
$$$f(x)=[1\le x\%(n+n^2)\le n]$$$.
It's easy to prove this by induction.
Can you elaborate on what x is? And what your overall algorithm is?