U USACO Prep

USACO 2018 December · Gold · all three problems

← Full December 2018 set · Official results

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

Statement

Undirected weighted graph with N pastures and M trails. The barn is at pasture N; cows live at pastures 1..N−1 and each must walk home. K haybales are placed at given pastures with yumminess yk. Each cow may stop at one haybale en route, but only if her total walking time then exceeds her direct-shortest path by at most yk. For each cow output 1 if she can detour to some haybale, else 0.

Constraints

Key idea

Two Dijkstras from pasture N. (1) d[v] = shortest distance from v to N. (2) Build a virtual super-source S connected to each haybale h with edge weight d[h] − yh (the "discounted distance" of detouring through h). Run Dijkstra from S to get e[v]. Cow v succeeds iff e[v] ≤ d[v].

Complexity target

O((N + M) log N) for each Dijkstra.

Reference solution (C++)

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

int N, M, K;
vector<vector<pair<int, ll>>> G;

vector<ll> dijkstra(int src) {
    vector<ll> d(N + 1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    d[src] = 0; pq.push({0, src});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > d[u]) continue;
        for (auto [v, w] : G[u]) if (du + w < d[v]) {
            d[v] = du + w; pq.push({d[v], v});
        }
    }
    return d;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> K;
    G.assign(N + 2, {});                       // node N+1 is the virtual source
    for (int i = 0; i < M; ++i) {
        int a, b; ll t; cin >> a >> b >> t;
        G[a].push_back({b, t}); G[b].push_back({a, t});
    }
    auto d = dijkstra(N);                      // distance to barn
    int S = N + 1;
    for (int k = 0; k < K; ++k) {
        int h; ll y; cin >> h >> y;
        // Virtual edge S -> h with weight d[h] - y; both directions ok since we
        // only use S as source.
        ll w = d[h] - y;                       // may be negative -> shift later
        G[S].push_back({h, w});
    }
    // Dijkstra with possibly-negative S-edges is fine: only S has them, and
    // they're traversed once from S.
    auto e = dijkstra(S);
    for (int v = 1; v < N; ++v)
        cout << (e[v] <= d[v] ? 1 : 0) << "\n";
}

Pitfalls

Problem 2 — Cowpatibility

Statement

Each of N cows has an unordered set of exactly 5 ice-cream flavors. Two cows are compatible if their sets share ≥ 1 flavor. Output the number of unordered pairs that are not compatible.

Constraints

Key idea

Inclusion–exclusion over flavor subsets. Let f(S) = number of cows whose flavor set ⊇ S. The number of compatible pairs is ΣS≠∅ (−1)|S|+1 · C(f(S), 2), summed over the 25−1 = 31 non-empty subsets of each cow's 5 flavors (so 31·N keys total). Answer = C(N, 2) − compatible.

Complexity target

O(N · 32 · log) with a hash map keyed by sorted subsets. ~1.5M map insertions.

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; cin >> N;
    // Map subset (as sorted vector) -> count of cows whose set contains it.
    map<vector<int>, ll> cnt;
    vector<array<int, 5>> cows(N);
    for (int i = 0; i < N; ++i) {
        for (auto& x : cows[i]) cin >> x;
        sort(cows[i].begin(), cows[i].end());
        for (int mask = 1; mask < 32; ++mask) {
            vector<int> sub;
            for (int b = 0; b < 5; ++b) if (mask & (1 << b)) sub.push_back(cows[i][b]);
            cnt[sub]++;
        }
    }
    ll compat = 0;
    for (auto& [sub, c] : cnt) {
        ll pairs = c * (c - 1) / 2;
        int sz = sub.size();
        if (sz % 2 == 1) compat += pairs;
        else             compat -= pairs;
    }
    ll total = (ll)N * (N - 1) / 2;
    cout << total - compat << "\n";
}

Pitfalls

Problem 3 — Teamwork

Statement

A line of N cows with skills s1..sN. Partition the line into contiguous groups of size at most K. Each cow's effective skill becomes the maximum of her group. Maximize the sum of effective skills.

Constraints

Key idea

1-D DP. Let dp[i] = best sum considering the first i cows. Transition: dp[i] = max over j ∈ [1, K] of dp[i − j] + j · max(s[i−j+1..i]). Compute the rolling max inline as j grows.

Complexity target

O(N·K) = 107.

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<int> s(N + 1);
    for (int i = 1; i <= N; ++i) cin >> s[i];

    vector<ll> dp(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int mx = 0;
        for (int j = 1; j <= K && i - j >= 0; ++j) {
            mx = max(mx, s[i - j + 1]);
            dp[i] = max(dp[i], dp[i - j] + (ll)j * mx);
        }
    }
    cout << dp[N] << "\n";
}

Pitfalls

What Gold December 2018 was actually testing