Вертикальний обмін (Розбір)

Розв'язання

Для кожної позиції $i$ розглянемо значення c_i = (a_i - \texttt{'0'})+ (b_i - \texttt{'0'}).

Таким чином, c_i — це кількість одиниць у $i$-му стовпчику, тому c_i може дорівнювати лише $0$, $1$ або $2$.

Зауважимо, що перестановка a_i та b_i місцями не змінює значення c_i.

Припустимо, що можна зробити обидва рядки неспадними.

Тоді для кожних i < j маємо a_i \le a_j та b_i \le b_j.

Отже, a_i + b_i \le a_j + b_j.

Тому послідовність c_1,c_2,\ldots,c_n також повинна бути неспадною.

Тепер доведемо, що цієї умови достатньо.

Якщо послідовність $c$ неспадна, то, оскільки кожне c_i належить множині \{0,1,2\}, вона має такий вигляд: 0,0,\ldots,0,\ 1,1,\ldots,1,\ 2,2,\ldots,2.

Стовпчик з c_i=0 обов'язково має вигляд \begin{matrix} 0\\ 0 \end{matrix},

а стовпчик з c_i=2 обов'язково має вигляд \begin{matrix} 1\\ 1 \end{matrix}.

Для кожного стовпчика з c_i=1 його елементи мають вигляд або $(0,1)$, або $(1,0)$. За потреби поміняємо їх місцями так, щоб стовпчик мав вигляд \begin{matrix} 0\\ 1 \end{matrix}.

Після цього для всіх стовпчиків із сумою $1$ перший рядок складатиметься з деякої кількості нулів, після яких ідуть одиниці, і другий рядок також складатиметься з деякої кількості нулів, після яких ідуть одиниці.

Отже, обидва рядки будуть неспадними.

Тому відповідь дорівнює YES тоді й лише тоді, коли c_1 \le c_2 \le \ldots \le c_n.

Залишається лише перевірити кожну пару сусідніх позицій.

Часова складність розв'язання — $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;
}