U USACO Prep

2023 February Platinum · 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 · Hungry Cow (Platinum)

Official problem (cpid=1308)

Statement (paraphrased)

Same eating model as Bronze: Bessie eats one haybale per day if any is in stock. But now you process U updates of the form "on day d set delivery to b haybales" (overwriting any previous delivery on day d, or removing if b=0). After each update output the sum of days on which Bessie eats, mod 109+7.

Constraints

Key idea

Build an implicit segment tree over a compressed timeline of delivery days plus the open intervals between them. Each node stores: range length, total deliveries inside, count of "eaten days" already pinned, and the surplus (excess deliveries carried over the right boundary). Combining children l, r: surplus(l) flows into r's empty days first; eaten days = eaten(l) + eaten(r) + min(unfilled(r), surplus(l)), and the days summed are tracked via an extra field summing arithmetic progressions. Updates are O(log) on the implicit segtree. Sums of consecutive integers from a..b mod p use (a+b)(b−a+1)/2 mod p.

Complexity target

O(U log U) time, O(U log U) memory for the implicit segtree.

C++ reference solution

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

// Implicit segtree on compressed delivery-day coordinates.
// Each node holds: len, eaten_days_count, eaten_days_sum (mod p),
//                  surplus (haybales carried past the right end).
struct Node { ll len=0, cnt=0, sum=0, sur=0; };

ll arith(ll a, ll b){              // a + (a+1) + ... + b mod p
    ll k = (b - a + 1) % MOD;
    ll s = ((a + b) % MOD * (k % MOD)) % MOD;
    return s * inv2 % MOD;
}

Node merge(const Node& L, const Node& R, ll Lstart, ll Rstart){
    Node X;
    X.len = L.len + R.len;
    // Surplus from L spills into the unfilled portion of R.
    ll spill = min(L.sur, R.len - R.cnt);
    // Days newly eaten lie in R's unfilled left-most positions (greedy fill).
    // Tracking the exact day numbers requires storing R's "first-empty" position;
    // editorial uses a recursive lazy-spill traversal.
    X.cnt = L.cnt + R.cnt + spill;
    X.sum = (L.sum + R.sum) % MOD;  // R's newly-eaten day-sum patched during recursion
    X.sur = L.sur - spill + R.sur;
    return X;
}
// Full implementation omitted — Platinum editorial gives ~80 lines.
int main(){
    int U; cin >> U;
    inv2 = 500000004; // modular inverse of 2 mod 1e9+7
    // ... build implicit segtree, process updates, output total day-sum.
    // [verify] full impl in https://usaco.org/current/data/sol_prob3_platinum_feb23.html
    cout << 0 << '\n';
}

Pitfalls

Problem 2 · Problem Setting

Official problem (cpid=1309)

Statement (paraphrased)

FJ has N candidate problems and M test-solvers; each solver labels every problem "easy" (0) or "hard" (1). Each problem thus carries an M-bit signature. Choose an ordered subset (problemset) such that for no solver j does some later problem appear easy while some earlier one appears hard. Count ordered problemsets mod 109+7.

Constraints

Key idea

Each signature S ∈ {0,1}M defines an equivalence class. Within a class, problems are interchangeable, so a class of size c contributes Σk=0..c C(c,k) · k! permutations once you've decided to include k of them — but the ordering between classes must respect the partial order "S ⪯ T iff S OR T = T and S AND T = S" (S can come before T iff no solver j has Tj=0 while Sj=1). DP over subsets: g[mask] = number of valid orderings using exactly the classes whose signature is a subset of mask. SOS-style transition: g[mask] = Σ over S ⊆ mask, S a maximal element, g[mask − S] · (contribution of class S given how many we pick). 2M·M ≤ 2·107.

Complexity target

O(2M·M + N).

C++ reference solution

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

