PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: fellas
Tester: mridulahi
Editorialist: iceknight1093
DIFFICULTY:
2464
PREREQUISITES:
Observation
PROBLEM:
You’re given two binary strings A and B of length N.
In one move, you can choose a non-empty substring of A and flip all of its values.
Find the number of ways to perform exactly two flips so that the resulting string is B.
EXPLANATION:
Let’s call an index i (1 \leq i \leq N) good if A_i = B_i, and bad otherwise.
Our aim is to make all the indices good after two moves.
Notice that there will be several disjoint groups of bad indices, each forming a contiguous segment.
For example, if
then the bad indices are \{1, 3 ,4, 6\}, forming segments [1], [3, 4], [6].
The important observation here is that a single flip move can reduce the number of such segments by at most one.
Proof
Consider a flip operation that intersects K\geq 2 bad segments.
This flip must also then contain all the good segments that separate these bad segments.
There are K-1 such segments, each of which will be bad after the flip.
So, the number of bad segments increases by at least K-1, and decreases by at most K (each of the bad segments will become good), for a total decrease of at most 1.
In particular, if the number of bad segments is \gt 2, this means we can’t turn A into B using two moves; and the answer is 0.
So, we only need to consider the cases when there are two or fewer segments. Let’s look at each one separately.
Let X denote the number of bad segments.
Case 1: X = 0
In this case, we have A = B before we even start.
So, after the first move, we’ll have a single bad segment - exactly the one we flipped.
The only thing we can do is to flip it back; meaning the second move is uniquely fixed after the first is chosen.
The first move can be anything; and so equals the number of substrings of A, i.e
Case 2: X = 1
There is a single bad segment; let it be [L, R].
Notice that the second move is again uniquely determined: there must be exactly one bad segment remaining, and we’ll flip it to good.
So, let’s try and count the number of first moves that achieve this.
There are several possibilities here:
- We can reduce [L, R] a bit by cutting off some (proper) prefix or suffix, i.e, operate on either [L, i] or [i, R].
There are (R-L) prefixes and (R-L) suffixes to choose from. - We can extend [L, R] to the left by choosing [i, L-1]: there are L-1 choices here.
- Alternately, we can choose [i, R] to delete the original bad segment entirely; for another L-1 choices.
- We can extend [L, R] to the right by choosing [R+1, i]: there are (N-R) choices here.
- Once again, we obtain another (N-R) choices by choosing [L, i] instead; and deleting the original bad segment.
Adding everything together, we have a total of
which is independent of L and R entirely!
Case 3: X = 2
Now, we have two disjoint bad segments.
Yet again, once the first move is fixed the second is uniquely determined; so let’s count the number of first moves that leave a single bad segment remaining.
Let the bad segments be S_1 = [L_1, R_1] and S_2 = [L_2, R_2]. Without loss of generality, let R_1 \lt L_2.
Then, the possible moves are:
- Delete S_1 entirely, then delete S_2 entirely; or vice versa.
- Choose [L_1, L_2-1] and then [R_1+1, R_2]; or vice versa.
- Choose [L_1, R_2] and then [R_1+1, L_2-1]; or vice versa.
These 6 are the only choices, so the answer is always 6 in this case.
So, once X is known the answer is also known in \mathcal{O}(1) time.
Finding X can be done easily in \mathcal{O}(N) time: for example, iterate across the string and count the number of indices i such that A_i \neq B_i but A_{i-1} = B_{i-1}.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
t = input()
difct = 0
for i in range(n):
if s[i] == t[i]: continue
if s[i-1] == t[i-1] or i == 0: difct += 1
if difct == 0: print(n*(n+1)//2)
elif difct == 1: print(2*n - 2)
elif difct == 2: print(6)
else: print(0)