U USACO Prep

USACO 2016 December · Gold · all three problems

← Full December 2016 set · Official results

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

Statement

N cows at given 2D positions all use identical walkie-talkies with squared transmission radius X (so a cow can reach another within Euclidean distance √X). Messages can be relayed. Find the minimum integer X such that any cow's message reaches every other cow.

Constraints

Key idea

The answer is the maximum squared edge weight in a Minimum Spanning Tree on the complete graph of cows (weights = squared distances). MST minimizes the maximum edge that connects all nodes — exactly what "all reachable" means. With N ≤ 1000 there are ~5 · 105 edges; sort + Kruskal with union-find is comfortable.

Complexity target

O(N² log N) for sorting edges; O(N² α(N)) for the union-find scan. ~5 · 106 operations.

Reference solution (C++)

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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int f(int x) { return p[x] == x ? x : p[x] = f(p[x]); }
    bool u(int a, int b) {
        a = f(a); b = f(b); if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a; if (r[a] == r[b]) ++r[a];
        return true;
    }
};

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

    // All N*(N-1)/2 edges weighted by squared distance.
    vector<tuple<ll, int, int>> e;
    e.reserve((ll)N * (N - 1) / 2);
    for (int i = 0; i < N; ++i)
        for (int j = i + 1; j < N; ++j) {
            ll dx = x[i] - x[j], dy = y[i] - y[j];
            e.emplace_back(dx * dx + dy * dy, i, j);
        }
    sort(e.begin(), e.end());

    DSU dsu(N);
    ll ans = 0; int used = 0;
    for (auto& [w, a, b] : e) {
        if (dsu.u(a, b)) { ans = w; if (++used == N - 1) break; }
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Cow Checklist

Statement

Farmer John must visit H Holsteins (in order 1..H) and G Guernseys (in order 1..G), starting at Holstein 1 and ending at Holstein H. Between consecutive visits he travels in a straight line; cost is the squared Euclidean distance. He may interleave the two ordered lists freely. Find the minimum total cost.

Constraints

Key idea

DP on (i, j, last) where i = next unused Holstein index, j = next unused Guernsey index, last ∈ {H, G} is which breed the previous step landed on. The current position is fully determined by (i, j, last). Transitions: from state (i, j, H) (we just visited Holstein i−1) you can go to Holstein i (cost dist²(Hi−1, Hi)) leading to (i+1, j, H), or to Guernsey j (cost dist²(Hi−1, Gj)) leading to (i, j+1, G). Initial state: (2, 1, H) with cost 0 (we're at H1). Answer is min over j of dp[H+1][j][H]. The state space is H · G · 2 ≈ 2 · 106.

Complexity target

O(H · G) states with O(1) transitions ≈ 2 · 106 operations.

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 H, G; cin >> H >> G;
    vector<ll> hx(H + 1), hy(H + 1), gx(G + 1), gy(G + 1);
    for (int i = 1; i <= H; ++i) cin >> hx[i] >> hy[i];
    for (int j = 1; j <= G; ++j) cin >> gx[j] >> gy[j];

    auto d2 = [&](ll x1, ll y1, ll x2, ll y2) {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    };

    const ll INF = LLONG_MAX / 4;
    // dp[i][j][k]: at H_i (k=0) or G_j (k=1), having visited H_1..H_i and G_1..G_j.
    vector dp(H + 2, vector(G + 2, array<ll, 2>{INF, INF}));
    dp[1][0][0] = 0;  // Start at H1, no Guernsey visited yet.

    for (int i = 1; i <= H; ++i)
      for (int j = 0; j <= G; ++j)
        for (int k = 0; k < 2; ++k) if (dp[i][j][k] < INF) {
            ll cur = dp[i][j][k];
            ll cx = (k == 0 ? hx[i] : gx[j]);
            ll cy = (k == 0 ? hy[i] : gy[j]);
            // Next visit: Holstein i+1 (must move forward) or Guernsey j+1.
            if (i + 1 <= H) {
                ll nc = cur + d2(cx, cy, hx[i + 1], hy[i + 1]);
                dp[i + 1][j][0] = min(dp[i + 1][j][0], nc);
            }
            if (j + 1 <= G) {
                ll nc = cur + d2(cx, cy, gx[j + 1], gy[j + 1]);
                dp[i][j + 1][1] = min(dp[i][j + 1][1], nc);
            }
        }

    ll ans = INF;
    for (int j = 0; j <= G; ++j) ans = min(ans, dp[H][j][0]);
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Lasers and Mirrors

Statement

A laser source and a barn sit at integer (x, y) points. There are N fence posts at given (x, y) coordinates, on each of which Bessie may place a 90° mirror. The laser shoots either horizontally or vertically; a mirror redirects it 90° (either turn). Find the minimum number of mirrors needed to route the beam from source to barn, or −1 if impossible.

Constraints

Key idea

Treat each unique x-coordinate and y-coordinate as a graph node. A fence post at (x, y) creates an edge between the "row y" node and the "column x" node (cost 1 — placing a mirror there switches the beam between rows and columns). The source sits on its row and column for free; the barn must be reached via either its row or its column. BFS from the source row/column gives the minimum number of mirrors minus one (the last mirror puts the beam onto the barn's row/column; the answer is BFS distance − 1 if we treat each fence post as a step between row-node and column-node).

Complexity target

O((N + R + C) + N log N) where R, C are the numbers of distinct y and x values; coordinate compression keeps the graph at most ~2N nodes.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; long long sx, sy, bx, by;
    cin >> N >> sx >> sy >> bx >> by;
    vector<long long> px(N), py(N);
    for (int i = 0; i < N; ++i) cin >> px[i] >> py[i];

    // Compress all distinct x's and y's (including source and barn) into IDs.
    vector<long long> xs = {sx, bx}, ys = {sy, by};
    for (int i = 0; i < N; ++i) { xs.push_back(px[i]); ys.push_back(py[i]); }
    sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
    auto xid = [&](long long v){ return (int)(lower_bound(xs.begin(), xs.end(), v) - xs.begin()); };
    auto yid = [&](long long v){ return (int)(lower_bound(ys.begin(), ys.end(), v) - ys.begin()); };

    // Node layout: columns 0..|xs|-1, rows |xs|..|xs|+|ys|-1.
    int XS = xs.size(), YS = ys.size();
    auto col = [&](int i){ return i; };
    auto row = [&](int i){ return XS + i; };
    vector<vector<int>> adj(XS + YS);
    for (int i = 0; i < N; ++i) {
        int c = col(xid(px[i])), r = row(yid(py[i]));
        adj[c].push_back(r); adj[r].push_back(c);
    }

    // BFS from both source's row and column; goal is barn's row or column.
    vector<int> dist(XS + YS, -1);
    queue<int> q;
    int sCol = col(xid(sx)), sRow = row(yid(sy));
    int bCol = col(xid(bx)), bRow = row(yid(by));
    dist[sCol] = 0; q.push(sCol);
    dist[sRow] = 0; q.push(sRow);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    int a = dist[bCol], b = dist[bRow];
    int best = -1;
    if (a != -1) best = a;
    if (b != -1) best = (best == -1) ? b : min(best, b);
    // BFS distance counts mirror hops; subtract 1 because reaching the
    // barn's own row/column needs no extra mirror at the barn itself.
    cout << (best <= 0 ? best : best - 1) << "\n";
}

Pitfalls

What Gold December 2016 was actually testing