int main(){
    int N, M; cin >> N >> M;
    vector<int> cnt(1<<M, 0);
    for (int i = 0; i < N; ++i){
        string row; cin >> row;
        int s = 0;
        for (int j = 0; j < M; ++j) if (row[j] == 'H') s |= (1<<j);
        cnt[s]++;
    }
    // f[s] = number of nonempty ordered sequences using only classes that are subsets of s,
    // where every successive signature is ⊆ s and respects ⪯.
    // Transition: f[s] = sum over T ⊆ s, T != 0, of (ways to pick a nonempty ordered sequence
    // from class T) * f[s ^ (T's contribution)].
    // The editorial uses "fix the maximal element of the ordering."
    vector<ll> f(1<<M, 0); f[0] = 1;
    for (int s = 1; s < (1<<M); ++s){
        // For each bit j set in s, transition from s without j; details in editorial.
        // Sketch: iterate over subsets T of s containing only top-level elements.
        // (Real implementation is ~30 lines; this is a placeholder.) // [verify]
    }
    ll ans = (f[(1<<M)-1] - 1 + MOD) % MOD; // subtract empty problemset if needed
    cout << ans << '\n';
}

Pitfalls

Problem 3 · Watching Cowflix

Official problem (cpid=1310)

Statement (paraphrased)

On a tree of N nodes, a subset S of nodes is marked "viewing". Pay min cost so that the chosen connected-component cover of all viewing nodes consists of disjoint subtrees; each chosen component of size d costs d + k. For every k = 1..N, output the minimum total cost.

Constraints

Key idea

For fixed k, do a tree DP: dp[v][0/1] = min cost to cover all viewing nodes inside v's subtree, where 0 = v is not in any chosen component, 1 = v is in some component (and we will close or extend it upward). Answer for fixed k = min(dp[root][0], dp[root][1]+k). Naively O(N²). To handle all k, observe that the answer as a function of k is piecewise-linear concave: as k grows, the optimal number of components C* decreases. Use Aliens trick (binary search on the slope penalty) or smallish- to-large merging with sqrt-decomposition on k: solve for O(√N) representative k-values in O(N) each, plus a sub-N²·√ method splits over k ≤ √N (many components) and k > √N (few components). Editorial uses √N decomposition:

Total O(N · √N).

Complexity target

O(N · √N) or O(N log² N) with Aliens.

C++ reference solution

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

int N;
vector<vector<int>> adj;
vector<int> want;
vector<ll> dp0, dp1; // dp[v][0]: v not in chosen comp; dp[v][1]: v in chosen comp

ll Kfixed;
void dfs(int u, int par){
    // dp0[u]: u not in component — must satisfy want[u]==0
    // dp1[u]: u in component — counts u's size, must add Kfixed once when closed.
    ll d0 = (want[u] ? INF : 0);
    ll d1 = 1; // u itself
    for (int v : adj[u]) if (v != par){
        dfs(v, u);
        // child's best closed = min(dp0[v], dp1[v] + Kfixed)
        ll closed = min(dp0[v], dp1[v] + Kfixed);
        ll d0n = (d0 == INF ? INF : d0 + closed);
        // u in component: child either also-in (merge: dp1[v], same component) or closed
        ll d1n = d1 + min(dp1[v], closed);
        d0 = d0n; d1 = d1n;
    }
    dp0[u] = d0; dp1[u] = d1;
}

int main(){
    cin >> N;
    string s; cin >> s;
    want.assign(N+1, 0);
    for (int i = 1; i <= N; ++i) want[i] = (s[i-1] == '1');
    adj.assign(N+1, {});
    for (int i = 0; i < N-1; ++i){ int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); }
    dp0.assign(N+1, 0); dp1.assign(N+1, 0);
    for (int k = 1; k <= N; ++k){
        Kfixed = k;
        dfs(1, 0);
        cout << min(dp0[1], dp1[1] + Kfixed) << '\n';
    }
    // O(N^2) — fine for N=5000 subtask. Full N=2e5 needs √-decomposition or Aliens trick. [verify]
}

Pitfalls