Binary Array Game

We need decide who can force the final single value. Alice wants final 0, Bob wants final 1.

The move is:

$$[a_l,\ldots,a_r] \to 1 - \min(a_l,\ldots,a_r)$$

Since the array is binary:

• if the chosen segment is all 1, it becomes 0;
• if the chosen segment contains at least one 0, it becomes 1.

That’s the whole game. Everything else is just not getting baited by the notation.

Key Observation

The final value becomes 0 only if the final chosen segment is all 1s.

So if a player ever receives an array consisting only of 1s and length at least $2$, the only sensible ending is to choose the whole array and make the final number 0. That is good for Alice, no matter whose turn it is.

This means Alice has a very direct plan: on her first move, try to turn the array into all 1s. Then Bob is stuck: if the array length is more than $1$, every legal full-array ending gives 0; if the array length is already $1$, it is 1, which would be bad for Alice, so she must avoid choosing the entire array unless it already gives 0.

When can Alice make the whole remaining array all 1s?

A move turns the chosen segment into 1 if the chosen segment contains at least one 0.

All elements outside the chosen segment stay unchanged. Therefore, after Alice's move, the whole array is all 1s exactly when:

1. her chosen segment contains every zero in the array, and
2. everything outside that segment is already 1, and
3. she does not choose the whole array if the segment contains a zero, because that would immediately end at 1, handing Bob the win like a gift-wrapped disaster.

Let $L$ be the position of the first zero, and $R$ be the position of the last zero.

Alice can cover all zeros by choosing the segment $[L,R]$. This segment becomes 1. The outside parts are all 1s by definition of first/last zero.

Now the important bit: this is a legal winning first move only if $[L,R]$ is not the whole array. That happens exactly when:

• $L > 1$, meaning there is a 1 before the first zero, or
• $R < n$, meaning there is a 1 after the last zero.

So Alice wins if there is a 1 outside the first-zero-to-last-zero interval.

There is also the special case with no zeros. If the array is all 1s, Alice chooses the whole array immediately and gets final 0, so Alice wins.

What if zeros touch both ends?

Now suppose the array starts with 0 and ends with 0. Then $L=1$ and $R=n$.

Alice cannot choose a proper segment containing all zeros, because all zeros span the whole array. Her options are:

• choose the whole array, which contains a zero, so it becomes final 1; Bob wins immediately;
• choose a proper segment, which leaves at least one original endpoint zero outside the segment, so the resulting array still contains a zero.

After any non-losing Alice move, Bob gets an array that still has at least one zero. Bob can now simply choose the entire current array. Since it contains a zero, it becomes final 1, and Bob wins.

So if the first and last elements are both 0, Bob wins. Brutal, but fair.

Final Rule

Alice wins iff:

• the array has no zeros, or
• a[0] == 1, or
• a[n-1] == 1.

Otherwise Bob wins.

Since if there is at least one zero and both ends are zero, the first zero is at the start and the last zero is at the end, so Bob has the forced win.

The implementation is tiny:

• read $n$ and the array;
• check whether there is any zero;
• print Alice if all ones or either endpoint is 1;
• otherwise print Bob.

Complexity: $O(n)$ per test case, memory $O(1)$ besides the input array. The constraints are small enough that even a potato could run this, but we still write it cleanly.