U USACO Prep

USACO 2022 December · Gold · all three problems

← Full December 2022 set · Official results

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

Statement

Bessie wants to bring as much total popularity to a movie as possible. She has A moonies and B ice cream cones. Friend i has popularity Pi, charges Ci moonies, and accepts a discount of 1 mooney per Xi cones (only that friend's rate). She can pay any non-negative real combination (mooney + cone exchange) for each friend; partial payments don't help (each friend either comes fully or not). Maximize Σ Pi over chosen friends.

Constraints

Key idea

Sort friends by Xi ascending (cheapest cone-to-mooney conversion first). With that order fixed, do a 2D knapsack DP indexed by (#friends processed, moonies used) and track the maximum "moonies-equivalent budget remaining in cones" — when paying a friend you should always exhaust their cone discount first because friends seen later have a worse cone exchange rate. Standard "two resources, one with conversion" pattern.

Complexity target

O(N · A · 2) ≈ 8·106, well within 2s.

Reference solution (C++)

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

// dp[a] = max popularity achievable using exactly <= a moonies and any number
// of cones available so far. Friends sorted by X ascending: we always use as
// many cones as possible on the current friend before any future friend.
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, A, B; cin >> N >> A >> B;
    vector<array<int,3>> f(N);     // {P, C, X}
    for (auto& t : f) cin >> t[0] >> t[1] >> t[2];
    sort(f.begin(), f.end(), [](auto& a, auto& b){ return a[2] < b[2]; });

    // dp[a] = best popularity when a moonies remain available *and* B cones still in reserve.
    // Cones are spent before moonies (lowest X first), so we walk friends in order.
    vector<int> dp(A + 1, 0);
    int cones = B;
    for (auto& t : f) {
        int P = t[0], C = t[1], X = t[2];
        // To pay friend: spend k cones (k <= cones, k <= C*X), reducing cost by k/X moonies.
        // Max cone usage = min(cones, C*X); the remaining mooney cost is C - floor(k/X).
        // Greedy on this friend: spend exactly min(cones, C*X) cones first.
        int spendCones = min(cones, C * X);
        int discount   = spendCones / X;          // floored mooneys saved
        int needMoney  = C - discount;
        if (needMoney < 0) needMoney = 0;
        // 0/1 knapsack update on moonies axis.
        for (int a = A; a >= needMoney; --a)
            dp[a] = max(dp[a], dp[a - needMoney] + P);
        cones -= spendCones;
        if (cones < 0) cones = 0;
    }
    cout << *max_element(dp.begin(), dp.end()) << "\n";
    // NOTE: the above is the simplified "greedy cones" sketch; the official
    // editorial does a full 2D DP. Treat as starting point. [verify] cpid=1257
}

Pitfalls

Problem 2 — Mountains

Statement

N mountains in a row with heights hi. Two mountains i < j see each other iff no mountain k with i < k < j has its peak strictly above the straight line from peak i to peak j. Q updates each set hi ← v; after each update output the total number of pairs (i, j) that can see each other.

Constraints

Key idea

Brute force O(N²) per update is fine: 2000² · 2000 = 8·109 is too slow, but per pair the visibility check is O(N), giving O(N³) = 8·109 — needs care. Better: maintain a visibility matrix vis[i][j] (only j > i) in O(N²) total and update lazily. When hx changes only pairs (i, j) with i ≤ x ≤ j can change — O(N²) pairs to recheck per update, each in O(1) via the slope test using cross-products → O(N²) per update, O(N²·Q) = 1.6·1010: still too slow, but with integer cross-products and a tight inner loop and Q ≤ 2000, ~4·109 ops in 5s is feasible after pruning to pairs straddling x.

Complexity target

O(N² + N·Q) using slope cross-products and per-update local rebuild (Σ over updates of |pairs crossing x| = O(N) average per update).

Reference solution (C++)

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

int N, Q;
vector<ll> h;

// Pair (i, j) visible iff for all k in (i, j):
// (h[k] - h[i]) * (j - i) <= (h[j] - h[i]) * (k - i)
// i.e. peak k not strictly above the line i-j. Cross-product form avoids fp.
bool visible(int i, int j) {
    ll dx = j - i, dy = h[j] - h[i];
    for (int k = i + 1; k < j; ++k) {
        ll lhs = (h[k] - h[i]) * dx;
        ll rhs = dy * (k - i);
        if (lhs > rhs) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> Q;
    h.resize(N);
    for (auto& x : h) cin >> x;

    // Initial visibility count.
    auto countAll = [&]() -> ll {
        ll c = 0;
        for (int i = 0; i < N; ++i)
            for (int j = i + 1; j < N; ++j)
                if (visible(i, j)) ++c;
        return c;
    };
    ll vis = countAll();

    while (Q--) {
        int x; ll v; cin >> x >> v; --x;
        // Subtract pairs (i, j) with i <= x <= j that are currently visible.
        // Then update h[x] = v. Then add back the new visible count over the same set.
        ll delta = 0;
        for (int i = 0; i <= x; ++i)
            for (int j = max(x, i + 1); j < N; ++j)
                if (visible(i, j)) --delta;
        h[x] = v;
        for (int i = 0; i <= x; ++i)
            for (int j = max(x, i + 1); j < N; ++j)
                if (visible(i, j)) ++delta;
        vis += delta;
        cout << vis << "\n";
    }
}

Pitfalls

Problem 3 — Strongest Friendship Group

Statement

Given an undirected friendship graph on N cows with M edges, the strength of a subset S of cows is |S| · (minimum degree of any cow in S, using only edges inside S), provided the induced subgraph is connected. Maximize strength over all connected subsets S.

Constraints

Key idea

Classic "k-core" + size optimization. Repeatedly peel the lowest-degree vertex from the whole graph; just before peeling vertex v with current degree d, the remaining subgraph is a candidate set whose min-degree is ≥ d, and the connected component containing v has size c, so c · d is a lower bound on achievable strength. Track the maximum of (size of v's current component) × (degree of v at deletion time) across all peels — that is the answer. Use a priority queue (or bucket sort by degree) plus a DSU run in reverse to evaluate component sizes.

Complexity target

O((N + M) log N) with a min-heap; O(N + M) with bucket degrees.

Reference solution (C++)

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

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 (p[x] != 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, M; cin >> N >> M;
    vector<vector<int>> adj(N);
    vector<pair<int,int>> edges(M);
    for (auto& [a, b] : edges) { cin >> a >> b; --a; --b; adj[a].push_back(b); adj[b].push_back(a); }

    // Peel in increasing degree to get a removal order.
    vector<int> deg(N), order;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    vector<char> dead(N, 0);
    for (int i = 0; i < N; ++i) { deg[i] = adj[i].size(); pq.push({deg[i], i}); }
    vector<int> degAtRemoval(N);
    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (dead[v] || d != deg[v]) continue;
        dead[v] = 1;
        degAtRemoval[v] = d;
        order.push_back(v);
        for (int u : adj[v]) if (!dead[u]) { --deg[u]; pq.push({deg[u], u}); }
    }

    // Now reverse the order: add vertices back, maintaining components with DSU.
    DSU dsu(N);
    vector<char> live(N, 0);
    ll best = 0;
    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int v = order[i];
        live[v] = 1;
        for (int u : adj[v]) if (live[u]) dsu.u(u, v);
        ll cand = (ll)dsu.sz[dsu.f(v)] * degAtRemoval[v];
        best = max(best, cand);
    }
    cout << best << "\n";
}

Pitfalls

What Gold December 2022 was actually testing