U USACO Prep

USACO 2018 January · Silver · 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 (Silver)

Statement

N lifeguards each cover a half-open time interval [ai, bi). Farmer John must fire exactly K of them. Maximize the total time during which at least one of the remaining N−K lifeguards is on duty.

Constraints

Key idea

First, discard any interval strictly contained in another — keeping the bigger one is always at least as good (firing it only ever costs more coverage). After that the remaining intervals, sorted by left endpoint, also have increasing right endpoints. Now run a DP: dp[i][j] = maximum covered time using intervals from the first i (sorted) of which we kept some subset, having fired j so far, with interval i kept. Transition: from a previous kept interval p, the marginal coverage is bi − max(bp, ai), and (i − p − 1) intervals between them are fired.

Complexity target

O(N² · K). With N ≤ 100, fine in any constant.

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 by left ascending, right descending — then drop any interval whose
    // right endpoint is <= the running max right (it's contained in a previous).
    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;
    int dropped = 0;
    for (auto& p : iv) {
        if (p.second <= curR) { ++dropped; continue; }  // contained
        v.push_back(p); curR = p.second;
    }
    int M = v.size();
    // We must fire K total. We've already "freely" discarded `dropped` contained
    // ones; we still need to fire (K - dropped) more from v. If that's < 0 we
    // were forced to fire useful intervals — clamp to 0; if > M-1 we can't keep
    // even one, answer is 0.
    int need = max(0, K - dropped);
    if (need >= M) { cout << 0 << "\n"; return 0; }

    // dp[i][j] = best coverage using v[0..i], firing exactly j of v[0..i],
    // with v[i] kept. Sentinel v[-1] = (0,0).
    // Final answer = max over i, j = need, plus we fire all v[i+1..M-1] (which
    // forces those to be in the "fired" budget).
    const ll NEG = LLONG_MIN / 4;
    vector dp(M, vector<ll>(need + 1, NEG));
    for (int i = 0; i < M; ++i) {
        // option A: v[i] is the first kept interval — fire all i before it.
        if (i <= need) dp[i][i] = v[i].second - v[i].first;
        // option B: extend from some previous kept p < i, firing i-p-1 between.
        for (int p = 0; p < i; ++p) {
            ll add = v[i].second - max(v[p].second, v[i].first);
            if (add < 0) add = 0;
            int between = i - p - 1;
            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;  // these are fired
        if (trailing > need) continue;
        int j = need - trailing;
        if (j >= 0 && j <= need && dp[i][j] != NEG)
            ans = max(ans, dp[i][j]);
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Rental Service

Statement

Farmer John has N cows producing mi gallons of milk each per day. He has M milk-store contracts: store j buys up to qj gallons at pj cents per gallon (cumulative capacity, can sell to many stores). He also has R neighbors who will rent a whole cow for rk cents per day. Each cow either sells all its milk or is rented out — never both. Maximize total daily revenue.

Constraints

Key idea

Sort cows by milk descending, stores by price descending, renters by price descending. For each "split" k ∈ [0, N] meaning "rent the top k highest-paying renters out, milk the remaining N−k biggest-milk cows", revenue = (sum of top k renter prices) + (top milk filling top stores). The "top milk filling top stores" function is monotone non-increasing in k (you lose your largest cow each step), so a single linear sweep with a pointer into the milk/store stream is enough.

Complexity target

O((N + M + R) log) for sorts, O(N + M) for the sweep.

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, M, R;
    cin >> N >> M >> R;
    vector<ll> cows(N);
    for (auto& x : cows) cin >> x;
    vector<pair<ll,ll>> stores(M);  // (price, qty)
    for (auto& p : stores) cin >> p.second >> p.first;
    vector<ll> rents(R);
    for (auto& x : rents) cin >> x;

    sort(cows.rbegin(), cows.rend());
    sort(stores.rbegin(), stores.rend());          // by price desc
    sort(rents.rbegin(), rents.rend());

    // milkRev[k] = revenue selling milk from the FIRST k cows (highest milk).
    // We'll then evaluate: pick top j renters, milk the remaining N-j highest-milk
    //   cows = first N-j cows of the sorted list. So milkRev[N-j] is needed.
    vector<ll> milkRev(N + 1, 0);
    int si = 0;
    ll remain = (si < M ? stores[si].second : 0);
    for (int i = 0; i < N; ++i) {
        ll have = cows[i], rev = 0;
        while (have > 0 && si < M) {
            ll take = min(have, remain);
            rev += take * stores[si].first;
            have -= take; remain -= take;
            if (remain == 0) {
                ++si;
                remain = (si < M ? stores[si].second : 0);
            }
        }
        milkRev[i + 1] = milkRev[i] + rev;
    }

    // rentPrefix[j] = sum of top j renter prices.
    vector<ll> rentPrefix(R + 1, 0);
    for (int i = 0; i < R; ++i) rentPrefix[i + 1] = rentPrefix[i] + rents[i];

    ll ans = 0;
    for (int j = 0; j <= min(N, R); ++j) {
        ll rev = rentPrefix[j] + milkRev[N - j];
        ans = max(ans, rev);
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — MooTube (Silver)

Statement

Bessie's MooTube has N videos connected by N−1 weighted edges (a tree). Two videos are "K-similar" if every edge on the path between them has weight ≥ K. For each of Q queries (K, v) output the number of videos K-similar to v (excluding v itself).

Constraints

Key idea

Offline. Sort edges by weight descending. Sort queries by K descending. Sweep: while the next edge has weight ≥ current K, union its endpoints (DSU with size). Then answer = size of v's component − 1.

Complexity target

O((N + Q) log (N + Q)) for sorts, O((N + Q) α(N)) for DSU.

Reference solution (C++)

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

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int f(int x) { while (x != p[x]) x = p[x] = p[p[x]]; return x; }
    void u(int a, int b) {
        a = f(a); b = f(b); if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    vector<tuple<int,int,int>> edges(N - 1);  // (w, a, b)
    for (auto& [w,a,b] : edges) { cin >> a >> b >> w; --a; --b; }
    sort(edges.begin(), edges.end(), greater<>());

    vector<tuple<int,int,int>> queries(Q);    // (K, v, idx)
    for (int i = 0; i < Q; ++i) {
        int k, v; cin >> k >> v; --v;
        queries[i] = {k, v, i};
    }
    sort(queries.begin(), queries.end(), greater<>());

    DSU dsu(N);
    vector<int> ans(Q);
    int ei = 0;
    for (auto& [k, v, idx] : queries) {
        while (ei < (int)edges.size() && get<0>(edges[ei]) >= k) {
            dsu.u(get<1>(edges[ei]), get<2>(edges[ei]));
            ++ei;
        }
        ans[idx] = dsu.sz[dsu.f(v)] - 1;
    }
    for (int x : ans) cout << x << "\n";
}

Pitfalls

What Silver January 2018 was actually testing