A. Gardener and the Capybaras

Given a string composed of characters 'a' and 'b', split it into three non-empty substrings. The goal is to make the middle substring lexicographically either the smallest or the largest among the three. Output any valid split or :( if impossible.

Approach: The presence of only 'a' and 'b' is not restrictive. For the middle substring to be the smallest, the character with the minimum value must appear in a position that is neither the first nor the last. If such a position exists, place that single character as the middle substring. For the middle substring to be the largest, identify the character with the maximum value. Starting fromm its first occurrence, extend it to the end of the string, excluding the final character, to form the middle substring. If neither construction is feasible, no solution exists.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        string inputStr;
        cin >> inputStr;
        char minChar = 127, maxChar = 0;
        for (char ch : inputStr) {
            if (ch < minChar) minChar = ch;
            if (ch > maxChar) maxChar = ch;
        }
        bool found = false;
        for (int idx = 1; idx < (int)inputStr.length() - 1; idx++) {
            if (inputStr[idx] == minChar) {
                cout << inputStr.substr(0, idx) << ' ' << inputStr[idx] << ' ' << inputStr.substr(idx + 1) << '\n';
                found = true;
                break;
            }
        }
        if (found) continue;
        string left, middle, right;
        for (int idx = 1; idx < (int)inputStr.length() - 1; idx++) {
            if (inputStr[idx] == maxChar) {
                left = inputStr.substr(0, idx);
                middle = inputStr.substr(idx, inputStr.length() - idx - 1);
                right = inputStr.back();
                break;
            }
        }
        if (!middle.empty() && middle >= left && middle >= right) {
            cout << left << ' ' << middle << ' ' << right << '\n';
        } else {
            cout << ":(" << '\n';
        }
    }
    return 0;
}

B. Gardener and the Array

Given a sequence of large numbers (bits up to 2×10^5), each represented by its set bits, determine if two distinct subsequences exist whose bitwise OR results are equal.

Approach: A key observation: if a solution exists, one subsequence can be the entire array. By adjustment, if two valid subsequences A and B exist (|A| ≥ |B|), numbers not in A can be added to both if they change the OR, otherwise added only to A. This leads to another observation: a solution exists if and only if the entire array's OR equals the OR of the array after removing one specific element. Implement by counting how many numbers have each bit set. For each element, check if for every bit it sets, the count remains at least 2 after its removal, ensuring other elements cover that bit.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int elemCount;
        cin >> elemCount;
        vector<vector<int>> bitLists(elemCount);
        vector<int> bitFreq(200001, 0);
        for (int i = 0; i < elemCount; i++) {
            int len;
            cin >> len;
            bitLists[i].resize(len);
            for (int j = 0; j < len; j++) {
                cin >> bitLists[i][j];
                bitFreq[bitLists[i][j]]++;
            }
        }
        bool possible = false;
        for (int i = 0; i < elemCount; i++) {
            bool valid = true;
            for (int bit : bitLists[i]) {
                if (bitFreq[bit] == 1) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                possible = true;
                break;
            }
        }
        cout << (possible ? "Yes" : "No") << '\n';
    }
    return 0;
}

C. Interesting Sequence

Given integers n and x, find the smallest m such that the bitwise AND of all numbers from n to m (inclusive) equals x. If no such m exists, output -1.

Approach: The bitwise AND of a consecutive range results in n with some trailing bits cleared. For the minimal m, the condition simplifies to n & m = x. Compute y = n ^ x. The value m must clear the highest set bit in y and all lower bits in n. Let mask be the smallest power of two greater than y. If n has the bit corresponding to mask set, output -1. Otherwise, set that bit in n and clear all lower bits to form m. Verify that n & m equals x.

#include <iostream>
using namespace std;

