U USACO Prep

2024 February Platinum · All three problems

← Back to Feb 2024 hub · Official results

Platinum is two divisions above me. These writeups are editorial-distilled notes, not original solves. Canonical statements at usaco.org.

Problem 1 · Lazy Cow

Official problem (cpid=1404)

Statement (paraphrased)

Bessie prepares test cases over consecutive minutes. Each minute she either rests, or spends 3a−1 energy to produce a fresh test cases. D demands arrive online: demand i requires that within the most recent mi minutes she will have produced at least bi test cases. After each demand is added to the set, output the minimum energy needed to satisfy every demand seen so far, mod 109+7.

Constraints

Key idea

Producing b cases in a window of m minutes uses minimum energy when b is spread as evenly as possible (because 3a−1 is convex). The optimal cost is a closed-form function f(m, b) = (b mod m) · 3⌈b/m⌉−1 + (m − b mod m) · 3⌊b/m⌉−1. Demands compose: the answer is the maximum over all relevant (m, b) "rate" constraints, which forms an upper envelope (convex hull trick over piecewise-exponential functions sorted by slope b/m). Maintain a Li-Chao-like structure on the slopes; each new demand either dominates older constraints or is dominated.

Complexity target

O(D log D · log MOD) for hull maintenance + modular exponentiation per query.

C++ reference solution

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

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

// f(m, b) in closed form mod MOD.
ll fcost(ll m, ll b){
    ll q = b / m, r = b % m;
    ll part_hi = r % MOD * mpow(3, q, MOD) % MOD;          // q exponent for the (b%m) high buckets
    ll part_lo = (m - r) % MOD * mpow(3, max<ll>(0, q-1), MOD) % MOD;
    return (part_hi + part_lo) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int D; cin >> D;
    // Maintain active demands; new ones may dominate or be dominated by earlier ones
    // when sorted by the "rate" b/m. Here we keep a simple O(D^2) baseline for subtasks 1–8.
    vector<pair<ll,ll>> demands;
    for (int i = 0; i < D; ++i) {
        ll m, b; cin >> m >> b;
        demands.push_back({m, b});
        ll ans = 0;
        for (auto [mm, bb] : demands) ans = max(ans, fcost(mm, bb)); // not max in mod-land; full solution uses real-valued compare
        cout << ans % MOD << '\n';
    }
    return 0;
}

Baseline only; the "max" must compare real magnitudes before modding, and the full solution wraps the hull-of-slopes structure around this primitive.

Pitfalls

Problem 2 · Minimum Sum of Maximums

Official problem (cpid=1405)

Statement (paraphrased)

N tiles with ugliness ai; K of them are stuck at fixed indices. You may permute the rest. Minimise Σi=1..N−1 max(ai, ai+1). Output the minimum.

Constraints

Key idea

If K = 0, sort and place: putting the smallest values at the ends and largest in the middle of a zigzag is optimal — but actually the closed form is "sort ascending, then sum gives 2·(sum) − max − min" or similar; check via small cases. For K up to 6, the fixed slots partition the row into at most 7 free segments. For each segment, given which free values land in it (a subset of the free multiset of size = segment length), the segment's contribution depends on which free value is at each end (touching the fixed neighbour). DP: enumerate which free values fall in which segment (with segment-length partition) and which two are endpoints — Stirling-like assignment but with K ≤ 6 segments, it's tractable. Min-cost assignment via DP over a sorted multiset.

Complexity target

O(N3 · 2K) or O(N2 · K · 2K) depending on implementation; both fit in 3003 · 64 ≈ 1.7 · 109-ish — tight but doable with good constants in 2 s.

C++ reference solution

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

int N, K;
vector<int> a;     // 1-indexed
vector<int> fixed_idx;
vector<int> free_vals; // sorted ascending

