ATOB1 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given two binary strings A and B.
You can modify A as follows:

  • Choose L and R (1 \le L \le R \le N) and flip all the elements A_L, A_{L+1}, \ldots, A_R between 0 and 1.
  • This has a cost of 1 if A_L = A_R and 0 otherwise.

Find the minimum cost of a sequence of moves that transforms A into B.

EXPLANATION:

With our aim being to minimize the cost, clearly we should try to use cost 0 moves as much as possible.
Luckily, they turn out to be quite powerful!

A move (L, R) has a cost of 0 if and only if A_L \ne A_R, meaning one of A_L and A_R equals 0 and the other equals 1.
This means a cost 0 move exists only when A contains both 0's and 1's.
Further, since the move flips everything in the range [L, R], after the move we’ll still have both a 0 and a 1.

So, for now let’s work with only strings that have both 0's and 1's (which means we exclude exactly two strings: one being all zeros and the other being all ones.)

As it turns out, if A contains both 0's and 1's, it’s possible to convert it to any other string containing both 0's and 1's using only cost-0 moves!

A quick sketch of why is to note the following:

  1. Cost 0 moves allow us to swap two adjacent characters of the string.
    So, we’re able to freely rearrange the characters of a string with no additional cost.
  2. Using this, it’s possible to sort the string in ascending order, i.e. being it to 00\ldots 0011\ldots 11.
  3. From this state, we can manipulate the number of zeros and ones in the string - for example choose a substring of the form 0111\ldots to increase the number of zeros; or \ldots 0001 to increase the number of ones.
  4. Once we have the appropriate number of zeros and ones, we can once again use adjacent swaps to rearrange them as we like to reach the target string.

A full proof can be found in the editorial to the harder version, which explicitly constructs a sequence of moves.

With the above idea, we can now easily complete the solve process.
Observe that if A contains all zeros, then a single cost-1 move can transform it to either a string containing both zeros and ones (choose L = R), or to a string containing all ones (choose L = 1 and R = N.)

So,

  • If A contains all zeros,
    • If B also contains all zeros, the answer is 0.
    • Otherwise, the answer is 1.
  • Similarly, if A contains all ones, the answer is 0 if B also contains all ones and 1 otherwise.
  • Finally, if A contains both zeros and ones,
    • If B contains either all zeros or all ones, the answer is 1.
    • Otherwise, the answer is 0.

A simpler way of looking at this is as follows.
Call a string type 1 if it contains only zeros, type 2 if it contains only ones, and type 3 if it contains both zeros and ones.
Then, the answer is 0 if A and B have the same type; and the answer is 1 otherwise.

This makes for an easy \mathcal{O}(N) check.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string a, b; cin >> a >> b;

        auto type = [] (string s) {
            int res = 0;
            for (auto c : s) {
                if (c == '0') res |= 1;
                if (c == '1') res |= 2;
            }
            return res;
        };

        if (type(a) != type(b)) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}