int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        long long n, x;
        cin >> n >> x;
        if (n == x) {
            cout << n << '\n';
            continue;
        }
        long long diff = n ^ x;
        long long bit = 1;
        long long temp = n;
        while (bit <= diff) {
            if (temp & bit) temp ^= bit;
            bit <<= 1;
        }
        if (n & bit) {
            cout << "-1" << '\n';
        } else {
            temp |= bit;
            if ((n & temp) == x) cout << temp << '\n';
            else cout << "-1" << '\n';
        }
    }
    return 0;
}

D. Friendly Spiders

Given n numbers, connect two nodes i and j if gcd(a_i, a_j) > 1. Find the shortest path between nodes s and t.

Approach: Construct a bipartite graph with original nodes and auxiliary nodes for prime factors. For each number, connect it to nodes representing its prime factors. This reduces edge complexity to O(n log max_a). Perform a BFS from s to t on this expanded graph, tracking predecessors to reconstruct the path of original nodes.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX_VAL = 300000;
vector<int> primes;
vector<bool> isComposite(MAX_VAL + 1, false);

void sieve() {
    for (int i = 2; i <= MAX_VAL; i++) {
        if (!isComposite[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= MAX_VAL; j += i) isComposite[j] = true;
        }
    }
}

int main() {
    sieve();
    int nodeCount;
    cin >> nodeCount;
    vector<vector<int>> graph(nodeCount + primes.size() + 5);
    vector<int> values(nodeCount + 1);
    for (int i = 1; i <= nodeCount; i++) {
        cin >> values[i];
        int val = values[i];
        for (int p : primes) {
            if (p * p > val) break;
            if (val % p == 0) {
                graph[i].push_back(nodeCount + p);
                graph[nodeCount + p].push_back(i);
                while (val % p == 0) val /= p;
            }
        }
        if (val > 1) {
            auto it = lower_bound(primes.begin(), primes.end(), val);
            int idx = distance(primes.begin(), it);
            graph[i].push_back(nodeCount + primes[idx]);
            graph[nodeCount + primes[idx]].push_back(i);
        }
    }
    int start, target;
    cin >> start >> target;
    vector<int> dist(graph.size(), -1);
    vector<int> prev(graph.size(), -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int neighbor : graph[cur]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[cur] + 1;
                prev[neighbor] = cur;
                q.push(neighbor);
            }
        }
    }
    if (dist[target] == -1) {
        cout << "-1" << '\n';
    } else {
        stack<int> path;
        for (int v = target; v != -1; v = prev[v]) {
            if (v <= nodeCount) path.push(v);
        }
        cout << path.size() << '\n';
        while (!path.empty()) {
            cout << path.top() << ' ';
            path.pop();
        }
        cout << '\n';
    }
    return 0;
}

E. The Human Equation

Given a sequence, you can repeatedly select a subsequence and alternately add 1 to odd-indexed elements and subtract 1 from even-indexed elements (or vice versa). Find the minimum operations to make all elements zero.

Approach: Maintain two accumulators: pos_acc for net positive contributions and neg_acc for net negative contributions from previous operations. Iterate through the sequence. For a positive element val, if neg_acc >= val, it can be neutralized by previous negative operations, transferring val to pos_acc and reducing neg_acc. Otherwise, val - neg_acc new operations are needed, added to the answer, pos_acc increases by val, and neg_acc resets to zero. Handle negative elements symmetrically.

#include <iostream>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        long long pos_acc = 0, neg_acc = 0, operations = 0;
        for (int i = 0; i < n; i++) {
            long long val;
            cin >> val;
            if (val > 0) {
                pos_acc += val;
                if (neg_acc >= val) neg_acc -= val;
                else {
                    operations += val - neg_acc;
                    neg_acc = 0;
                }
            } else {
                val = -val;
                neg_acc += val;
                if (pos_acc >= val) pos_acc -= val;
                else {
                    operations += val - pos_acc;
                    pos_acc = 0;
                }
            }
        }
        cout << operations << '\n';
    }
    return 0;
}

F. Laboratory on Pluto

