RVBS - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given binary strings A and B of the same length.
In one move, you can choose a substring of A that contains exactly one occurrence of 1 and reverse it.
Find the minimum moves to convert A into B; print -1 if it’s not possible to do so.

EXPLANATION:

Our operation doesn’t allow us to change the number of zeros and ones in A.
So, if we want A = B in the end, A and B must have the same number of zeros and ones to begin with too.
If their counts differ, the answer is hence immediately -1.

On the other hand, if A and B have the same number of ones initially, it’s always possible to make them equal (because, for example, the operation allows us to swap adjacent unequal characters; so any rearrangement can be reached.)

So, when A and B have the same number of ones, we only need to focus on finding the minimum number of operations needed.

Each operation, we are able to reverse a substring that contains a single 1.

Note that this means:

  1. We can only move around a single occurrence of 1 at a time; and
  2. Different occurrences of 1 cannot ‘cross’ each other.

Suppose there are k ones in both strings.
Let them be at indices x_1 \lt x_2 \lt\ldots\lt x_k in A and y_1 \lt y_2\lt\ldots\lt y_k in B.
Then, since occurrences of 1 cannot cross each other, the occurrence at index x_i must eventually end up at index y_i.

Since we can only move a single occurrence at a time, a lower bound on the answer is certainly just the count of i such that x_i \ne y_i.

This lower bound is indeed attainable.

Proof

We’ll prove that there always exists a move that fixes a 1 in place.

If k = 0 then no moves are needed.
If k = 1 then there’s only one 1, and the operation allows us to move it around freely; so obviously one operation is enough.
Now assume k \ge 2.

If x_i = y_i for some index i, we can then solve independently for the ranges [1, x_i-1] and [x_i+1, N] of the string.
So, we assume this is not the case for any i.

If x_1 \gt y_1, then everything to the left of index x_1 in A is a 0.
This means we can just reverse the segment [y_1, x_1] in A, and the 1 at x_1 will move to y_1, fixing it in place.
Similarly, if x_k \lt y_k, we can reverse [x_k, y_k] to fix the last 1 in place.

So, the only interesting case is when x_1 \lt y_1 and x_k \gt y_k.
However, in this case there must exist some index i such that x_i \lt y_i but x_{i+1} \gt y_{i+1}.
When this happens, everything from x_i+1 to x_{i+1}-1 contains only zeros in A.
In particular, note that this range contains indices y_i and y_{i+1}.
This allows us to reverse [x_i, y_i] freely, fixing a 1 at index y_i as required.
Now we can once again solve for the left and right of this index independently.

This proves our claim that there’s always a move that fixes a previously-unfixed 1, hence the answer is the number of unfixed ones.

The final solution is hence quite simple:

  • If A and B have different counts of 1, the answer is -1.
    Otherwise, they have equal counts - say k.
  • Let x_1 \lt \ldots\lt x_k be the positions of ones in A.
  • Let y_1 \lt \ldots\lt y_k be the positions of ones in B.
  • The answer is the count of i such that x_i \ne y_i.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()
        
    aone, bone = [], []
    for i in range(n):
        if a[i] == '1': aone.append(i)
        if b[i] == '1': bone.append(i)
    
    if len(aone) != len(bone):
        print(-1)
        continue
    
    diff = 0
    for i in range(len(aone)):
        diff += aone[i] != bone[i]
    print(diff)