ANDOR1 - 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 of the same length.
In one move you can:

  • Choose an index i (1 \le i \lt N), and
  • Replace both A_i and A_{i+1} by either A_i\ \mid\ A_{i+1} or A_i\ \&\ A_{i+1}.

Decide if it’s possible to make A = B or not.

EXPLANATION:

Let’s define a block to be a maximal segment of equal characters in a binary string.
For example, the string \texttt{001011100} has five blocks: \{00, 1, 0, 111, 00\}.
Note that blocks always alternate between containing zeros and containing ones.

We now analyze how performing an operation changes the blocks of A.
Clearly, if A_i = A_{i+1} then performing an operation just leaves both values unchanged; so this is pointless.
Thus, the only useful operations are when A_i \ne A_{i+1}.
In this case, we have one 0 and one 1, so we can either set both values to 0 by using bitwise AND, or both values to 1 by using bitwise OR. Note that we’re thus overwriting exactly one of A_i and A_{i+1} with the other one.

Now, since A_i \ne A_{i+1}, observe that indices i and i+1 are both borders of their respective blocks.
Since we’re overwriting exactly one of the values, we’re really just moving block borders slightly: for example, overwriting A_i means we shrink the block ending at index i and expand the block starting at i+1.

In particular, observe that:

  • An operation only moves block borders, and hence it cannot create new blocks.
  • It is however possible to reduce the number of blocks: if we shrink a size-1 block, it will disappear, reducing the block count.

Let ct_A denote the number of blocks in A initially, and ct_B denote the number of blocks in B.

As we noted, it’s impossible to increase ct_A via operations.
So, if ct_A \lt ct_B it’s definitely impossible to make A = B (since they must obviously have the same block count in the end.)

This leaves us with the cases of ct_A = ct_B and ct_A \gt ct_B.

Let’s deal with ct_A = ct_B first.
Since the block counts are equal, we are not allowed to delete any blocks.
In particular, observe that this means we are not able to change the first character of A; since the only way to change it is by deleting its block entirely.
So, in this case, if A_1 \ne B_1 then it’s impossible to make A equal to B.

However, if A_1 = B_1 then it’s always possible.

Proof

Without loss of generality, suppose A_1 = 0, i.e. A starts with a 0 (and hence so does B.)

First, do the following repeatedly:

  • Let i be the smallest index such that A_i \ne A_{i+1}.
  • If i \gt 1, perform an operation with i that overwrites A_i to become A_{i+1}.
    If i = 1, stop the process.

At the end of this process, we’ll have A_1 = 0 and A_2 = 1, i.e. the first block consists of a single element.

Now, repeat the same process but starting from index 2 instead, i.e. repeatedly pick the smallest i\ge 2 such that A_i \ne A_{i+1} and operate on it if i \gt 2.
At the end of this, we’ll have A_2 = 1 and A_3 = 0.
Then repeat for indices 3, 4, 5, \ldots in order as long as possible.

At the end of this, A will look like 010101\ldots010000\ldots 000 or 010101\ldots010111\ldots 111 depending on whether it ends with 0 or 1 (which we haven’t changed.)

From this state, it’s quite easy to turn it into B by performing a similar process but from the back instead.
That is, repeatedly shrink the last block till it’s equal to B’s last block; then repeatedly shrink the second-last of A till it equals B’s second-last block, and so on till eventually A and B are equal.

Finally, we have the case of ct_A \gt ct_B.
In this case, it’s always possible to make A equal to B.
This is because, in the case of ct_A = ct_B the only issue we had was when the first characters of A and B were different.
However, when ct_A \gt ct_B we have freedom to delete the first block if needed (by expanding the second block), which will change the value of A_1.
After making A_1 = B_1, we can then simply keep deleting the last block (by expanding the second-last block) till we reach a state where the block counts are equal, after which we know from earlier that it’s possible.

The tl;dr is:

  • If ct_A \lt ct_B, the answer is No.
  • If ct_A \gt ct_B, the answer is Yes.
  • If ct_A = ct_B, the answer is Yes if A_1 =B_1 and No otherwise.

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;

        int ablk = 1, bblk = 1;
        for (int i = 1; i < n; ++i) {
            ablk += a[i] != a[i-1];
            bblk += b[i] != b[i-1];
        }

        if (ablk > bblk or (ablk == bblk and a[0] == b[0])) cout << "Yes\n";
        else cout << "No\n";
    }
}
1 Like
ANDOR2 - Editorial
2

Good explanation. Thank you!