Tree-Based Resource Distribution

When distributing a fixed quantity of resources across a tree structure where each node must eventually hold an equal amount, removing any edge partitions the graph into two independent substructures. Let the total resource sum be $S$ and the number of nodes be $N$. The target allocation per node is $k = S / N$. For a subtree of size $m$, the required resource count is $m \times k$. By comparing the actual sum within the subtree against this target, the net flow across the connecting edge is determined. A positive difference indicates a surplus requiring upward transfer, while a negative difference indicates a deficit requiring downward transfer. A post-order traversal efficiently computes subtree sizes and accumulated resources. To output the operations in a valid sequence, a topological ordering based on in-degree tracking guarantees that dependencies are resolved, yielding the minimal number of transfer commands.

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

const int MAXN = 200005;
int node_count;
long long initial[MAXN], subtree_sum[MAXN], target_val;
int node_sz[MAXN], indegree[MAXN];
vector<int> adjacency[MAXN];
struct Operation { int to; long long qty; };
vector<Operation> actions[MAXN];

void compute_net_flow(int cur, int parent) {
    subtree_sum[cur] = initial[cur];
    node_sz[cur] = 1;
    for (int nxt : adjacency[cur]) {
        if (nxt == parent) continue;
        compute_net_flow(nxt, cur);
        subtree_sum[cur] += subtree_sum[nxt];
        node_sz[cur] += node_sz[nxt];
    }
    long long delta = subtree_sum[cur] - (node_sz[cur] * target_val);
    if (delta > 0) {
        actions[cur].push_back({parent, delta});
        indegree[parent]++;
    } else if (delta < 0) {
        actions[parent].push_back({cur, -delta});
        indegree[cur]++;
    }
}

void execute_operations() {
    int total_ops = 0;
    for (int i = 1; i <= node_count; ++i) total_ops += actions[i].size();
    cout << total_ops << "\n";
    queue<int> q;
    for (int i = 1; i <= node_count; ++i) if (indegree[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& op : actions[u]) {
            cout << u << " " << op.to << " " << op.qty << "\n";
            if (--indegree[op.to] == 0) q.push(op.to);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    long long total_res = 0;
    cin >> node_count;
    for (int i = 1; i <= node_count; ++i) { cin >> initial[i]; total_res += initial[i]; }
    target_val = total_res / node_count;
    for (int i = 1; i < node_count; ++i) {
        int u, v; cin >> u >> v;
        adjacency[u].push_back(v); adjacency[v].push_back(u);
    }
    compute_net_flow(1, 0);
    execute_operations();
    return 0;
}

Greedy Deadhead Minimization

Minimizing total travel distance in a routing system where payloads must be moved between fixed coordinates relies on decoupling loaded and empty segments. The loaded distance remains invariant regardless of scheduling. Therefore, optimization focuses solely on reducing empty traversal. By aggregating all departure coordinates into one list and all arrival coordinates into another, appending the final return-to-origin point, and sorting both arrays independently, the minimal empty distance is achieved by pairing the $i$-th element of each sorted sequence. This greedy matching guarantees shortest cumulative deviation.

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

typedef long long ll;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int requests, limit;
    if (!(cin >> requests >> limit)) return 0;
    vector<int> origins, destinations;
    origins.reserve(requests + 1);
    destinations.reserve(requests + 1);
    ll loaded_dist = 0;
    for (int i = 0; i < requests; ++i) {
        int s, e; cin >> s >> e;
        origins.push_back(s);
        destinations.push_back(e);
        loaded_dist += abs(s - e);
    }
    origins.push_back(limit);
    destinations.push_back(0);
    sort(origins.begin(), origins.end());
    sort(destinations.begin(), destinations.end());
    ll empty_dist = 0;
    for (size_t i = 0; i < origins.size(); ++i) empty_dist += abs(origins[i] - destinations[i]);
    cout << loaded_dist + empty_dist << "\n";
    return 0;
}

Subtree Range Queries via Square Root Decompsoition

Counting nodes with values exceeding a threshold within a specific subtree can be transformed into a range query problem using DFS linearization. Each node is assigned an entry timestamp, defining a contiguous interval $[L, R]$ representing its subtree. After coordinate compression, the problem reduces to counting elements greater than $X$ in a static array range. Square root decomposition partitions the array into blocks. Each block stores a sorted copy of its values, enabling logarithmic time binary searches for complete blocks, while partial blocks are scanned linearly. This hybrid approach balances preprocessing and query complexity effectively.

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

const int MX = 100005;
int n, block_len;
int raw_weights[MX], compressed[MX];
vector<int> children[MX];
int entry_time[MX], exit_time[MX], linear_map[MX], clock_idx = 0;
int blk_start[MX], blk_end[MX], blk_idx[MX], sorted_blk[MX];

void flatten_tree(int u) {
    entry_time[u] = ++clock_idx;
    linear_map[clock_idx] = u;
    for (int v : children[u]) flatten_tree(v);
    exit_time[u] = clock_idx;
}

void discretize() {
    vector<int> vals(n);
    for (int i = 1; i <= n; ++i) vals[i-1] = raw_weights[i];
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 1; i <= n; ++i)
        compressed[i] = lower_bound(vals.begin(), vals.end(), raw_weights[i]) - vals.begin() + 1;
}

