PROBLEM LINK:Author: ??? PREREQUISITES:Game theory PROBLEM:A game is played on a string of length $n$ consisting of QUICK EXPLANATION:Replace all EXPLANATION:If you didn't catch the simple solution, you might have instead tried to bruteforce all instances of the problem for small $n$, and found that there is always a winning move flipping just the leftmost First, replace all An example of a valid move is to replace a $1$ with a $0$, and then replacing some number of zeroes to the right of it with a $1$. Since this is a binary number, the place value of the $1$ is $2^k$ for some $k$, and the $0$s to the right of it have place values $2^{k1}, 2^{k2}, \ldots, 2^m$ for some $m$. A move in effect decreases the value of our number by $$2^k  2^{k1}  2^{k2}  2^{k3}  \ldots  2^m$$ which is just equal to $2^m$. (Why?) Thus, a valid move consists of subtracting a number $2^m \le X$. It can also be seen that subtracting any power of two $\le X$ constitutes a valid move. The question is now: which numbers $X$ are winning positions for the first player? A losing position is a position such that every move results in a winning position. A winning position is a position such that there is a move resulting in a losing position. We must find a property that all winning positions, and only winning positions, have. Such a property must satisfy the following:
It can be seen that the following property satisfies both requirements: $X$ is not a multiple of $3$ Obviously $X = 0$ doesn't have this property (because it is a multiple of $3$). Now, if $X$ is a multiple of $3$, then subtracting a power of two from it results in a number that is not a multiple by $3$, because no power of two is a multiple of $3$. But if $X$ is not a multiple of $3$, then there are two cases:
In both cases, the resulting number is a multiple of $3$. Thus, the property satisfies all requirements! So the solution is simply: If $X$ is divisible by $3$, then the second player wins. Otherwise, the first player wins. Finally, checking whether $X$ is a multiple of $3$ can be done with the Horner method modulo $3$: (here we write
Time Complexity:$O(n)$ AUTHOR'S AND TESTER'S SOLUTIONS:[setter][333] [333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server. [444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server. [555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
This question is marked "community wiki".
asked 26 Jan '16, 07:18
