PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Testers: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
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)