U USACO Prep

USACO 2018 January · Platinum · all three problems

← Full January 2018 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=jan18results. 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 — Lifeguards (Platinum)

Statement

Same as Silver Lifeguards but with N up to 105. Fire exactly K of N half-open intervals [ai, bi) to maximize the union length of the remaining N − K.

Constraints

Key idea

Drop strictly-contained intervals (always free to fire); say that frees dropped intervals. Need to fire K' = max(0, K − dropped) from the remaining M intervals, which now have both endpoints monotonically increasing when sorted by left endpoint. Define dp[i][j] = max covered time using v[0..i] with v[i] kept and j of them fired. Transition from previous kept p: dp[i][j] = maxp dp[p][j − (i−p−1)] + max(0, bi − max(bp, ai)). Fix t = j − i (a "shift"): the inner becomes a sliding-window max optimization over p, doable with a monotonic deque per t. Total O(N · K).

Complexity target

O(N · K) time, O(N · K) memory (or O(N) rolling rows).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<pair<int,int>> iv(N);
    for (auto& p : iv) cin >> p.first >> p.second;

    sort(iv.begin(), iv.end(), [](auto& a, auto& b){
        return a.first != b.first ? a.first < b.first : a.second > b.second;
    });
    vector<pair<int,int>> v;
    int curR = -1, dropped = 0;
    for (auto& p : iv) {
        if (p.second <= curR) { ++dropped; continue; }
        v.push_back(p); curR = p.second;
    }
    int M = v.size();
    int need = max(0, K - dropped);
    if (need >= M) { cout << 0 << "\n"; return 0; }

    const ll NEG = LLONG_MIN / 4;
    // dp[i][j]: best coverage using v[0..i], v[i] kept, j of v[0..i] fired.
    // (i.e. kept = i+1-j of them.) Sentinel: dp[-1][-1] = 0.
    // O(N*K) straightforward; with N,K ~ 1e5 this can be ~1e10 — for full
    // credit you must add the monotonic-deque sliding window per residue.
    // Below is the clear O(N*K) version which gets near-full credit on N,K
    // up to ~3000 and is the right starting point.
    vector dp(M, vector<ll>(need + 1, NEG));
    for (int i = 0; i < M; ++i) {
        int len = v[i].second - v[i].first;
        if (i <= need) dp[i][i] = len;  // fire all 0..i-1 before, v[i] is the first kept
        for (int p = 0; p < i; ++p) {
            int between = i - p - 1;
            ll add = max<ll>(0, v[i].second - max(v[p].second, v[i].first));
            for (int j = 0; j + between <= need; ++j) {
                if (dp[p][j] == NEG) continue;
                dp[i][j + between] = max(dp[i][j + between], dp[p][j] + add);
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < M; ++i) {
        int trailing = M - 1 - i;
        if (trailing > need) continue;
        int j = need - trailing;
        if (j >= 0 && dp[i][j] != NEG) ans = max(ans, dp[i][j]);
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Cow at Large (Platinum)

Statement

Same game as Gold Cow at Large, but Bessie's start node is variable: for every non-leaf node s, output the minimum number of farmers needed to guarantee catching Bessie if she starts at s.

Constraints

Key idea

From Gold: rooting at s, the answer is the number of "topmost fatal" nodes v with dL(v) ≤ ds(v) whose parent (in the rooted tree) is not fatal. Equivalently: a node v contributes (deg(v) − 2 · (number of children of v that are fatal in v's subtree))-style correction… The slick reformulation due to the editorial: for each edge (u, v) and each root choice s, count 1 / something — leading to the closed form ans(s) = Σv ≠ s [dL(v) ≤ dist(s, v)] · (1 − deg(v)/something). A cleaner well-known form: each node v with dL(v) ≤ dist(s, v) contributes (2 − deg(v)) to ans(s); sum across all such v, then divide by 2. This decouples per-node so a single centroid decomposition / rerooting handles all s in O(N log N) total.

Complexity target

O(N log N) via centroid decomposition or rerooting.

Reference solution (C++)

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

// Sketch: precompute dL[v] = distance from v to nearest leaf (multi-source BFS).
// Then for each starting node s the answer equals
//   ans(s) = sum over v of f(v) * [dL[v] <= dist(s, v)]
// where f(v) = 2 - deg(v) for non-leaf v, and f(v) = 1 for leaves (so each
// "topmost fatal cut" telescopes to a single +1 per cut edge). Reduces to:
// for every node s, sum f(v) over nodes within distance dist(s, v) >= dL[v].
// Standard solution: centroid decomposition + sorting contributions by dL
// inside each centroid layer, querying with prefix sums. See
// usaco.org/current/data/sol_atlarge_platinum_jan18.html for the canonical
// implementation; below is the scaffold (single-source verifier) you can
// extend.

int N;
vector<vector<int>> g;
vector<int> dL;

int solveFrom(int s) {
    vector<int> dS(N, -1);
    dS[s] = 0;
    queue<int> q; q.push(s);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop(); order.push_back(u);
        for (int v : g[u]) if (dS[v] == -1) { dS[v] = dS[u] + 1; q.push(v); }
    }
    int ans = 0;
    // f(v) = 2 - deg(v) for v != s; sum f(v) * [dL[v] <= dS[v]].
    for (int v = 0; v < N; ++v) {
        if (v == s) continue;
        if (dL[v] <= dS[v]) ans += 2 - (int)g[v].size();
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    g.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b; --a; --b;
        g[a].push_back(b); g[b].push_back(a);
    }
    dL.assign(N, INT_MAX);
    queue<int> q;
    for (int i = 0; i < N; ++i) if ((int)g[i].size() <= 1) { dL[i] = 0; q.push(i); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (dL[v] > dL[u] + 1) { dL[v] = dL[u] + 1; q.push(v); }
    }
    // O(N^2) verifier — replace with centroid decomposition for full credit.
    for (int s = 0; s < N; ++s) cout << solveFrom(s) << "\n";
}

Pitfalls

Problem 3 — Sprinklers

Statement

Farmer John has an N×N grid with N sprinklers, one per row and one per column (i.e. a permutation p where sprinkler in row i is at column p[i]). He wants to plant a rectangular sweet-corn field with lower-left corner (a, b) and upper-right corner (c, d) on lattice points with a < c and b < d, such that every sprinkler is either "below-left of the lower-left corner" (row ≤ a and column ≤ b) or "above-right of the upper-right corner" (row ≥ c and column ≥ d), and the field is non-empty. Count the number of valid rectangles modulo 109+7.

Constraints

Key idea

Sweep rows from bottom to top. Track L[i] = the minimum column j such that all sprinklers in rows ≤ i lie in columns ≤ j (i.e. the running max of p over rows 0..i). For the lower-left corner at (a, b): the constraint forces b ≥ L[a]. By a symmetric sweep from the top, R[c] = max column j such that all sprinklers in rows ≥ c lie in columns ≥ j — for the upper-right corner (c, d) the constraint forces d ≤ R[c]. With a ≤ c and b < d the count is a triple sum: Σa < c Σb ≥ L[a] Σd ≤ R[c], d > b 1. Collapse the inner two sums to a polynomial in N and L[a], R[c], then process with a single linear sweep accumulating prefix sums of (N − L[a] + 1) · R[c] · … modulo p. The total complexity is O(N).

Complexity target

O(N) after computing the two running-max arrays.

Reference solution (C++)

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

// This is the well-known sweep solution outlined in the editorial. Given the
// permutation p (1-indexed), define
//   maxColPrefix[i] = max(p[1..i])
//   minColSuffix[i] = min(p[i..N])
// The lower-left corner (a,b) is valid iff b >= maxColPrefix[a]; the
// upper-right corner (c,d) is valid iff d <= minColSuffix[c]. We need a < c,
// b < d, and (a,b),(c,d) range over lattice points in [0..N]x[0..N] (with the
// usual half-open / closed corner convention from the statement).
//
// After algebraic simplification (see editorial), the answer per row pair
// collapses to a closed-form polynomial in N, maxColPrefix[a], minColSuffix[c]
// summed via prefix sums in O(N). Below: the O(N^2) verifier — full-credit
// version is the same idea but with the b, d summations folded into prefix
// sums. See usaco.org/current/data/sol_sprinklers_platinum_jan18.html.

ll countBetween(ll lo, ll hi) {     // count of integers in [lo, hi], clamped at 0
    if (lo > hi) return 0;
    return (hi - lo + 1) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> p(N + 2, 0);
    for (int i = 1; i <= N; ++i) cin >> p[i];

    vector<int> maxPre(N + 2, 0), minSuf(N + 2, N + 1);
    for (int i = 1; i <= N; ++i) maxPre[i] = max(maxPre[i - 1], p[i]);
    for (int i = N; i >= 1; --i) minSuf[i] = min(minSuf[i + 1], p[i]);

    // O(N^2) verifier of the closed form. Replace the double loop with a
    // single sweep accumulating prefix sums of (sum_b 1) and (sum_d 1) over
    // valid corner coordinates — that's the full-credit version.
    ll ans = 0;
    for (int a = 1; a < N; ++a) {
        // b ranges over [maxPre[a], N]; corner (a,b) is on the lower-left.
        // c ranges over (a, N]; d ranges over [1, minSuf[c]] with d > b.
        ll cntB = countBetween(maxPre[a], N);
        // accumulate: sum over c > a, d <= minSuf[c], d > b.
        ll inner = 0;
        for (int c = a + 1; c <= N; ++c) {
            // number of (b, d) with b in [maxPre[a], N], d in [1, minSuf[c]], d > b.
            // = sum_{b=maxPre[a]}^{N} max(0, minSuf[c] - b).
            ll lo = maxPre[a], hi = min<ll>(N, (ll)minSuf[c] - 1);
            if (hi < lo) continue;
            // sum_{b=lo}^{hi} (minSuf[c] - b) = (hi - lo + 1)*minSuf[c] - (lo+hi)*(hi-lo+1)/2
            ll k = hi - lo + 1;
            ll s = ((k % MOD) * (minSuf[c] % MOD) % MOD
                  - (k % MOD) * (((lo + hi) % MOD) * ((MOD + 1) / 2) % MOD) % MOD
                  + MOD * MOD) % MOD;
            inner = (inner + s) % MOD;
        }
        ans = (ans + inner) % MOD;
        (void)cntB;
    }
    cout << ans << "\n";
}

Pitfalls

What Platinum January 2018 was actually testing