Nasser and Equal Array (Editorial)

Solution

General Idea: We need to decide whether all elements of the array can be made equal using the two operations.

Operation $1$ adds $2$, so it never changes the parity of an element.

Operation $2$ needs a segment of length at least $2$ whose elements are all equal. Two adjacent elements can only be equal if they have the same parity, and the operation flips the parity of the whole segment.

If n = 1, the array already consists of equal elements, so the answer is YES.

If no two adjacent elements have the same parity, the parities alternate. Operation $1$ keeps them alternating, and operation $2$ can never be applied because no two adjacent elements can become equal. So the answer is NO.

Otherwise, there is an index $i$ such that a_i and a_{i+1} have the same parity. We raise the smaller one by steps of $2$ until they are equal, which gives a block of equal values. Then we expand the block one neighbour at a time:

If the neighbour has the same parity as the block, we use operation $1$ on the smaller side by steps of $2$ until they are equal. If the block is the smaller side, we raise it by applying operation $2$ twice for each step of $2$.

If the neighbour has a different parity, we apply operation $2$ once on the block to flip its parity, and then continue as above.

Repeating this until the block covers the whole array makes all elements equal, so the answer is YES.

Therefore the answer is YES if and only if n = 1 or there exists an index $i$ such that:

The solution scans the array once, so it runs in $\mathcal{O}(n)$ time per test case.

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << "YES";
        return;
    }
    bool ok = false;
    for (int i = 1; i < n; i++) {
        if ((a[i] - a[i + 1]) % 2 == 0) {
            ok = true;
            break;
        }
    }
    cout << (ok ? "YES" : "NO");
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}