Easy But Easy Game

After each move, the number of ones in the string increases by $1$. So the game is finite.

To solve the problem, let’s make $\frac{n}{2}$ pairs of characters: $(s_1, s_n), (s_2, s_{n-1}), (s_3, s_{n-2}), …, (s_{\frac{n}{2}}, s_{n-\frac{n}{2}+1})$. Each pair of characters should be equal to form a palindrome. Initially, there are $3$ possible types of pairs: $(0, 0)$, $(1, 1)$ and $(0, 1)$ (or $(1, 0)$). If $n$ is odd, there is a single character at the center of the string which is either $0$ or $1$. Let the count of each type of pairs be $cnt_{00}$, $cnt_{11}$ and $cnt_{01}$ respectively and $mid$ be the central character which is $0$ or $1$. The string become a palindrome when $cnt_{01}$ is $0$. There will be no valid move when $cnt_0 < 2$ or $cnt_1 < 1$ where $cnt_0$ and $cnt_1$ are number of zeros and ones in the string respectively.

$cnt_0 = 2\times cnt_{00}+cnt_{01}$ when n is even.

$cnt_0 = 2\times cnt_{00}+cnt_{01}+(1-mid)$ when n is odd.

$cnt_1 = n-cnt_0$

Now, the problem can be solved using dynamic programming where the states are $cnt_{00}$, $cnt_{01}$ and $mid$ (if $n$ is odd). $cnt_{11} = \frac{n}{2}-cnt_{00}-cnt_{01}$ which is extracted from the states. Let’s define each state as a winning state or a losing state. The state from which the current player (who will move from this state) always wins by playing optimally, is a winning state, otherwise, it’s a losing state.

The state where no valid move exists or the string is a palindrome, it’s a losing state. From any state, if we can reach at least one losing state after a single move, then the state is a winning state. Because the current player will choose the move such that the opponent gets a losing state. If all states we can reach from the current state are winning states, then the current state is a losing state. Because, no matter which move the current player chooses, the opponent will get a winning state. If the state of the given string is a winning state, then Alice wins, otherwise, Bob wins.

From each state, we can select two $0$s and one $1$ in all possible ways and visit all reachable states from the current state and decide the current state winning or losing for the current player based on the above rules. For example, the state where $cnt_{00} = 3$, $cnt_{01} = 2$ and $mid=1$, if we select two $0$s from the pair $(0, 0)$ and one $1$ from the pair $(0, 1)$, the new state will be $cnt_{00}=3$, $cnt_{01}=1$ and $mid=1$ as selecting two $0$s from the pair $(0, 0)$ will decrease $cnt_{00}$ by $1$ and selecting one $1$ from the pair $(0, 1)$ will decrease $cnt_{01}$ by 1 and increase $cnt_{00}$ by $1$ at the same time.

For each string of length $n$, there are at most $2\times\frac{n}{2}\times\frac{n}{2}$ different states. The complexity is $O(n^2)$.