A Bit Odd

The tempting wrong idea is to count the total inversions and check odd/even. Nope. The sample 0100 has $2$ inversions, but Alice still wins. So the total count is wearing a fake mustache here.

Call a string balanced if:

• every 0 has an even number of 1s before it;
• every 1 has an even number of 0s after it.

The whole answer is:

• balanced string -> Bob
• otherwise -> Alice

Now let’s justify that instead of just vibe-coding it.

Terminal Positions

A player cannot move iff there is no subsequence with an odd number of inversions.

If the string contains any 1 before any later 0, then choosing just those two characters gives subsequence 10, which has exactly one inversion. So a move exists.

Therefore terminal strings are exactly sorted binary strings:

$0^*1^*$

Why An Unbalanced String Is Winning

Suppose there is a 0 at position $p$ with an odd number of 1s before it.

We will leave a sorted string. Put a cut at $p$. To make the remaining string sorted, delete all 1s on the left of the cut and all 0s on the right of the cut. The 0 at $p$ is optional: either keep it or delete it.

If we switch whether this 0 is deleted, the inversion parity of the deleted subsequence changes by the number of deleted 1s before it. But all 1s before it are deleted, and that number is odd. So the parity flips.

That means one of the two choices deletes a subsequence with odd inversion count. The remainder is sorted, so Alice wins instantly.

The argument is symmetric if there is a 1 with an odd number of 0s after it. Put the cut just before that 1; all those 0s after it are forced deleted, and choosing whether to delete this 1 flips the parity by an odd amount.

So if the string is not balanced, Alice has a one-move kill. Brutal, but fair.

Why A Balanced String Is Losing

Now assume the current string $s$ is balanced.

We prove Alice cannot move to another balanced string. That is enough, because every unbalanced string is immediately winning for the next player.

Let Alice delete subsequence $D$ and leave subsequence $R$. Suppose, for contradiction, that $R$ is also balanced.

Count inversions inside $D$ modulo $2$ by looking at deleted 0s:

For each deleted 0, the number of total 1s before it in $s$ is even, because $s$ is balanced. So:

deleted ones before it has the same parity as kept ones before it.

Therefore, the inversion parity of $D$ equals the parity of the number of cross pairs:

kept 1 before deleted 0.

Now count those same cross pairs by kept 1s. For every kept 1, the total number of 0s after it in $s$ is even, since $s$ is balanced. Also, because $R$ is balanced, the number of kept 0s after it is even. Thus the number of deleted 0s after it is also even.

So every kept 1 contributes an even number of cross pairs. The total cross-pair count is even, hence the deleted subsequence $D$ has an even number of inversions.

But Alice’s move must delete a subsequence with an odd number of inversions. Contradiction.

So from a balanced string, every legal move leaves an unbalanced string. Then the next player immediately deletes to a terminal sorted string. Therefore balanced positions are losing.

Implementation

We only need parity.

First scan left to right:

• maintain parity of number of 1s seen;
• if we see 0 while this parity is odd, Alice wins.

Then scan right to left:

• maintain parity of number of 0s seen;
• if we see 1 while this parity is odd, Alice wins.

If neither scan finds a violation, print Bob.

Complexity: $O(n)$ per test case, $O(1)$ extra memory.