int count_greater(int l, int r, int threshold) {
    if (l > r) return 0;
    int b_l = blk_idx[l], b_r = blk_idx[r], cnt = 0;
    if (b_l == b_r) {
        for (int i = l; i <= r; ++i) if (compressed[linear_map[i]] >= threshold) cnt++;
        return cnt;
    }
    for (int i = l; i <= blk_end[b_l]; ++i) if (compressed[linear_map[i]] >= threshold) cnt++;
    for (int b = b_l + 1; b < b_r; ++b)
        cnt += blk_end[b] - (lower_bound(sorted_blk + blk_start[b], sorted_blk + blk_end[b] + 1, threshold) - sorted_blk) + 1;
    for (int i = blk_start[b_r]; i <= r; ++i) if (compressed[linear_map[i]] >= threshold) cnt++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> raw_weights[i];
    for (int i = 2; i <= n; ++i) { int p; cin >> p; children[p].push_back(i); }
    flatten_tree(1); discretize();
    block_len = sqrt(n);
    int total_blks = (n + block_len - 1) / block_len;
    for (int b = 0; b < total_blks; ++b) {
        blk_start[b] = b * block_len + 1;
        blk_end[b] = min((b + 1) * block_len, n);
        for (int i = blk_start[b]; i <= blk_end[b]; ++i) {
            blk_idx[i] = b;
            sorted_blk[i] = compressed[linear_map[i]];
        }
        sort(sorted_blk + blk_start[b], sorted_blk + blk_end[b] + 1);
    }
    for (int u = 1; u <= n; ++u)
        cout << count_greater(entry_time[u] + 1, exit_time[u], compressed[u] + 1) << "\n";
    return 0;
}

Modular Arihtmetic Game Optimization

In subtraction games where players remove a prime number $p$ such that $p \equiv a \pmod 4$, the winning condition hinges entirely on $a \pmod 4$. If $a$ is divisible by 4, the second player forces a win. Otherwise, the first player controls the parity. To minimize game length, the winning player selects the largest valid prime congruent to the current residue modulo 4. Even positions resolve deterministically in $a/2$ turns. For odd positions, the required moves equal $1 + (a - p)/2$, where $p$ is the precomputed maximal prime matching the residue. A linear sieve populates these maximal primes efficiently, enabling $O(1)$ lookups during query resolution.

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

const int LIMIT = 5000005;
bool composite[LIMIT];
int max_prime_mod4[4];
int turns_cache[LIMIT];

void build_sieve() {
    max_prime_mod4[0] = 2; max_prime_mod4[1] = 1;
    max_prime_mod4[2] = 2; max_prime_mod4[3] = 3;
    turns_cache[1] = 1;
    for (int i = 2; i < LIMIT; ++i) {
        if (!composite[i]) {
            for (int j = i << 1; j < LIMIT; j += i) composite[j] = true;
            max_prime_mod4[i % 4] = i;
        }
        int rem = i % 4;
        turns_cache[i] = (i - max_prime_mod4[rem]) / 2 + 1;
    }
}

void process_case() {
    int groups; cin >> groups;
    int min_turns = LIMIT;
    while (groups--) {
        int val; cin >> val;
        min_turns = min(min_turns, turns_cache[val]);
    }
    if (min_turns & 1) cout << "Farmer John\n";
    else cout << "Farmer Nhoj\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    build_sieve();
    int queries; cin >> queries;
    while (queries--) process_case();
    return 0;
}

Compiler Configuration and Runtime Limits

Certain competitive programming environments enforce strict standard compliance, which can trigger compilation errors when relying on non-standard global array initialization or implicit type conversions. Replacing ambiguous declarations with explicit standard constructs or static initialization lists resolves these incompatibilities. Additionally, deep recursive traversals may exhaust default stack allocations on local development machines. Mitigating this involves adjusting linker directives to expand the stack segment. For GCC-based toolchains, appending -Wl,--stack=134217728 to compilation flags allocates 128MB of stack space. MSVC users can apply #pragma comment(linker, "/STACK:134217728") at the source level. Verifying memory limits before contest submissions prevents unexpected runtime failures on large test cases.