Vertical Exchange (Editorial)

Solution

For every position $i$, consider the value

c_i = (a_i - \texttt{'0'}) + (b_i - \texttt{'0'}).

Thus, c_i is the number of ones in the $i$-th column, so c_i can only be $0$, $1$, or $2$.

Notice that swapping a_i and b_i does not change c_i.

Suppose that it is possible to make both strings non-decreasing.

Then, for every i < j, we have a_i \le a_j and b_i \le b_j.

Therefore, a_i + b_i \le a_j + b_j.

So the sequence c_1,c_2,\ldots,c_n must also be non-decreasing.

Now let us prove that this condition is sufficient.

If the sequence $c$ is non-decreasing, since every c_i belongs to \{0,1,2\}, it has the following form: 0,0,\ldots,0,\ 1,1,\ldots,1,\ 2,2,\ldots,2.

A column with c_i=0 is necessarily \begin{matrix} 0\\ 0 \end{matrix},

and a column with c_i=2 is necessarily \begin{matrix} 1\\ 1 \end{matrix}.

For every column with c_i=1, its elements are either $(0,1)$ or $(1,0)$. If necessary, we swap them so that the column becomes \begin{matrix} 0\\ 1 \end{matrix}.

After doing this for all columns with sum $1$, the first string consists of some zeros followed by some ones, and the second string also consists of some zeros followed by some ones.

Hence, both strings are non-decreasing.

Therefore, the answer is YES if and only if c_1 \le c_2 \le \ldots \le c_n.

It remains only to check every pair of adjacent positions.

The time complexity of the solution is $O(n)$.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string a, b;
    cin >> a >> b;

    for (int i = 0; i + 1 < n; i++) {
        int x = (a[i] - '0') + (b[i] - '0');
        int y = (a[i + 1] - '0') + (b[i + 1] - '0');

        if (x > y) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";

    return 0;
}