Problem A – Kamilka’s Sheep and the Optimal Boost

Given n distinct positive integers a1, a2, …, an, choose a non–negative integer d and add d to every element. After the increment, pick any two resulting values x and y and compute gcd(x, y). The goal is to maximize this greatest common divisor.

Key observation: for any two indices i < j, the difference (aj + d) – (ai + d) = aj – ai is invariant under the uniform increment. Moreover, gcd(ai + d, aj + d) divides this difference. By the Euclidean algorithm, best we can achieve is exactly the difference itself. Hence the answer is simply the spread between the largest and smallest original numbers.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        int n;  cin >> n;
        vector<long long> a(n);
        for (auto &x : a) cin >> x;
        sort(a.begin(), a.end());
        cout << a.back() - a.front() << '\n';
    }
    return 0;
}

Problem B – Lady Bug’s Binary Jailbreak

Two length-n binary strings A and B are given. Allowed moves are:

• swap Ai with Bi–1 for any 2 ≤ i ≤ n, or
• swap Bi with Ai–1 for any 2 ≤ i ≤ n.

Determine whether A can be turned into an all-zero string.

The swaps effectively let every odd-indexed bit of A be exchanged with any even-indexed bit of B, and vice-versa. Consequently, the multiset of all ones in positions with the same parity can be freely redistributed between the two strings. Therefore the task reduces to checking whether the total number of ones in odd positions across both strings is ≤ ⌊n/2⌋ and the total number of ones in even positions is ≤ ⌈n/2⌉.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        int n;  cin >> n;
        string a, b;  cin >> a >> b;
        int odd = 0, even = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] == '1') (i & 1 ? even : odd)++;
            if (b[i] == '1') (i & 1 ? odd : even)++;
        }
        cout << (odd <= (n + 1) / 2 && even <= n / 2 ? "YES\n" : "NO\n");
    }
    return 0;
}

Problem C – Asuna’s Mosquito Towers

n non-negtaive integers h1, …, hn are given. One may repeatedly pick two indices i ≠ j such that hi + hj is odd and hi > 0, then decrease hi by 1 and increase hj by 1. The objective is to maximize max(h1, …, hn) after any number of moves.

The parity of the count of odd numbers is preserved. Let S be the total sum and c the number of odd values. Each odd value can be reduced to 1, transferring the rest to even piles, after which all evens can be funneled into one remaining odd pile. The resulting maximum is therefore S – c + 1. If all numbers share the same parity, no move is possible and the original maximum stands.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        int n;  cin >> n;
        vector<long long> a(n);
        for (auto &x : a) cin >> x;
        bool odd = false, even = false;
        for (auto x : a) {
            if (x & 1) odd = true;
            else even = true;
        }
        if (!odd || !even) {
            cout << *max_element(a.begin(), a.end()) << '\n';
            continue;
        }
        long long sum = accumulate(a.begin(), a.end(), 0LL);
        int cnt = count_if(a.begin(), a.end(), [](long long x){ return x & 1; });
        cout << sum - cnt + 1 << '\n';
    }
    return 0;
}

Problem D – Mishkin Energizer Rebalancing

A string s of length n over alphabet {L, I, T} is called balanced when each character appears the same number of times. Allowed operation: choose an index i < n with si ≠ si+1 and insert any character x ∉ {si, si+1} between them. Produce ≤ 2n moves to balance the string, or report impossibility.

Impossible only when the string is monochromatic. Otherwise repeatedly locate the rarest character and insert it at the first legal position. The greedy strategy never exceeds 2n insertions.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        int n;  cin >> n;
        string s;  cin >> s;
        int cnt[3] = {0};
        for (char c : s) cnt[c == 'L' ? 0 : c == 'I' ? 1 : 2]++;
        if (cnt[0] == n || cnt[1] == n || cnt[2] == n) {
            cout << "-1\n";
            continue;
        }
        vector<int> ops;
        string cur = s;
        while (true) {
            int m = cur.size();
            int c[3] = {0};
            for (char ch : cur) c[ch == 'L' ? 0 : ch == 'I' ? 1 : 2]++;
            int mx = max({c[0], c[1], c[2]});
            if (c[0] == mx && c[1] == mx && c[2] == mx) break;
            int target = 0;
            if (c[0] < mx) target = 0;
            else if (c[1] < mx) target = 1;
            else target = 2;
            char need = "LIT"[target];
            for (int i = 0; i + 1 < m; ++i) {
                if (cur[i] != cur[i + 1] && cur[i] != need && cur[i + 1] != need) {
                    cur.insert(cur.begin() + i + 1, need);
                    ops.push_back(i + 1);
                    break;
                }
            }
        }
        cout << ops.size() << '\n';
        for (int x : ops) cout << x << '\n';
    }
    return 0;
}

Problem E – Chessboard Parity Painting

An n × m grid initially green except for k cells already painted black or white. Re-color every green cell so that the number of adjacent (edge-sharing) pairs with different colors is even. Count the valid colorings modulo 1 000 000 007.

Working modulo 2, the parity of the count of differing adjacent pairs equals the sum over all cells of (degree × color). Interior cells have even degree and thus never afffect the parity. Only border cells (excluding the four corners) matter. Let u be the number of unpainted border cells and t the unpainted interior cells. Let v be the XOR of already-painted border cells. If u = 0 and v = 1 the answer is 0; otherwise it is 2t + max(0, u – 1).

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1'000'000'007;

long long pow2(long long e) {
    long long r = 1, b = 2;
    while (e) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;  cin >> T;
    while (T--) {
        long long n, m, k;  cin >> n >> m >> k;
        long long border = 2 * (n + m - 2);
        long long inside = n * m - border;
        long long free_border = border - 4;
        long long free_inside = inside;
        long long parity = 0;
        for (int i = 0; i < k; ++i) {
            long long x, y, c;  cin >> x >> y >> c;
            bool on_border = (x == 1 || x == n || y == 1 || y == m);
            if (on_border && !(x == 1 && y == 1) && !(x == 1 && y == m) &&
                             !(x == n && y == 1) && !(x == n && y == m)) {
                free_border--;
                parity ^= c;
            } else if (!on_border) {
                free_inside--;
            }
        }
        if (free_border == 0 && parity == 1) cout << "0\n";
        else cout << pow2(free_inside + max(0LL, free_border - 1)) << '\n';
    }
    return 0;
}