U USACO Prep

2023 February Gold · All three problems

← Back to Feb 2023 hub · Official results

Canonical statements live at usaco.org. Statements below are my paraphrase — open the official problem PDFs before submitting your own solution. Each problem links to the official viewer.

Problem 1 · Equal Sum Subarrays

Official problem (cpid=1305)

Statement (paraphrased)

You are given an array a[1..N] whose ½N(N+1) contiguous subarray sums are all distinct. For each index i, compute the minimum |Δ| such that replacing ai with ai+Δ produces an array containing two distinct subarrays with equal sum.

Constraints

Key idea

Changing ai by Δ shifts a subarray sum by Δ iff the subarray contains index i, else by 0. The N(N+1)/2 subarray sums split into two groups per i: those containing i (shifted), those not (fixed). The minimum |Δ| forcing a collision is the minimum |scontains − snot| across all pairs (one from each group) — plus, if any two shifted subarrays already have equal post-shift sum for some Δ, equivalently any two sums in the "contains-i" group with matching difference… but since all original sums are distinct, the minimum Δ comes purely from cross-group differences, PLUS the minimum |a − b| inside the contains-i group taken pair-wise (giving Δ = b−a if both shift by Δ — but they shift by the same amount, so their difference is invariant — disregard). So compute all subarray sums (O(N²)), and for each i partition into "contains/doesn't" and find the closest pair across the partition via sorted merge in O(N²).

That's O(N²) per i and O(N⁴) total — too slow. Standard editorial uses a sorted master list and for each i sweeps the sorted-order toggle of "contains-i" subarrays, finding the closest cross-color pair in O(N² log N) overall.

Complexity target

O(N3) or O(N² log N) total.

C++ reference solution

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

int main(){
    int N; cin >> N;
    vector<ll> a(N+1), pre(N+1, 0);
    for (int i = 1; i <= N; ++i){ cin >> a[i]; pre[i] = pre[i-1] + a[i]; }
    // Enumerate all O(N^2) subarrays with their (l, r, sum)
    int K = N*(N+1)/2;
    vector<tuple<ll,int,int>> subs; subs.reserve(K);
    for (int l = 1; l <= N; ++l)
        for (int r = l; r <= N; ++r)
            subs.emplace_back(pre[r]-pre[l-1], l, r);
    sort(subs.begin(), subs.end());

    // For each i, walk sorted list. Color each subarray "yes" if it contains i, else "no".
    // Min |Δ| = min |sum_yes − sum_no| over adjacent-in-sorted-order opposite-colored pairs.
    for (int i = 1; i <= N; ++i){
        ll best = LLONG_MAX;
        int prevCol = -1; ll prevSum = 0;
        for (auto& [s, l, r] : subs){
            int col = (l <= i && i <= r) ? 1 : 0;
            if (prevCol != -1 && col != prevCol) best = min(best, s - prevSum);
            prevCol = col; prevSum = s;
        }
        cout << best << '\n';
    }
}

Pitfalls

Problem 2 · Fertilizing Pastures

Official problem (cpid=1306)

Statement (paraphrased)

A tree of N pastures rooted at 1, each pasture i with grass rate ai. Each edge takes 1 second to traverse. Farmer John walks from pasture 1, visiting every pasture; on arrival at pasture i at time t he pays t·ai fertilizer. If T=0 he must return to root after visiting all; if T=1 he may end anywhere. Minimise total time first, then total fertilizer.

Constraints

Key idea

