hi guys!
i have met a problem in a test and i really dont understand the solution the problem: you are given n(n<=1e5) integers non negative and there are 2 player A , B play in turn (A move first).
in each turn , player of this turn must choose one in n intergers , call x , x must greater than 1 and decrease x by an amount not exceeding half of it.
who can not move will lose. if A and B all play optimally , who will win.
i thought it's greedy , and have tried to construct an strategy , but i couldn't.
i heard that my friend have just change each a[i] to (a[i]-1)/2 if a[i] still odd , and finally , he calculate the xor sum of all a[i] , if the ans is 0 so B win , in contrast A win.
he said that was game theory or nim or grundy .. or somethings.
i tried to find the information of these on google but didn't understand anything.
please can someone help me how to learn these , like what should i read to learn these ;-;
Auto comment: topic has been updated by PDNAM (previous revision, new revision, compare).
Auto comment: topic has been updated by PDNAM (previous revision, new revision, compare).
Auto comment: topic has been updated by PDNAM (previous revision, new revision, compare).
You can refer this blog for why the xor sum works:https://codeforces.me/blog/entry/66040
can you share the problem?
Sprague Grundy basically says that the "equivalent nim number" of state equals the mex of whereever you can go.
For example, if we're at state S, and we could go to any of states A(0), B(1), or C(5), then the nim number of S is 2. Intuitively, at a nim number of 2 you can go to a state with a nim number of 0 or 1 by taking pieces out, or you in this case could go to state C(5), but from C(5) your opponent can take you back to a nim number of 2. (So in essence, nothing happened, but we assume the game is acyclic, so eventually you can't "have both players skip their turn" anymore.)
In this case, 0 is 0, 1 is 1, 2 is 0, 3 is 1, 4 is 2, 5 is 0, etc. (you can calculate this in $$$x \log x$$$ time with some segtrees and stuff. there is probably some pattern if $$$x \le 10^{18}$$$ or something like that but I'm too lazy to check)
If you consider $$$n = 1$$$ (a single integer), then it is a losing state if $$$x = 0,1,3,7,15,31,..$$$ (in the form of $$$2^k - 1$$$) and a winning state otherwise.
If $$$x \le 1$$$ then the game ends. Otherwise let $$$x = 2^k + y$$$ be a winning state where $$$(0 \le y \lt 2^k - 1)$$$ then $$$2^k \le (2^k + y) \lt 2^{k + 1} - 1$$$ then $$$(2^k + y) - (2^k - 1) = y + 1 \le 2^k - 1 \le \frac{x}{2}$$$.
This shows that if $$$x$$$ is in a winning state you can always force your opponent to a losing state, and when you are in a losing state your opponent always ends in a winning state.
To extend this to a general $$$n$$$, we can observe that if there are an odd number of winning subgames then the first player wins (by simply changing it to an even number) otherwise the second player wins (by doing an opposite move to the first player).