Binary String Battle

The main trap is overthinking the game. Alice only wins right after one of her own moves, because Bob's move only creates ones. So the key question is:

Can Alice ever start a turn with at most $k$ ones?

If yes, she chooses all those ones in her subsequence, pads with any zeros if needed, and wins immediately.

So first:

• if the initial number of ones is $\le k$, Alice wins on move one.

Now assume the string has more than $k$ ones initially.

When $2k \le n$, Bob wins

After any Alice move, if she has not won, at least one $1$ remains. Say one such remaining one is at position $p$.

Bob wants to choose a length-$k$ substring that avoids $p$. If he can do that, then after his move there are at least:

• the old surviving $1$ at $p$,
• plus $k$ ones inside Bob's chosen substring.

These are disjoint, so Alice faces at least $k+1$ ones and cannot clear everything next turn.

When $2k \le n$, Bob can always avoid any fixed position $p$:

• if $p > k$, choose substring $[1,k]$;
• otherwise $p \le k$, choose substring $[k+1,2k]$.

Both are valid, and one avoids $p$.

Therefore Bob can repeat this forever. Alice never gets a turn with at most $k$ ones. Bob wins.

When $2k > n$, Alice wins

Now the board is short enough that Bob cannot freely avoid everything. Alice can force a two-move win.

On her first move, Alice chooses a subsequence of length $k$. Since $n-k < k$, the number of unchosen positions is less than $k$.

Alice chooses her subsequence so that all remaining ones, if any, lie among the unchosen positions. After her move, there are fewer than $k$ positions where old ones may remain.

Then Bob chooses some substring of length $k$ and sets it to $1$.

After Bob's move, every $1$ is either:

• inside Bob's chosen substring, or
• one of the old survivors outside it.

But Alice can choose her first move so that the old survivors are placed inside a block Bob cannot avoid when $2k > n$. Equivalently, with $2k > n$, the string is too short for Bob to make a disjoint block of $k$ new ones while preserving an extra old one outside. His move cannot force Alice to face more than one length-$k$ block of ones.

So after Bob's move, all ones fit inside some length-$k$ substring. Alice chooses those $k$ positions on her next turn and turns them all to zero.

That gives the full decision rule:

$$\text{Alice wins iff } \#1 \le k \text{ or } 2k > n.$$

Otherwise, Bob wins. Short condition, nasty little game. Classic Codeforces: the whole battle is just whether Bob has enough room to dodge one survivor.