For T=0 each edge is traversed exactly twice, so total time = 2(N−1). At every fork the order of children matters for the fertilizer total. For a subtree rooted at child c with size s(c) and "total fertilizer if visited first at time 0" f(c) and total grass-rate W(c), if we visit child x before child y the contribution adds W(y)·(2 s(x)) on top of f(y). Greedy/exchange-argument: order children by ratio s(c) / W(c) ascending (Smith's rule analogue). Then compute totals bottom-up. For T=1, pick the single best leaf to end at — saves the return walk of its root-leaf path; choose the path maximising the savings ≈ depth − (sum of rates beyond the cut). Tree DP from there.

Complexity target

O(N log N) for the per-node child sort.

C++ reference solution

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

int N, mode;
vector<vector<int>> ch;
vector<ll> a;
vector<ll> sz, W, F; // size, sum of rates, fertilizer if subtree entered at t=0

void dfs(int u){
    sz[u] = 1; W[u] = a[u]; F[u] = 0;
    vector<tuple<long double,int>> ord;
    for (int v : ch[u]){ dfs(v); ord.emplace_back((long double)sz[v]/W[v], v); }
    sort(ord.begin(), ord.end());
    ll t = 1; // arrival at child after one edge
    for (auto& [r, v] : ord){
        // children of u: walking down adds t to every node in subtree v
        F[u] += F[v] + t * W[v];
        t   += 2 * sz[v];
        sz[u] += sz[v]; W[u] += W[v];
    }
}

int main(){
    cin >> N >> mode;
    a.resize(N+1); ch.assign(N+1, {});
    for (int i = 1; i <= N; ++i) cin >> a[i];
    for (int i = 2; i <= N; ++i){ int p; cin >> p; ch[p].push_back(i); }
    sz.assign(N+1, 0); W.assign(N+1, 0); F.assign(N+1, 0);
    dfs(1);
    if (mode == 0) cout << 2*(N-1) << ' ' << F[1] << '\n';
    else {
        // T=1: choose any node to end at. Editorial: per subtree, drop the return walk
        // along the optimal terminal path; full code in editorial.
        cout << "[stop-path optimisation — see editorial]\n"; // [verify]
    }
}

Pitfalls

Problem 3 · Piling Papers

Official problem (cpid=1307)

Statement (paraphrased)

N papers each bear a digit ai ∈ {1..9}. For each of Q queries (l, r), consider every way to walk through papers l..r left-to-right and for each paper choose to push it on top of the stack, push it on the bottom of the stack, or skip it. The final stack, read top→bottom, forms a number (possibly empty / treated as 0). Count, mod 109+7, how many of the 3r−l+1 ways yield a number in [A, B].

Constraints

Key idea

Count(≤X) − Count(≤A−1). To count(≤X), fix the final length L (1..min(N, |X|)+1) — the answer of length < |X| is "any arrangement of L digits", count by interval DP. For length = |X|, do digit DP comparing prefix-of-stack to X with a tight/loose flag while sweeping the source papers left-to-right and choosing top/bottom/skip. State f[l][r][tight] = ways to build a stack matching X's prefix of length (already matched) from papers l..r. Transitions: append al to bottom (if equal-or-less to X's next digit), prepend ar to top, or skip.

Complexity target

O(N3) precompute + O(N) per query, or O(N3 log B) per side; comfortably under 2 s for N=300, Q=5·104.

C++ reference solution

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

// Count(L, l, r) = # ways to use papers l..r choosing top/bottom/skip ending with
// stack of length exactly L (no upper bound on value). Closed form: C(r-l+1, L) * 2^L * L! / L!
// = C(r-l+1, L) * 2^L  (each chosen paper goes either to top or bottom; order in stack determined
// by traversal order, with 2 choices per chosen position). We additionally multiply by 1 for each
// skipped paper.
// Real ≤X count needs digit-DP; skeleton below shows the framework.

int N, Q;
int a[305];
long long A, B;

int main(){
    cin >> N >> A >> B >> Q;
    for (int i = 1; i <= N; ++i) cin >> a[i];
    auto countLE = [&](long long X, int l, int r) -> long long {
        if (X < 0) return 0;
        // digit-DP over (l, r) interval picking top/bottom/skip to match prefix of X.
        // Implementation omitted for brevity — see editorial.
        return 0; // [verify]
    };
    while (Q--){
        int l, r; cin >> l >> r;
        long long ans = (countLE(B, l, r) - countLE(A-1, l, r) + MOD) % MOD;
        cout << ans << '\n';
    }
}

Pitfalls