ADJOR - Editorialea

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You’re given a binary array A.
In one move, you can choose an index i (1 \lt i \lt N) and set A_i to A_{i-1} \mid A_{i+1}.
Is it possible to convert A into B?

EXPLANATION:

Let’s make a couple of observations.
First off, it’s impossible to change the first and last characters of A using our operation.
So, if A_1 \neq B_1 or A_N \neq B_N, it’s definitely impossible to make A equal to B.

Now, let’s look at the operation itself.
We essentially take three consecutive elements, and set the middle one to the bitwise OR of the other two.
It’s not hard to see that there are only four “useful” moves, i.e. moves that change anything at all. These are:

  • [0, 0, 1] \to [0, 1, 1]
  • [1, 0, 0] \to [1, 1, 0]
  • [1, 0, 1] \to [1, 1, 1]
  • [0, 1, 0] \to [0, 0, 0]

All other moves will leave the middle element unchanged and so there’s no need to consider them.

Looking at these operations, we can observe the following:

  1. The only way to convert a 1 to a 0 is via the move [0, 1, 0] \to [0, 0, 0].
  2. As a result of this, if there are two adjacent ones in A, neither of them can ever be converted to a 0 again.
    This is because converting one of them to a 0 requires the other one to already be 0 (and vice versa).
  3. Further, the moves that change zeros to ones all result in the new 1 being adjacent to another 1.
    This means, once an index is converted to a 1, it can’t become a 0 again.
  4. A move that converts a 0 into a 1, is essentially just “propagating” the 1.
    That is, one way to think of the move is that we choose a 1 in A, and then set one of its neighbors to 1.

Let’s now use these observations to decide which moves are needed.

First, consider an index i such that A_i = 1 and B_i = 0.
This index needs to be turned into 0, which as noted earlier is only possible if A_{i-1} = A_{i+1} = 0 already: if either adjacent element is 1 then we’re in trouble.

So, every element that must be turned from 1 to 0, must be surrounded by zeros on both sides.
If this doesn’t hold for any index, it’s definitely impossible to turn A into B; so we now only need to deal with strings where this does hold.

Suppose we just perform all the necessary moves on A which turn ones into zeros.
This means we’re now left with a state where:

  • If B_i = 0 then A_i = 0 for sure.
  • If B_i = 1 then A_i might be either 0 or 1.

So, we only need to perform moves that convert zeros to ones.
As noted earlier, the only thing we can do is “propagate” existing occurrences of 1.
Further, since ones can’t be turned back into zeros, if B_i = 0 we definitely can’t set A_i = 1 using the operation.

This means that the occurrences of 0 in B are functionally “blocking” the propagation of ones.
So, B essentially splits up into several blocks of ones; where the blocks are separated by zeros and each block must be solved independently.
For example, if B = [1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0] then we have three blocks:

  • The first one of length 2, containing indices 1 and 2.
  • The second one of length 1, containing index 4.
  • The third one of length 3, containing indices 8, 9, 10.

Looking at some block [L, R] of ones in B,

  • If there’s an occurrence of 1 in the range [L, R] of A, this 1 can just be propagated to cover the entire range [L, R].
  • If there’s no 1 in range [L, R] of A, then it’s impossible to satisfy this block.

In summary, A can be converted to B if and only if the following conditions all hold:

  1. A_1 = B_1 and A_N = B_N.
  2. For 1 \lt i \lt N, if A_i = 1 and B_i = 0 then A_{i-1} = A_{i+1} = 0 must hold.
  3. For each maximal block of ones in B, the corresponding segment in A should contain at least one 1.

All three conditions are easy to check for in linear time.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++){
        cin >> b[i];
    }
    
    if (a[1] != b[1] || a[n] != b[n]){
        cout << "No\n";
        return;
    }
    
    for (int i = 1; i <= n; i++){
        if (a[i] == 1 && b[i] == 0){
            if (a[i - 1] == 1 || a[i + 1] == 1){
                cout << "No\n";
                return;
            }
            a[i] = 0;
        }
    }
    
    for (int i = 1; i <= n; i++) if (b[i] == 1){
        int r = i;
        while (r + 1 <= n && b[r + 1] == b[i]){
            r++;
        }
        
        int cnt = 0;
        for (int j = i; j <= r; j++){
            cnt += a[j] == 1;
        }
        
        if (cnt == 0){
            cout << "No\n";
            return;
        }
        
        if ((i > 1 && a[i - 1] == 1) || (r < n && a[r + 1] == 1)){
            cout << "No\n";
            return;
        }
        
        i = r;
    }
    
    cout << "Yes\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (PyPy3) 
def solve(a, b):
    if a[0] != b[0] or a[-1] != b[-1]: return 'No'
    
    for i in range(1, n-1):
        if a[i] == 1 and b[i] == 0:
            if a[i-1] == 1 or a[i+1] == 1: return 'No'
    
    for i in range(n):
        if b[i] == 1 and (i == 0 or b[i-1] == 0):
            j, ct = i, 0
            while j < n and b[j] == 1:
                ct += a[j]
                j += 1
            if ct == 0: return 'No'
    return 'Yes'

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(solve(a, b))
1 Like