PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: watoac2001
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have a binary string S of length N.
In one move, you can choose some suffix of it and flip every character in this suffix.
Find the minimum number of moves needed to turn S into an alternating string.
EXPLANATION:
There are only two alternating strings: 0101010\ldots and 101010\ldots
Let’s fix one of them, say T=0101\ldots and try to see how many moves we need to turn S into it.
As an initial observation, notice that the order we perform moves in doesn’t matter at all - only which suffixes we choose to flip.
Further, flipping some suffix twice is the same as not flipping it at all; so each suffix needs to be flipped at most once.
Thus, we only need to decide which subset of suffixes to flip.
Let’s look at the strings S and T.
if S_1 \neq T_1, we’re forced to flip the suffix starting at 1 - that’s the only way to change S_1, after all.
But, if S_1 = T_1, we’re forced to not flip the suffix from 1, to ensure that this equality holds.
So, our choice of what to do with the first suffix is uniquely determined.
Now, let’s look at S_2 and T_2.
S_2 might’ve been flipped by the previous operation (if we chose to do it).
Notice that the same situation applies again: if S_2\neq T_2 now, we’re forced to flip it; otherwise we’re forced to not flip it.
In fact, this applies to every index i: if the actions on suffixes 1 to i-1 have been decided, the action on suffix i will be uniquely decided too, since that’s the only way we have left to affect S_i.
Applying this idea directly gives a solution in \mathcal{O}(N^2): for each i from 1 to N, decide whether it needs to be flipped or not.
If it does need to be flipped, perform the flip on each index \geq i in linear time.
This is too slow, however.
To optimize it, notice that when we’re at index i, we only care about the value of S_i after all previous flips have been made, since that’s all the information we need at this stage.
This value doesn’t really depend on which flips were made: it only depends on the number of flips (if the count is even, S_i will remain unchanged from what it originally was; otherwise it’ll flip).
So, instead of directly simulating the flips, simply store their count done so far; which gives a linear-time algorithm!
To finish, compute the number of flips needed to turn S into both 0101\ldots and 1010\ldots, and take the minimum of them.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
def calc(s, t):
n = len(s)
ans, flip = 0, 0
for i in range(n):
req = s[i] != t[i]
if req != flip:
flip ^= 1
ans += 1
return ans
zeroone = '01'*(10**5)
onezero = '10'*(10**5)
for _ in range(int(input())):
n = int(input())
s = input().strip()
print(min(calc(s, zeroone[:n]), calc(s, onezero[:n])))