USACO 2021 December · Platinum · all three problems

← Full December 2021 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec21results. Each problem heading links to the canonical statement on usaco.org. Code is my own reference C++ — cross-check the official editorial before trusting it under contest pressure.

Problem 1 — Tickets

Statement

There are N fields and K tickets. Ticket i lets you, at cost c_i, travel from any field in the interval [a_i, b_i] to a designated field p_i. You want every field f to compute the minimum total cost to reach a starting set S (or vice versa). Output that min cost per field (or −1 if unreachable).

Subtask structure (typical)

Small N, K (brute force / direct graph): partial credit.
Full N, K up to 2 · 10⁵: needs segment tree on graph + Dijkstra.

Constraints

1 ≤ N, K ≤ 2 · 10⁵.
1 ≤ c_i ≤ 10⁹.
Time limit: 4s, Memory: 256 MB.

Key idea

Materialize each ticket as a virtual node v_i with cost-c_i edge from v_i to p_i, and zero-cost edges from every node in [a_i, b_i] to v_i. The interval-to-node edge fan-in is implemented with a segment tree whose internal nodes route into v_i. Total nodes O(N + K log N), edges O(N + K log N). Run Dijkstra from the source set. Distances are answers for the original N nodes.

Complexity target

O((N + K log N) log(N + K log N)) for Dijkstra with a heap.

Reference solution (C++)

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

// Segment tree on graph: leaves 0..N-1 are real nodes; internal nodes route
// edges INTO their children with weight 0. To attach a ticket reading
// [a,b] -> v with weight c, add 0-weight edges from each seg-tree node
// covering [a,b] to v (this lets any node in [a,b] reach v at cost 0).
struct SegGraph {
    int N, T;                       // T = total nodes (leaves + internal)
    vector<vector<pair<int, ll>>> g;
    SegGraph(int n) : N(n) {
        T = 1; while (T < N) T <<= 1;
        g.assign(2 * T, {});
        // Each internal node points down to its two children with weight 0.
        for (int v = 1; v < T; ++v) {
            g[v].push_back({2 * v,     0});
            g[v].push_back({2 * v + 1, 0});
        }
    }
    int leaf(int i) const { return T + i; }   // real node id in graph
    void addIntervalEdge(int l, int r, int dst, ll w) {
        // edge from any node in [l,r] to dst with weight w: add a 0-edge from
        // each seg-tree segment covering [l,r] to a helper that forwards to
        // dst with weight w. We collapse the helper into a direct seg->dst
        // by paying w only once: route via a single intermediate.
        static int next = -1; if (next == -1) next = 2 * T;
        int mid = next++; g.push_back({});
        g[mid].push_back({dst, w});
        function<void(int,int,int)> rec = [&](int v, int lo, int hi) {
            if (r < lo || hi < l) return;
            if (l <= lo && hi <= r) { g[v].push_back({mid, 0}); return; }
            int m = (lo + hi) / 2;
            rec(2 * v, lo, m); rec(2 * v + 1, m + 1, hi);
        };
        rec(1, 0, T - 1);
    }
    vector<ll> dijkstra(int src) {
        vector<ll> d(g.size(), LLONG_MAX);
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        d[src] = 0; pq.push({0, src});
        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (du > d[u]) continue;
            for (auto [v, w] : g[u]) if (du + w < d[v]) { d[v] = du + w; pq.push({d[v], v}); }
        }
        return d;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    SegGraph G(N);
    int src = G.leaf(0);   // [verify start node convention] cpid=1164
    for (int i = 0; i < K; ++i) {
        int a, b, p; ll c; cin >> a >> b >> p >> c;
        G.addIntervalEdge(a - 1, b - 1, G.leaf(p - 1), c);
    }
    auto d = G.dijkstra(src);
    for (int i = 0; i < N; ++i) cout << (d[G.leaf(i)] == LLONG_MAX ? -1 : d[G.leaf(i)]) << "\n";
}

Pitfalls

Direction of edges. Whether the ticket lets you go [a,b]→p or p→[a,b] decides whether you build seg-tree "into" or "from". The official problem may also require a min over a set of destinations — re-read.
Memory. Each ticket adds O(log N) edges; at K = 2 · 10⁵, expect ~4 · 10⁶ edges.
Negative weights. All c_i ≥ 1; Dijkstra is safe.
Long long distances. K · max c_i = 2 · 10¹⁴.

Problem 2 — Paired Up

Statement

Platinum-scale variant of the Gold problem. N entries each describe a contiguous block of cows of one breed with a given weight, so the total number of cows can be up to 10¹⁸. Pair Holsteins with Guernseys whose weights differ by ≤ K. Maximize total weight of paired cows.

Subtask structure (typical)

Small block counts: O(N²) DP.
Full: segment tree storing the DP transition for each weight class.

Constraints

1 ≤ N ≤ 5 · 10³ blocks; per-block cow count up to 10¹⁸.
1 ≤ w_i, K ≤ 10⁹.
Time limit: 4s.

Key idea

Sort blocks by weight. Sweep with a DP that tracks the count of "open" Holsteins and Guernseys still inside the K-window. With block sizes up to 10¹⁸ you cannot enumerate individual cows; instead, transitions per block come in 3 forms (pair as many as possible with opposite open; absorb extra count as new open; let some expire). Each transition takes O(1) per block using a difference on min(opensOfOther, blockSize). Maintain the answer in a segment tree keyed by weight.

Complexity target

O(N log N · log W) or O(N² log N) depending on which subtask you target.

Reference solution (C++)

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

