A

Problem: Group the numbers 1 to 12 into sets: {1, 3, 5, 7, 8, 10, 12}, {4, 6, 9, 11}, {2}. Given two numbers, determine if they belong to the same group.

Solution: This is essentially a connectivity problem, which can be solved using a union-find data structure.

const int N = 14;
int fa[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void solve() {
    for (int i = 0; i < N; i++) fa[i] = i;
    std::set<int> S{1, 3, 5, 7, 8, 10, 12};
    for (auto x : S) fa[find(x)] = find(*S.begin());
    S.clear(); S.insert({4, 6, 9, 11});
    for (auto x : S) fa[find(x)] = find(*S.begin());
    S.clear(); S.insert({2});
    for (auto x : S) fa[find(x)] = find(*S.begin());
    int x, y; std::cin >> x >> y;
    std::cout << (find(x) == find(y) ? "Yes" : "No") << "\n";
}

B

Problem: Given an H × W image, output the image surrounded by a border of '#' characters.

Solution: Simulate the process by creating a new grid that is two rows and two columns larger, and place the original image offset by one row and one column.

int n, m; std::cin >> n >> m;
std::vector<std::vector<char>> g(n + 1, std::vector<char>(m + 1));
for (int i = 1; i <= n; i++) {
    std::string s; std::cin >> s;
    for (int j = 1; j <= m; j++) {
        g[i][j] = s[j - 1];
    }
}
std::vector<std::vector<char>> g2(n + 3, std::vector<char>(m + 3, '#'));
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        g2[i + 1][j + 1] = g[i][j];
    }
}
for (int i = 1; i <= n + 2; i++) {
    for (int j = 1; j <= m + 2; j++) {
        std::cout << g2[i][j];
    }
    std::cout << "\n";
}

C

Problem: Cut an H × W rectangle into three smaller rectangles with integer side lengths. Minimize the difference between the largest and smallest area among the three. Constraints: 2 ≤ H, W ≤ 10⁵.

Solution: One of the three rectangles must share a entire side with the original rectangle. There are four possible cutting patterns:

• Three vertical rectangles.
• One vertical rectangle on one side and two horizontal rectangles.
• Rotating the above by 90 degrees gives the other two patterns.

For three vertical rectangles, the optimal split makes the widths as equal as possible. The answer is H × (W % 3 != 0). Similarly for three horizontal rectangles.

For the mixed patterns (one vertical plus two horizontal, or one horizontal plus two vertical), we can enumerate the width (or height) of the rectangle that shares the full side, and then split the remaining part into two equal halves (as close as possible). This can be done in O(H + W) by scanning, or optimized to O(log max(H, W)) using ternary search due to the unimodal nature of the function.

#include <algorithm>
#include <iostream>
typedef long long ll;

ll solve() {
    ll H, W; std::cin >> H >> W;
    ll ans = 1LL << 60;
    if (W >= 3) ans = std::min(ans, 1LL * H * (W % 3 != 0));
    if (H >= 3) ans = std::min(ans, 1LL * W * (H % 3 != 0));
    
    ll S[3];
    auto calc = [&] (ll L1, ll L2, ll X) -> ll {
        S[0] = L1 * X;
        S[1] = (L2 - X) * (L1 / 2);
        S[2] = (L2 - X) * ((L1 + 1) / 2);
        std::sort(S, S + 3);
        return S[2] - S[0];
    };
    
    // Case 1: vertical stripe on left, then split right part horizontally
    ll L = 1, R = W - 1;
    while (R - L > 3) {
        ll M1 = L + (R - L) / 3, M2 = L + (R - L) * 2 / 3;
        if (calc(H, W, M1) > calc(H, W, M2)) L = M1;
        else R = M2;
    }
    for (ll i = L; i <= R; i++) {
        ans = std::min(ans, calc(H, W, i));
    }
    
    // Case 2: horizontal stripe on top, then split bottom part vertically
    L = 1, R = H - 1;
    while (R - L > 3) {
        ll M1 = L + (R - L) / 3, M2 = L + (R - L) * 2 / 3;
        if (calc(W, H, M1) > calc(W, H, M2)) L = M1;
        else R = M2;
    }
    for (ll i = L; i <= R; i++) {
        ans = std::min(ans, calc(W, H, i));
    }
    
    std::cout << ans << "\n";
    return ans;
}

D

Problem: Given an array of length 3N, remove N elements without changing the order. The value is the sum of the first N remaining elements minus the sum of the last N remaining elements. Find the maximum possible value. Constraints: 1 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ 10⁹.

Solution: Let the 3N elements be colored: removed elements are black, the first N remaining are blue, the last N remaining are red. For any split point L between N and 2N, the blue elements are the N largest elements to the left of L, and the red elements are the N smallest elements to the right of L.

We can compute prefix arrays using heaps. Process from left to right with a min-heap to keep the largest N elements so far, storing the sum at each position. Process from right to left with a max-heap to keep the smallest N elements so far, storing the sum at each position. Then the answer is the maximum over L in [N, 2N] of (sumL[L] - sumR[L+1]).

Time complexity: O(N log N).

#include <iostream>
#include <vector>
#include <queue>
typedef long long ll;

int main() {
    int N; std::cin >> N;
    std::vector<int> a(3 * N + 1);
    for (int i = 1; i <= 3 * N; i++) std::cin >> a[i];
    
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
    ll cur = 0;
    std::vector<ll> sumL(3 * N + 1);
    for (int i = 1; i <= 3 * N; i++) {
        if (pq_min.size() < N) {
            cur += a[i];
            pq_min.push(a[i]);
        } else if (pq_min.top() < a[i]) {
            cur -= pq_min.top();
            cur += a[i];
            pq_min.pop();
            pq_min.push(a[i]);
        }
        sumL[i] = cur;
    }
    
    std::priority_queue<int, std::vector<int>, std::less<int>> pq_max;
    cur = 0;
    std::vector<ll> sumR(3 * N + 1);
    for (int i = 3 * N; i >= 1; --i) {
        if (pq_max.size() < N) {
            cur += a[i];
            pq_max.push(a[i]);
        } else if (pq_max.top() > a[i]) {
            cur -= pq_max.top();
            cur += a[i];
            pq_max.pop();
            pq_max.push(a[i]);
        }
        sumR[i] = cur;
    }
    
    ll ans = - (1LL << 60);
    for (int i = N; i <= 2 * N; i++) {
        ans = std::max(ans, sumL[i] - sumR[i + 1]);
    }
    std::cout << ans << "\n";
    return 0;
}

The algorithm runs in O(N log N) due to heap operations.