A

Given a sequence ${a_n}$, select the largest possible subset such that no two selected elements sum to a prime number.

Constraints: $T \leq 4$, $n \leq 750$, $a_i \leq 10^9$.

Identical values can be merged into counts. Note that at most one instance of 1 may be included.

This becomes a bipartite graph problem: odd numbers connect to the source, even numbers to the sink, with capacities equal to their counts. For every pair $(i,j)$ where $a_i + a_j$ is prime, add an infinite-capacity edge from the odd node to the even node. The answer is the total count minus the minimum cut.

Primality testing uses Miller–Rabin with bases $2, 3, 5, 7, 11$, sufficient for numbers up to $2 \times 10^9$. The overall complexity is $O(n^2 \sqrt[4]{V})$ for building the graph plus max-flow computation.

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

typedef long long ll;
const int N = 755, M = 1200000, INF = 1e9;

int qpow(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod;
        b >>= 1;
    }
    return res;
}

bool isPrime(int n) {
    if (n == 2) return true;
    if (n < 2 || !(n & 1)) return false;
    static int test[] = {2, 3, 5, 7, 11};
    for (int a : test) {
        if (a >= n) break;
        if (qpow(a, n - 1, n) != 1) return false;
    }
    return true;
}

struct Dinic {
    struct Edge { int to, cap, rev; };
    vector<Edge> g[N];
    int level[N], iter[N];

    void add(int u, int v, int cap) {
        g[u].push_back({v, cap, (int)g[v].size()});
        g[v].push_back({u, 0, (int)g[u].size() - 1});
    }

    void bfs(int s) {
        memset(level, -1, sizeof(level));
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &e : g[u])
                if (e.cap > 0 && level[e.to] < 0)
                    level[e.to] = level[u] + 1, q.push(e.to);
        }
    }

    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int &i = iter[u]; i < (int)g[u].size(); ++i) {
            Edge &e = g[u][i];
            if (e.cap > 0 && level[u] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int maxflow(int s, int t) {
        int flow = 0, f;
        for (;;) {
            bfs(s);
            if (level[t] < 0) return flow;
            memset(iter, 0, sizeof(iter));
            while ((f = dfs(s, t, INF)) > 0) flow += f;
        }
    }

    void clear(int n) {
        for (int i = 0; i <= n; ++i) g[i].clear();
    }
} G;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> a(n);
        for (int &x : a) cin >> x;
        sort(a.begin(), a.end());

        // Remove extra 1s
        int start = 0;
        while (start + 1 < n && a[start] == 1 && a[start + 1] == 1) start++;

        vector<int> vals(a.begin() + start, a.end());
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());

        unordered_map<int, int> cnt;
        for (int i = start; i < n; ++i) cnt[a[i]]++;

        int V = vals.size();
        int S = V, T_node = V + 1;
        G.clear(T_node + 1);

        for (int i = 0; i < V; ++i) {
            if (vals[i] & 1)
                G.add(S, i, cnt[vals[i]]);
            else
                G.add(i, T_node, cnt[vals[i]]);
        }

        for (int i = 0; i < V; ++i)
            for (int j = i + 1; j < V; ++j)
                if (isPrime(vals[i] + vals[j])) {
                    if (vals[i] & 1)
                        G.add(i, j, INF);
                    else
                        G.add(j, i, INF);
                }

        int total = n - start;
        cout << total - G.maxflow(S, T_node) << '\n';
    }
    return 0;
}

B

On an $n \times m$ grid with bombs (k) and crystals (b), triggering a bomb detonates either its entire row or column, which may chain-react other bombs. Determine the maximum number of crystals that can be destroyed.

Constraints: $n, m \leq 3000$, total non-empty cells $\leq nm$.

Model bombs as nodes. Connect each bomb to the nearest bomb in each of the four directions. This forms connected components. Within each component:

• If it contains a cycle, all rows and columns touched by any bomb in the component can be fully triggered.
• If acyclic (a tree), optimal triggering starts from a leaf bomb (with only one neighbor), sacrificing either its row or column—choose the option losing fewer crystals.

Use union-find to detect cycles and group bombs. Precompute 2D prefix sums for crystal counts per row/column segment.

Time complexity: $O(nm \alpha(nm))$.

C

On an $n \times m$ toroidal grid (left-right wraparound), multiple independent tokens move under these rules:

• Cannot revisit cells or enter obstacles (#).
• Can move left, right, or down.
• Wrap between $(i,1)$ and $(i,m)$.

Players alternate moves; the player unable to move loses. Determine the winner assuming optimal play.

Since tokens are independent, compute the XOR of Sprague–Grundy (SG) values for all starting positions.

Key observations:

• For rows containing atleast one obstacle, state depends only on direction (none, left-only, right-only), yielding $O(nm)$ states.
• For empty rows, precompute transition tables:
  • From any cell, simulate propagation left/right to determine SG values at boundaries.
  • Use memoization and reverse propagation to fill SG values in $O(1)$ per cell.

Overall complexity: $O(nm)$ per test case.

D

Given a tree rooted at node 1 and weights $d_i$, for each node $i$, compute:

$$ \sum_{j=1}^{n} [\text{dist}(j,i) \leq 2 \cdot \text{dist}(1,i)] \cdot d_j $$

Constraints: $n \leq 2 \times 10^6$, $\sum d_i < 2^{31}$.

This requires efficient subtree aggregation with distance constraints. Heavy-light decomposition (HLD) or centroid decomposition can be applied, but the intended solution likely uses a specialized DFS with careful bookkeeping of contributions within distance thresholds.