2254 C1. Marenol (Easy Version)

Problem Overview

We are given two binary strings, $a$ and $b$, of the same length $N$. We can perform the following operations any number of times:

• Replace 001 with 100 (or vice versa)
• Replace 110 with 011 (or vice versa)

We need to determine if it is possible to transform string $a$ into string $b$.

Why Brute-Force Fails

At first glance, you might be tempted to use a Breadth-First Search (BFS) or a simple simulation to try all possible replacements starting from string $a$ to see if we ever reach string $b$.

However, look at the constraints: the length of the string $N$ can be up to $2 \cdot 10^5$. The number of possible valid string states grows exponentially. Attempting to simulate these operations will immediately result in a Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE).

Whenever a problem asks if one state can be transformed into another under massive constraints, it is a huge red flag that you should stop simulating and start looking for a mathematical invariant.

The "Flip" Abstraction

Let's carefully analyze the operations physically rather than purely logically:

• 001 $\leftrightarrow$ 100: This is exactly a reversal (or flip) of the 3 characters.
• 011 $\leftrightarrow$ 110: This is also exactly a reversal of the 3 characters.

What about the other possible binary strings of length 3?

• 101 reversed is 101
• 010 reversed is 010
• 000 reversed is 000
• 111 reversed is 111

Proving Movement by 2

When you reverse a block of 3 characters, what physically happens?

• The center character (index $i+1$) stays exactly where it is.
• The first character (index $i$) and the third character (index $i+2$) swap places.

Essentially, a character on the edge jumps completely over the center character. This means any character at index $i$ can swap with the character at index $i+2$!

Because a character can only move in steps of 2, it can never change whether it sits in an even slot or an odd slot. However, because swapping index $i$ and $i+2$ is mathematically equivalent to an adjacent swap within the even (or odd) sub-array, we can use these adjacent swaps to generate any permutation (just like Bubble Sort). Therefore, all the characters in even slots can freely shuffle among themselves, and all the characters in odd slots can freely shuffle among themselves.

For string $a$ to be transformable into string $b$, they must satisfy this absolute invariant:

• The exact characters sitting in the even slots of $a$ must match the even slots of $b$.
• The exact characters sitting in the odd slots of $a$ must match the odd slots of $b$.

Pseudocode

Before writing the final code, let's break down the logic step-by-step. Since we only need to verify that the even slots match and the odd slots match, we just need to count the 1s!

1. Create four counters:
   - a_even: to count '1's in even slots of string A
   - a_odd: to count '1's in odd slots of string A
   - b_even: to count '1's in even slots of string B
   - b_odd: to count '1's in odd slots of string B

2. Loop through every character in string A:
   - If the character is a '1':
     - Check its position. If the position is even, add 1 to a_even.
     - If the position is odd, add 1 to a_odd.

3. Do the exact same loop for string B, updating b_even and b_odd.

4. Final Check:
   - If a_even equals b_even AND a_odd equals b_odd, output "YES".
   - Otherwise, output "NO".

Solution Code

#include <iostream>
#include <string>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    
    int a_even_1 = 0, a_odd_1 = 0;
    int b_even_1 = 0, b_odd_1 = 0;
    
    for (int i = 0; i < n; i++) {
        if (a[i] == '1') {
            if (i % 2 == 0) a_even_1++;
            else a_odd_1++;
        }
        if (b[i] == '1') {
            if (i % 2 == 0) b_even_1++;
            else b_odd_1++;
        }
    }
    
    if (a_even_1 == b_even_1 && a_odd_1 == b_odd_1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}