Select n cells on an infinite grid to minimize perimeter. Two query types: Type 1 constructs an optimal shape; Type 2 computes the minimal perimeter and the number of optimal shapes modulo a given value.

Approach: For minimal perimeter, the shape approximates a rectangle. Let r ≤ c be dimensions with r * c ≥ n. Minimize 2*(r+c). For construction (Type 1), choose r that minimizes perimeter and fill row by row. For counting (Type 2), optimal shapes are nearly rectangular with corners possibly missing. Define dp[i][j] as the number of non-decreasing sequences of length i summing to j, representing one corner's missing cells. Compute prefix sums f[k] for up to k missing cells. The count for a shape with total missing cells K is the convolution of four f arrays. Precompute these for K up to √n. Enumerate feasible r near √n to sum counts, adjusting for when r = c.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<vector<int>> dp;
vector<int> f, g, h;
int MOD;

void precompute(int limit) {
    dp.assign(limit + 1, vector<int>(limit + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= limit; i++) {
        for (int j = i; j <= limit; j++) {
            if (i == j) dp[i][j] = 1;
            else {
                dp[i][j] = dp[i-1][j-1];
                if (j > i) dp[i][j] = (dp[i][j] + dp[i][j-i]) % MOD;
            }
        }
    }
    f.assign(limit + 1, 0);
    f[0] = 1;
    for (int k = 1; k <= limit; k++) {
        for (int i = 1; i <= k; i++) {
            f[k] = (f[k] + dp[i][k]) % MOD;
        }
    }
    g.assign(2 * limit + 1, 0);
    for (int i = 0; i <= limit; i++) {
        for (int j = 0; j <= limit; j++) {
            g[i+j] = (g[i+j] + (long long)f[i] * f[j] % MOD) % MOD;
        }
    }
    h.assign(2 * limit + 1, 0);
    for (int i = 0; i <= limit; i++) {
        for (int j = 0; j <= 2 * limit; j++) {
            if (i + j <= 2 * limit) h[i+j] = (h[i+j] + (long long)f[i] * g[j] % MOD) % MOD;
        }
    }
}

void solveType1(int n) {
    int best_r = 1;
    for (int r = 2; r <= n; r++) {
        int c = (n + r - 1) / r;
        int cur = r + c;
        int best_c = (n + best_r - 1) / best_r;
        if (cur < best_r + best_c) best_r = r;
    }
    int c = (n + best_r - 1) / best_r;
    cout << best_r << ' ' << c << '\n';
    int remaining = n;
    for (int i = 0; i < best_r; i++) {
        for (int j = 0; j < c; j++) {
            if (remaining > 0) {
                cout << '#';
                remaining--;
            } else cout << '.';
        }
        cout << '\n';
    }
}

void solveType2(int n) {
    int best_r = 1;
    int low = max(1, (int)sqrt(n) - 100);
    int high = min(n, (int)sqrt(n) + 100);
    for (int r = low; r <= high; r++) {
        int c = (n + r - 1) / r;
        if (r + c < best_r + (n + best_r - 1) / best_r) best_r = r;
    }
    int min_perim = 2 * (best_r + (n + best_r - 1) / best_r);
    cout << min_perim << ' ';
    long long total_ways = 0;
    for (int r = low; r <= high; r++) {
        int c = (n + r - 1) / r;
        if (r > c) break;
        if (r + c != best_r + (n + best_r - 1) / best_r) continue;
        int missing = r * c - n;
        total_ways = (total_ways + h[missing] * (r == c ? 1 : 2)) % MOD;
    }
    cout << total_ways << '\n';
}

int main() {
    int T, type;
    cin >> T >> type;
    if (type == 2) {
        cin >> MOD;
        precompute(1000);
    }
    while (T--) {
        int n;
        cin >> n;
        if (type == 1) solveType1(n);
        else solveType2(n);
    }
    return 0;
}