# DLSB - Editorial

Author: pols_agyi_pols
Testers: kingmessi
Editorialist: iceknight1093

TBD

None

# PROBLEM:

Alice and Bob play a game on a binary string S. On their turn, a player removes some substring whose characters are equal. Alice moves first.
Alice wants to remove every 1 from the string, while Bob wants to remove every 0.

Before the game starts, Bob can modify individual positions of S.
Whatâ€™s the minimum number of modifications he needs to ensure he wins?

# EXPLANATION:

Alice wants to remove every 1, while Bob wants to remove every 0.
Clearly, on her turn Alice will remove some block of 1's, and Bob will remove some block of 0's.

Suppose S contains x blocks of 1's and y blocks of 0's.
For example, if S = \texttt{10011001}, we have x = 3 and y = 2.
Note that since blocks alternate between 0 and 1, weâ€™ll have |x-y| \leq 1.
In particular,

• x = y means that the starting and ending blocks are of different types.
• x = y+1 or y = x+1 mean that the starting and ending blocks are of the same type.

Now, observe that:

• If x \leq y, Alice wins.
This is because, in this case S must either start with or end with a 1.
So, Alice can just delete the boundary block of 1's, which reduces x by 1 and doesnâ€™t change y.
• If x \gt y, Bob wins.
This is because, no matter what Alice does, x cannot be reduced by more than 1.
So, when the turn passes to Bob, itâ€™ll be the first case from his perspective; and he thus has a winning strategy.

Since we want Bob to win, we need to find the minimum number of flips that will result in x\gt y, that is, there being more blocks of 1's then 0's.
However, since we noted earlier that |x-y| \leq 1, this really means weâ€™re forced to ensure that x = y+1.
This is only possible if and only if S both starts and ends with a 1.

So, the solution is to simply flip the first and/or last character of S if theyâ€™re 0.
N = 1 is an edge case, since the first and last characters are the same (and so only one swap is needed, if at all).

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input().strip()

if n == 1:
print(1 - int(s[0]))
continue

ans = (s[0] == '0') + (s[-1] == '0')
print(ans)

1 Like

" Clearly, on her turn Alice will remove some block of 111â€™s, and Bob will remove some block of 000â€™s."
Why ? Can we have a proof for this please ?

Hi, I have some confusions,
if S = 10011001 we have x = 3 and y = 2, which means x = groups of 1s and y = groups of 0s.
but you have mentoned if x<= y, aloce wins as S must either start or end with a 1, but for â€ś0011001100â€ť, x=2 and y=3 (x<y) but string starts and ends with 0s.