U USACO Prep

2022 US Open · Gold

← Back to 2022 US Open · Official results page

Three Gold problems. G1 is a 2D matching problem that collapses to a 1D sweep after the right coordinate change, G2 is a counting-distinct-expressions DP modulo a prime, and G3 is a clever interval-bound tree DP where the answer is the smallest gap that survives a feasibility check.

Paraphrase warning. Statements here are summarized for my notes. Read the official problem on usaco.org before coding. Each problem links to the canonical statement.

G1 · Apple Catching

Official statement (cpid=1233)

Statement (paraphrase)

Events on a time × location plane: a cow event introduces some cows at (t, x), an apple event drops some apples at (t, x). A cow at (t_c, x_c) can catch an apple at (t_a, x_a) iff t_a ≥ t_c and |x_a − x_c| ≤ t_a − t_c. Each cow catches at most one apple, each apple is caught by at most one cow. Maximize the total apples caught.

Constraints

Key idea

The cone condition |x_a − x_c| ≤ t_a − t_c becomes a box after the 45° rotation u = t + x, v = t − x. Then a cow at (u_c, v_c) can catch an apple at (u_a, v_a) iff u_a ≥ u_c AND v_a ≥ v_c. Classical greedy bipartite matching: sort all events by u (with apples after cows on ties). Sweep, maintain a multiset of available cows keyed by v. For each apple, match it to the available cow with the largest v ≤ v_apple (the most "endangered" cow). Multiply by per-event quantities along the way.

Complexity

O(N log N) with a multiset / std::map keyed by v.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    // Event tuple: (u, v, isApple, count). Sort by u ascending; cows (isApple=0) before apples on tie
    // so that an apple at the same u can match a cow with the same u.
    vector<tuple<long long, long long, int, long long>> ev(N);
    for (int i = 0; i < N; i++) {
        int type; long long t, x, c; cin >> type >> t >> x >> c;
        long long u = t + x, v = t - x;
        ev[i] = {u, v, type == 2 ? 1 : 0, c};
    }
    sort(ev.begin(), ev.end(), [](auto& a, auto& b) {
        if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
        return get<2>(a) < get<2>(b); // cow (0) before apple (1)
    });

    // Available cows keyed by v -> remaining count.
    map<long long, long long> cows;
    long long caught = 0;
    for (auto& [u, v, isApple, cnt] : ev) {
        if (!isApple) {
            cows[v] += cnt;
        } else {
            // Greedy: match this apple group to cows with largest v <= v_apple, working downward.
            long long need = cnt;
            auto it = cows.upper_bound(v);
            while (need > 0 && it != cows.begin()) {
                --it;
                long long take = min(need, it->second);
                caught += take;
                need -= take;
                it->second -= take;
                if (it->second == 0) it = cows.erase(it);
            }
        }
    }
    cout << caught << "\n";
}

Pitfalls

G2 · Pair Programming

Official statement (cpid=1234)

Statement (paraphrase)

Two programs of length N each — every instruction is either "×d" (multiply running value by digit d ∈ {0..9}) or "+s" (add variable s; all variable names are distinct). Count, modulo 10⁹+7, the number of distinct symbolic expressions obtainable by interleaving the two programs in any of the C(2N, N) orderings and applying them to the running value starting from 0.

Constraints

Key idea

Two interleavings give the same expression iff their sequence of "×d" digits with the embedded variable additions match symbolically. The current running value resets to 0 whenever a "×0" appears; multiplying by 1 is a no-op that doesn't change the symbol; and adding distinct named variables in different orders gives the same expression (because of commutativity of addition over distinct variables — they're formal symbols, but the editorial's canonical form sums symmetrically). The DP f[i][j] = number of distinct prefix-expressions after consuming i of program A and j of program B, with careful "deduplication" rules at every ×0, ×1, and noun-add step.

The deduplication is the heart of the problem: when both programs' next instructions are interchangeable (both adds, or both ×1), the two transitions f[i+1][j] and f[i][j+1] would double-count, so subtract one. The editorial gives the exact inclusion–exclusion.

Complexity