// Segment endpoints fixed_idx[i-1]+1 .. fixed_idx[i]-1 (with sentinels 0 and N+1).
// DP across segments left to right, threading a state = how many free values consumed.
// For each segment, sub-DP picks consecutive free values (after sorting) and decides endpoints.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    a.assign(N + 1, 0);
    for (int i = 1; i <= N; ++i) cin >> a[i];
    fixed_idx.resize(K);
    for (auto& x : fixed_idx) cin >> x;
    sort(fixed_idx.begin(), fixed_idx.end());

    set<int> fset(fixed_idx.begin(), fixed_idx.end());
    for (int i = 1; i <= N; ++i) if (!fset.count(i)) free_vals.push_back(a[i]);
    sort(free_vals.begin(), free_vals.end());

    // Baseline: for small N we brute force the K = 0 case directly.
    if (K == 0) {
        ll ans = 0;
        for (size_t i = 0; i + 1 < free_vals.size(); ++i) ans += max(free_vals[i], free_vals[i+1]);
        // The optimum may be a different ordering than sorted; for the real solution, see editorial.
        cout << ans << '\n';
        return 0;
    }
    // General K: full DP omitted (see editorial).
    cout << 0 << '\n';
    return 0;
}

Outline only — the segment DP is non-trivial. Use the editorial's recursion as the reference.

Pitfalls

Problem 3 · Infinite Adventure

Official problem (cpid=1406)

Statement (paraphrased)

N cities. City i has a period Ti (a power of 2) and a portal table c(i, 0..Ti−1). Standing at city v on day t, you move to c(v, t mod Tv) on day t+1. For each of Q queries (v, t, Δ), output where you end up after Δ steps.

Constraints

Key idea

Binary lifting where the "state" is (city, time mod L) for L = some power-of-2 horizon. Because all Ti are powers of 2, for any horizon 2k, the behaviour of city i over the next 2k steps depends only on t mod max(Ti, 2k). Precompute jump[k][i][t mod Lk] = where you land after 2k steps starting at city i on day t. Memory bound is ΣTi · log Δ ≈ 105 · 60 = 6 · 106. Each query uses 60 lifts.

Complexity target

O((ΣT) · log Δ_max) preprocessing + O(Q · log Δ_max) per query.

C++ reference solution

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    vector<int> T(N);
    for (auto& x : T) cin >> x;
    vector<vector<int>> c(N);
    for (int i = 0; i < N; ++i) {
        c[i].resize(T[i]);
        for (auto& x : c[i]) cin >> x;
    }

    const int LOG = 60;
    // jump[k][i] is a vector of length L_k = max(T[i], 1<<k) holding the city you reach
    // after 2^k steps from (i, t mod L_k).
    vector<vector<vector<int>>> jmp(LOG);
    jmp[0].assign(N, {});
    for (int i = 0; i < N; ++i) {
        jmp[0][i].assign(T[i], 0);
        for (int r = 0; r < T[i]; ++r) jmp[0][i][r] = c[i][r];
    }
    for (int k = 1; k < LOG; ++k) {
        jmp[k].assign(N, {});
        ll step = 1LL << (k - 1);
        for (int i = 0; i < N; ++i) {
            int Lk = max<int>(T[i], 1 << k);
            // For huge k, Lk would overflow; clamp to a sane bound (e.g. 1<<30) — see editorial.
            Lk = min(Lk, 1 << 20);
            jmp[k][i].assign(Lk, 0);
            for (int r = 0; r < Lk; ++r) {
                int mid = jmp[k-1][i][r % (int)jmp[k-1][i].size()];
                int r2 = (int)((r + step) % max<int>(T[mid], 1));
                int sz = (int)jmp[k-1][mid].size();
                jmp[k][i][r] = jmp[k-1][mid][r2 % sz];
            }
        }
    }

    while (Q--) {
        int v; ll t, D; cin >> v >> t >> D;
        for (int k = 0; k < LOG && D; ++k) if ((D >> k) & 1) {
            int sz = (int)jmp[k][v].size();
            v = jmp[k][v][(int)(t % sz)];
            t += (1LL << k);
        }
        cout << v << '\n';
    }
    return 0;
}

The clamp on Lk is a sketch; the real solution uses the fact that once 2k exceeds Ti, the residue collapses to t mod Ti for the next-step computation. See the editorial for the precise periodicity argument.

Pitfalls