Codeforces Round #732 (Div. 2) - Unofficial Editorial (A - D)

A. AquaMoon and Two Arrays

We can calculate how many operations we need in order to make $a_i$ to become $b_i$ by increasing $a_i$ by 1 or decreasing $a_i$ by 1 digit by digit. Since each operation requires two changes. Therefore we can store $i$ in $inc$ if $a_i$ needs to be increased to be $b_i$, and vice versa in $dec$. If both size is not same, then there is no way to turn $a$ to $b$. Otherwise, we can iterate each $i$ in $inc$ and $dec$ and print $inc_i$ and $dec_i$ as one operation.

void solve() {
    int n; cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    vector<int> inc, dec;
    for(int i = 0; i < n; i++) {
        if(a[i] < b[i]) for(int j = 0; j < b[i] - a[i]; j++) inc.push_back(i);
        else if(b[i] < a[i]) for(int j = 0; j < a[i] - b[i]; j++) dec.push_back(i);
    }
    if(inc.size() != dec.size()) {
        cout << -1 << "\n";
    } else {
        cout << inc.size() << "\n";
        for(int i = 0; i < inc.size(); i++) {
            cout << dec[i] + 1 << " " << inc[i] + 1 << "\n";
        }
    }
}

B. AquaMoon and Stolen String

After shuffling some characters, we should be able to find $2 * n - 2$ pairs. However, we don't need to do that as we can solve it simply by the observation. We can notice that each character in stolen string must have an odd occurrence at every $j-th$ column. In this case, we can use a XOR bitwise trick to find out the expected character at $j-th$ column. This method works as each pair can cancel each other. Let's say we have 4 'a's and 1 'b'at the first column, we can know the the first character in the stolen string is $a \oplus a \oplus a \oplus a \oplus b = b$.

void solve() {
    int n, m; cin >> n >> m;
    string ans(m, 0);
    for(int i = 0; i < n * 2 - 1; i++) {
        string s; cin >> s;
        for(int j = 0; j < m; j++) {
            ans[j] ^= s[j];
        }
    }
    cout << ans << "\n";
}

C. AquaMoon and Strange Sort

In the beginning, the direction of each friend is right. At the end, we also need the direction to be right. Hence, for each digit, it can only move even number of times. We can calculate the occurrence of each digit in odd position and even position and compare with that after sorting $a$. If either one requires odd nubmer of times to move, then it returns $NO$.

const int mxN = 1e5 + 5;

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    vector<vector<int>> cnt(mxN, vector<int>(2));
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]][i % 2]++;
    }
    sort(a.begin(), a.end());
    for(int i = 0; i < n; i++) cnt[a[i]][i % 2]--;
    for(int i = 0; i < n; i++) {
        if(cnt[a[i]][0] != 0 || cnt[a[i]][1] != 0) {
            cout << "NO" << "\n";
            return;
        }
    }
    cout << "YES" << "\n";
}

D. AquaMoon and Chess

In each operation, basically we can only apply those $11$ groups. For example, if $s = 11110001011010$, we don't need to care about those 1s where $s[i - 1] = 0$ and $s[i + 1] = 0$ if applicable. Therefore, we can remove those unused 1s and rearranage it as $s = 111111000000$.

Let a pair of '11' be $X$ and $0$ be $Y$, then we can have $111111000000 -> XXXYYYYYY$ at the beginning. Then try to perform the operation to see the pattern.

$$111111000000 = XXXYYYYYY$$ $$111101100000 = XXYXYYYYY$$ $$111100110000 = XXYYXYYYY$$ $$111100011000 = XXYYYXYYY$$ $$111100001100 = XXYYYYXYY$$ $$111100000110 = XXYYYYYXY$$ $$111100000011 = XXYYYYYYX$$ $$110110000011 = XYXYYYYYX$$ $$...$$

We can notice that the answer is $C(N + M, N)$ where $N$ is the number of $X$ and $M$ is that of $Y$. In other words, we can put $X$ at position $(N + M)th$ column.

You can find the modint template here.

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    long long zero = 0, one = 0, sum = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '0') zero++, one += sum / 2, sum = 0;
        else sum++;
    }
    one += sum / 2;
    mint N = one + zero;
    mint M = one;
    cout << N.nCr(M) << "\n";
}