U USACO Prep

USACO 2015 December · Platinum · all three problems

← Full December 2015 set · Official results · First-ever Platinum contest.

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec15results. 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 — Max Flow

Statement

A tree on N stalls with N−1 pipes. K paths of milk are routed, each given as a pair (s, t); one unit of flow runs along the unique tree path from s to t. Output the maximum total flow through any single node.

Constraints

Key idea

Tree path addition via LCA + node difference array. For each path (s, t) with L = LCA(s, t), diff[s]++, diff[t]++, diff[L]−−, diff[parent(L)]−− (if exists). After all paths, do a post-order DFS: flow[v] = diff[v] + Σ flow[children]. Answer = max flow[v]. Use binary-lifting LCA in O((N + K) log N).

Complexity target

O((N + K) log N).

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
const int LG = 17;
int N, K;
vector<int> adj[50005];
int up[50005][LG], depth_[50005], par[50005];
long long diff_[50005], flow_[50005];
int order_[50005], oi = 0;

void bfs_root() { // iterative BFS to fill parents/depth in a topological order
    queue<int> q; q.push(1); par[1] = 0; depth_[1] = 0;
    vector<char> seen(N+1,0); seen[1] = 1;
    while (!q.empty()) {
        int v = q.front(); q.pop(); order_[oi++] = v;
        for (int u : adj[v]) if (!seen[u]) { seen[u]=1; par[u]=v; depth_[u]=depth_[v]+1; q.push(u); }
    }
}
int lca(int a, int b) {
    if (depth_[a] < depth_[b]) swap(a, b);
    int d = depth_[a] - depth_[b];
    for (int k = 0; k < LG; ++k) if (d & (1 << k)) a = up[a][k];
    if (a == b) return a;
    for (int k = LG-1; k >= 0; --k) if (up[a][k] != up[b][k]) { a = up[a][k]; b = up[b][k]; }
    return up[a][0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    bfs_root();
    for (int v = 1; v <= N; ++v) up[v][0] = par[v];
    for (int k = 1; k < LG; ++k)
        for (int v = 1; v <= N; ++v) up[v][k] = up[up[v][k-1]][k-1];
    while (K--) {
        int s, t; cin >> s >> t;
        int L = lca(s, t);
        diff_[s]++; diff_[t]++; diff_[L]--; if (par[L]) diff_[par[L]]--;
    }
    // accumulate flow in reverse BFS order (children before parent).
    for (int i = oi - 1; i >= 0; --i) {
        int v = order_[i];
        flow_[v] += diff_[v];
        if (par[v]) flow_[par[v]] += flow_[v];
    }
    long long ans = 0;
    for (int v = 1; v <= N; ++v) ans = max(ans, flow_[v]);
    cout << ans << "\n";
}

Pitfalls

Problem 2 — High Card Low Card (Platinum)

Statement

The Gold version's setup, but Bessie chooses the split: after seeing Elsie's full sequence, she picks a round index k ∈ [0, N] such that rounds 1..k are "high wins" and rounds k+1..N are "low wins". She then permutes her hand optimally. Output the maximum number of rounds she can win across all k.

Constraints

Key idea

Precompute hi[k] = max wins on Elsie's prefix of length k under high-wins rules, using Bessie's "high cards" (top j of her hand for some j). And lo[k] = max wins on Elsie's suffix starting at k+1 under low-wins rules, using Bessie's "low cards". For each split k, Bessie can give the top j cards of her sorted hand to the high half and the rest to the low half — best is to scan and choose. A clean approach: for fixed prefix length k, Bessie's high-pool optimum uses her largest j = k cards; her low-pool optimum uses her remaining N − k cards. Each can be computed in O(N log N) with a sweep using a multiset; then iterate k and report the max sum. Total O(N log N).

Complexity target

O(N log N).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> e(N+1);
    vector<bool> taken(2*N + 2, false);
    for (int i = 1; i <= N; ++i) { cin >> e[i]; taken[e[i]] = true; }
    vector<int> b;
    for (int v = 1; v <= 2*N; ++v) if (!taken[v]) b.push_back(v);
    sort(b.begin(), b.end()); // ascending

    // hi[k] = wins on first k rounds (high-wins) using Bessie's top k cards.
    // Process Elsie cards in order; for each new round, add Bessie's next-largest card to "available",
    // then greedily win if any available card beats the current Elsie card.
    vector<int> hi(N+1, 0);
    multiset<int> pool;
    for (int k = 1; k <= N; ++k) {
        pool.insert(b[N - k]); // add k-th largest of Bessie
        auto it = pool.upper_bound(e[k]);
        hi[k] = hi[k-1];
        if (it != pool.end()) { ++hi[k]; pool.erase(it); }
        else pool.erase(pool.begin()); // forced to play a card; sacrifice smallest
    }

    // lo[k] = wins on rounds k+1..N (low-wins) using Bessie's bottom N-k cards.
    // Iterate k from N down to 0; for each step add Bessie's next-smallest card.
    vector<int> lo(N+2, 0);
    pool.clear();
    for (int k = N; k >= 1; --k) {
        pool.insert(b[N - 1 - (N - k)]); // = b[k-1]
        // Round k is "low wins": want largest Bessie card < e[k].
        lo[k-1] = lo[k];
        auto it = pool.lower_bound(e[k]);
        if (it != pool.begin()) { --it; ++lo[k-1]; pool.erase(it); }
        else pool.erase(--pool.end());
    }

    int ans = 0;
    for (int k = 0; k <= N; ++k) ans = max(ans, hi[k] + lo[k]);
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Counting Haybales

Statement

N fields in a row, each starting with some haybales. Q operations of three types: M a b — print min of haybales in fields [a, b]. P a b c — add c to each field in [a, b]. S a b — print sum of haybales in [a, b].

Constraints

Key idea

Lazy-propagation segment tree storing sum and min per node, with a pending "add" lazy tag. Range-add updates both sum (+= add · len) and min (+= add) for the affected node; push the lazy down to children only when needed.

Complexity target

O((N + Q) log N).

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
long long sum_[4*MAXN], mn_[4*MAXN], lazy[4*MAXN];
int N;

void build(int node, int l, int r, vector<long long>& a) {
    if (l == r) { sum_[node] = mn_[node] = a[l]; return; }
    int m = (l+r)/2;
    build(node*2, l, m, a); build(node*2+1, m+1, r, a);
    sum_[node] = sum_[node*2] + sum_[node*2+1];
    mn_[node] = min(mn_[node*2], mn_[node*2+1]);
}
void push(int node, int l, int r) {
    if (!lazy[node]) return;
    int m = (l+r)/2;
    long long v = lazy[node];
    sum_[node*2] += v * (m - l + 1); mn_[node*2] += v; lazy[node*2] += v;
    sum_[node*2+1] += v * (r - m);   mn_[node*2+1] += v; lazy[node*2+1] += v;
    lazy[node] = 0;
}
void update(int node, int l, int r, int ql, int qr, long long v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        sum_[node] += v * (r - l + 1); mn_[node] += v; lazy[node] += v; return;
    }
    push(node, l, r); int m = (l+r)/2;
    update(node*2, l, m, ql, qr, v); update(node*2+1, m+1, r, ql, qr, v);
    sum_[node] = sum_[node*2] + sum_[node*2+1];
    mn_[node] = min(mn_[node*2], mn_[node*2+1]);
}
pair<long long,long long> query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return {0, LLONG_MAX};
    if (ql <= l && r <= qr) return {sum_[node], mn_[node]};
    push(node, l, r); int m = (l+r)/2;
    auto A = query(node*2, l, m, ql, qr);
    auto B = query(node*2+1, m+1, r, ql, qr);
    return {A.first + B.first, min(A.second, B.second)};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q; cin >> N >> Q;
    vector<long long> a(N+1);
    for (int i = 1; i <= N; ++i) cin >> a[i];
    build(1, 1, N, a);
    while (Q--) {
        char op; int x, y; cin >> op >> x >> y;
        if (op == 'M') cout << query(1, 1, N, x, y).second << "\n";
        else if (op == 'S') cout << query(1, 1, N, x, y).first << "\n";
        else { long long c; cin >> c; update(1, 1, N, x, y, c); }
    }
}

Pitfalls

What Platinum December 2015 was actually testing