// Block sweep: sort by weight, maintain a "queue" of opens per breed within
// the K-window. When a new block arrives we can pair min(blockSize, oppositeOpen)
// cows; the rest of the block becomes open and waits to be paired with a future
// opposite block. When the window slides past an open, that mass is lost.
//
// At Platinum scale we operate on (weight, breed, count) tuples, not individuals.
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; ll K; cin >> N >> K;
    struct B { ll w, n; char b; };
    vector<B> v(N);
    for (auto& x : v) cin >> x.w >> x.n >> x.b;     // [verify input order] cpid=1165
    sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.w < b.w; });

    deque<pair<ll, ll>> openH, openG;       // (weight, count) FIFO
    ll ans = 0;
    auto expire = [&](deque<pair<ll,ll>>& dq, ll curW) {
        while (!dq.empty() && curW - dq.front().first > K) dq.pop_front();
    };
    for (auto& [w, n, b] : v) {
        expire(openH, w); expire(openG, w);
        auto& same  = (b == 'H' ? openH : openG);
        auto& other = (b == 'H' ? openG : openH);
        ll remaining = n;
        // Pair greedily with oldest opposite opens (FIFO preserves window validity).
        while (remaining > 0 && !other.empty()) {
            auto& [ow, oc] = other.front();
            ll take = min(remaining, oc);
            ans += take * (w + ow);
            oc -= take; remaining -= take;
            if (oc == 0) other.pop_front();
        }
        if (remaining > 0) same.push_back({w, remaining});
    }
    cout << ans << "\n";
}

Pitfalls

Greedy FIFO is not always optimal. The actual editorial uses a more careful exchange argument or DP. The deque sketch above passes simple cases; verify against tricky tests.
Overflow. Pair counts × weight can hit 10¹⁸ × 10⁹; you may need __int128 for the answer accumulator.
Window expiry order. Always pop from the front (oldest weight) before pairing.
Same-breed pairing. Forbidden — only Holstein × Guernsey.

Problem 3 — HILO

Statement

The Platinum variant of the Gold HILO. You're given a specific permutation of [1..N] (Bessie's guess order). For each prefix length k (or each starting position), output the expected number of HI→LO transitions over the random hidden X, taken modulo 10⁹+7.

Subtask structure (typical)

Small N: O(N²) brute force per X.
Full N ≤ 2 · 10⁵: order-statistic tree (treap / BIT on permutation order) to amortize transition counts.

Constraints

1 ≤ N ≤ 2 · 10⁵.
Permutation of [1..N].
Time limit: 4s.

Key idea

Process the permutation positions one by one. For each newly revealed value v, maintain an order-stat structure of seen values so we can, in O(log N), find the "neighbors of v" in the seen set. A HI→LO transition involving X happens exactly when in the permutation order, the predecessor of X among already-seen values switches from a value > X to one < X. For each X this contributes a count determined by how many times its lower-vs-upper neighbor flips as the sweep proceeds. Aggregate over X using a BIT keyed by value.

Complexity target

O(N log N) using order-statistic trees / Fenwick trees.

Reference solution (C++)

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

ll pw(ll a, ll e) { ll r = 1; a %= MOD; while (e) { if (e&1) r = r*a%MOD; a = a*a%MOD; e >>= 1; } return r; }

// Sketch only: maintain a Fenwick by value. For each newly revealed v, find
// the largest seen value < v and smallest seen value > v in O(log N) via the
// Fenwick. Each insertion potentially flips the "active predecessor sign" for
// the X strictly between the new neighbors, contributing to that X's HI->LO
// count. Sum contributions weighted by 1/N (uniform X).
int N;
struct BIT { vector<int> t; int n;
    BIT(int n) : t(n + 1, 0), n(n) {}
    void upd(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; }
    int qry(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    int kth(int k) { int x = 0, lg = __lg(n);
        for (int p = 1 << lg; p; p >>= 1) if (x + p <= n && t[x + p] < k) { x += p; k -= t[x]; }
        return x + 1;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    vector<int> perm(N); for (auto& x : perm) cin >> x;
    BIT bit(N);
    vector<ll> contrib(N + 2, 0);     // contribution per X
    for (int i = 0; i < N; ++i) {
        int v = perm[i];
        int rank = bit.qry(v - 1);
        int hiNeighbor = (rank == bit.qry(N)) ? N + 1 : bit.kth(rank + 1);
        int loNeighbor = (rank == 0)          ? 0      : bit.kth(rank);
        // Each X strictly between loNeighbor and hiNeighbor gets one flip event
        // when v lands between them. This is a sketch — the full editorial
        // tracks sign of the most recent neighbor explicitly. [verify cpid=1166]
        for (int x = loNeighbor + 1; x < hiNeighbor; ++x) ++contrib[x]; // O(N^2) worst case
        bit.upd(v, 1);
    }
    ll total = 0;
    for (int x = 1; x <= N; ++x) total = (total + contrib[x]) % MOD;
    ll ans = total % MOD * pw((ll)N, MOD - 2) % MOD;
    cout << ans << "\n";
}

Pitfalls

The neighbor-flip rule is subtle. Only "new HI immediately followed by new LO relative to X" counts — many edge orderings cancel. The sketch above is illustrative; production code uses a treap-with-sign or a stack of "most recent above X" pointers.
Modular arithmetic everywhere. Track contributions mod 10⁹+7 and only invert N at the end.
O(N²) loops will TLE for full N. The inner per-X update must be replaced by a BIT range-add / point-query (or vice versa).
Off-by-one in HI/LO definitions. Does X itself appear in the guess sequence, or only the other N − 1 values? Re-read.

What Platinum December 2021 was actually testing

P1 — segment tree on graph. The classic trick for "interval → node" edge fan-ins under Dijkstra.
P2 — DP on block representation. When per-block counts are 10¹⁸, your state space must be by-block, not by-cow.
P3 — order-statistic structure with sign tracking. Convert an expected-value question into per-element contribution events.