O(N²) per test case with an N² table; with N ≤ 2000 sum, fits easily.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<string> A(N), B(N);
        for (auto& x : A) cin >> x;
        for (auto& x : B) cin >> x;

        // dp[i][j] = number of distinct expressions after consuming prefix A[0..i) and B[0..j).
        vector dp(N + 1, vector<long long>(N + 1, 0));
        dp[0][0] = 1;
        auto isMulZero = [](const string& s) { return s == "*0"; };
        auto isMulOne  = [](const string& s) { return s == "*1"; };
        auto isAdd     = [](const string& s) { return s[0] == '+'; };

        for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) {
            if (!dp[i][j]) continue;
            long long cur = dp[i][j];
            // Try taking next A-instr (if any).
            if (i < N) (dp[i + 1][j] += cur) %= MOD;
            if (j < N) (dp[i][j + 1] += cur) %= MOD;
            // Dedup: if both next moves yield equivalent expressions, subtract once.
            if (i < N && j < N) {
                bool same = false;
                if (isMulZero(A[i]) && isMulZero(B[j])) same = true; // both reset
                else if (isMulOne(A[i]) && isMulOne(B[j])) same = true; // both no-ops
                else if (isAdd(A[i]) && isAdd(B[j])) same = true; // commutes
                if (same) (dp[i + 1][j + 1] += MOD - cur) %= MOD; // remove the overcount
            }
        }
        // Standard correction: dp[N][N] currently counts ordered interleavings minus dup adjustments;
        // the editorial's final answer is dp[N][N]. (Refer to USACO editorial for exact recurrence.) [verify]
        cout << dp[N][N] << "\n";
    }
}

Pitfalls

G3 · Balancing a Tree

Official statement (cpid=1235)

Statement (paraphrase)

Rooted tree of N nodes, each with bounds l_i ≤ s_i ≤ r_i. Assign integer s_i in those bounds to minimize the maximum |s_u − s_v| over ancestor–descendant pairs (u, v). Output that minimum; when a flag B = 1, also output a valid assignment.

Constraints

Key idea

Binary search on the answer D. For a candidate D, propagate feasibility top-down: at each node the set of legal values is an interval, and the constraint "|s_u − s_v| ≤ D for every ancestor v" is equivalent to "s_u lies within distance D of every ancestor's chosen value." Since each subtree-root's interval [l, r] intersected with [lastVal − D, lastVal + D] is itself an interval, do a DFS that carries down the running interval intersect; for ancestor–descendant pair check it suffices to track the intersection of [l_anc − D, r_anc + D] type windows down the path — but the simpler complete approach is to do an interval-propagation DP per node (push min/max constraints both ways across the path). At the end, if every node has a non-empty feasible interval, D works.

Complexity

O(N log(maxR)) per test — ~30·N. With sum N ≤ 10⁵, well under 1 s.

Reference C++

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

int N; vector<vector<int>> ch; vector<long long> L, R;
vector<long long> fL, fR; // feasible interval after pushing down
bool feasible(long long D, int u, long long lo, long long hi) {
    // Intersect node bounds with [lo, hi].
    long long a = max(L[u], lo), b = min(R[u], hi);
    if (a > b) return false;
    fL[u] = a; fR[u] = b;
    // Descendants must lie within D of every ancestor; pushing the tightest window down works
    // because [a, b] - D, [a, b] + D widens per step but stays an interval per node.
    for (int v : ch[u])
        if (!feasible(D, v, max(lo, a) - D, min(hi, b) + D)) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int B; cin >> N >> B;
        ch.assign(N + 1, {}); L.assign(N + 1, 0); R.assign(N + 1, 0);
        fL.assign(N + 1, 0); fR.assign(N + 1, 0);
        for (int i = 2; i <= N; i++) { int p; cin >> p; ch[p].push_back(i); }
        for (int i = 1; i <= N; i++) cin >> L[i] >> R[i];

        long long lo = 0, hi = 1'000'000'000LL, ans = hi;
        while (lo <= hi) {
            long long mid = (lo + hi) / 2;
            if (feasible(mid, 1, 0, 2'000'000'000LL)) { ans = mid; hi = mid - 1; }
            else lo = mid + 1;
        }
        cout << ans << "\n";
        if (B) {
            // Recompute feasible with D = ans, then DFS picking s_u = fL[u] (any value in [fL,fR] works
            // as long as descendants get appropriately adjusted; greedy "take the low end" then re-intersect children).
            feasible(ans, 1, 0, 2'000'000'000LL);
            vector<long long> s(N + 1, 0);
            function<void(int, long long, long long)> assign = [&](int u, long long lo2, long long hi2) {
                long long val = max(fL[u], lo2);
                val = min(val, min(fR[u], hi2));
                s[u] = val;
                for (int v : ch[u]) assign(v, val - ans, val + ans);
            };
            assign(1, 0, 2'000'000'000LL);
            for (int i = 1; i <= N; i++) cout << s[i] << " \n"[i == N];
        }
    }
}

Pitfalls