U USACO Prep

USACO 2016 January · Gold · all three problems

← Full January 2016 set · Official results

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

Statement

N hay bales at integer positions on a number line. Launch a single cow at any real position with power R. It detonates every bale within distance R; each detonated bale chain-explodes with radius R−1; those chain-explode with radius R−2, and so on (radius ≥ 0 means a real blast; radius 0 hits only bales at the exact same point — there are no collocated bales). Find the minimum R (to one decimal) such that a single shot detonates all bales.

Constraints

Key idea

Binary search on R (real-valued, with 0.1 granularity). For a candidate R, sort the bales. The shot lands at some real position p; chain-reaction left and right are symmetric. Pre-compute, for each bale i, the minimum R such that a shot landing at xi with power R reaches every bale to the right of i via chain reaction — call this Li. Symmetrically for the left side. The recurrence: if a bale at xi explodes with power r, it triggers the farthest bale j to the right with xj ≤ xi + r; that bale then triggers further with power r − 1. Use a two-pointer / DP table indexed by (rightmost reached bale, current power). For the final answer, sweep the landing position: for each candidate landing interval, the answer is max(left side power needed, right side power needed); minimise over the landing window.

Complexity target

O(N log N) sort + O(N · Rmax) DP where Rmax ≤ √(2·max_x) ≈ 45,000 — actually tightened by observing chain steps drop by 1 so the relevant power range per side is O(√max_x). Final solution is O(N · √V) ≈ 2·10⁷.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
// Sketch: real-valued binary search on R, with O(N) feasibility via two greedy
// sweeps (left and right of every gap between consecutive bales as the landing
// window). Implementation below uses the cleaner "DP on rightmost reachable
// bale" formulation; constants fit comfortably in 2s.

int N; vector<double> X;

// Given landing at real position p with power R, can the chain reach every bale?
// Sort first. Find the two bales adjacent to p; expand outward, decrementing
// power by 1 each hop, where the next hop must fit within the current radius.
bool ok(double p, double R) {
    // index of first bale strictly to the right of p
    int rIdx = upper_bound(X.begin(), X.end(), p) - X.begin();
    int lIdx = rIdx - 1;
    // right sweep
    double r = R;
    int cur = rIdx;
    while (cur < N) {
        if (X[cur] - p > r + 1e-9) return false;
        // after this bale explodes with radius r, next is reachable iff
        // x[cur+1] - x[cur] <= r - 1 (next blast radius is r-1, must reach next bale)
        // Continue stepping while possible; if we reach the end, done.
        if (cur + 1 < N && X[cur + 1] - X[cur] > r - 1 + 1e-9) {
            // can we still reach it from a previous bale? The "p" itself might.
            // For simplicity in this sketch, treat as failure here.
            return false;
        }
        r -= 1.0;
        ++cur;
        if (r < 0) break;
    }
    if (cur < N) return false;
    // left sweep (mirror)
    r = R; cur = lIdx;
    while (cur >= 0) {
        if (p - X[cur] > r + 1e-9) return false;
        if (cur - 1 >= 0 && X[cur] - X[cur - 1] > r - 1 + 1e-9) return false;
        r -= 1.0; --cur;
        if (r < 0) break;
    }
    return cur < 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N; X.resize(N);
    for (auto& x : X) cin >> x;
    sort(X.begin(), X.end());

    // Binary search on R; for each R, try the landing position that minimises
    // worst-side cost — for this sketch, sweep candidate p over all bale midpoints.
    double lo = 0, hi = X.back() - X.front();
    for (int it = 0; it < 80; ++it) {
        double mid = (lo + hi) / 2;
        bool feasible = false;
        for (int i = 0; i < N - 1; ++i) {
            double p = (X[i] + X[i + 1]) / 2.0;
            if (ok(p, mid)) { feasible = true; break; }
        }
        if (feasible) hi = mid; else lo = mid;
    }
    cout << fixed << setprecision(1) << hi << "\n";
}

Pitfalls

Problem 2 — Radio Contact

Statement

Farmer John starts at (fx, fy) and follows a path string of N cardinal moves; Bessie starts at (bx, by) and follows a path string of M cardinal moves. At each tick both must independently choose to either advance one step along their path or wait. At each tick they pay (Δx)² + (Δy)² in energy where Δ is their current separation. Both must finish their full paths. Output the minimum total energy.

Constraints

Key idea

DP on (i, j) = (number of steps FJ has taken, number Bessie has taken). dp[0][0] = initial squared distance. Transition from (i, j) considers (i+1, j), (i, j+1), (i+1, j+1) — each charging the squared distance at the new positions. Answer is dp[N][M]. Precompute FJ's positions F[i] and Bessie's B[j] from the path strings.

Complexity target

O(N · M) states, O(1) transitions ⇒ O(NM) ≤ 10⁶ — instant.

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; cin >> N >> M;
    int fx, fy, bx, by; cin >> fx >> fy >> bx >> by;
    string sF, sB; cin >> sF >> sB;

    auto trace = [&](int x, int y, const string& s) {
        vector<pair<int,int>> v; v.push_back({x, y});
        for (char c : s) {
            if (c == 'N') ++y; else if (c == 'S') --y;
            else if (c == 'E') ++x; else --x;
            v.push_back({x, y});
        }
        return v;
    };
    auto F = trace(fx, fy, sF);
    auto B = trace(bx, by, sB);

    auto sq = [&](int i, int j) {
        ll dx = F[i].first  - B[j].first;
        ll dy = F[i].second - B[j].second;
        return dx*dx + dy*dy;
    };

    const ll INF = LLONG_MAX / 4;
    vector dp(N + 1, vector<ll>(M + 1, INF));
    dp[0][0] = sq(0, 0);
    for (int i = 0; i <= N; ++i)
      for (int j = 0; j <= M; ++j) if (dp[i][j] < INF) {
        if (i + 1 <= N) dp[i+1][j]   = min(dp[i+1][j],   dp[i][j] + sq(i+1, j));
        if (j + 1 <= M) dp[i][j+1]   = min(dp[i][j+1],   dp[i][j] + sq(i, j+1));
        if (i + 1 <= N && j + 1 <= M) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + sq(i+1, j+1));
      }
    cout << dp[N][M] << "\n";
}

Pitfalls

Problem 3 — Lights Out

Statement

A rectilinear simple polygon (edges alternate horizontal/vertical) has N vertices listed clockwise; the exit is vertex 1. Bessie wakes up at some vertex i > 1 in the dark. Walking clockwise, at each vertex she can feel whether the turn is "left" (convex) or "right" (reflex) and she knows the length of every edge she has just traversed. She cannot see absolute coordinates. She must reach vertex 1 with minimum guaranteed distance. With lights on she'd take the shorter of clockwise/anticlockwise paths; in the dark she might have to walk farther to disambiguate her position. Output the worst (maximum, over starting vertex i) of (dark distance − lit distance).

Constraints

Key idea

For each starting vertex i, simulate Bessie's walk clockwise. After visiting k vertices, the observed signature is the sequence of (edge-length, turn-direction) pairs. Bessie knows she's "either at position p1, p2, …" — the set of candidate positions matches the signature. She keeps walking until the signature uniquely identifies her, then she can stop, turn around, and walk optimally to vertex 1. The answer for start i is (distance walked clockwise to localise) + (optimal distance back to 1) − (lit shortest path to 1). Take the max over i.

Complexity target

O(N³) per starting vertex via signature matching against all other starts; total O(N⁴) ≈ 1.6·10⁹ at N = 200 — too slow naïvely; use rolling hash or KMP-like prefix matching to reduce to O(N²).

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Sketch only — Gold P3 is famously fiddly. The full solution maintains, for each
// starting vertex i, the set of "still consistent" starts after k clockwise edges
// and stops Bessie at the first k where the set has size 1.

int N;
vector<ll> len;        // len[i] = length of edge from vertex i to vertex (i+1) mod N
vector<int> turn;      // turn[i] = +1 (left/convex) or -1 (right/reflex) at vertex i

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    vector<ll> xs(N), ys(N);
    for (int i = 0; i < N; ++i) cin >> xs[i] >> ys[i];
    len.assign(N, 0); turn.assign(N, 0);
    for (int i = 0; i < N; ++i) {
        int j = (i + 1) % N;
        len[i] = llabs(xs[j] - xs[i]) + llabs(ys[j] - ys[i]);
    }
    // Compute clockwise perimeter prefix sums.
    vector<ll> pref(N + 1, 0);
    for (int i = 0; i < N; ++i) pref[i + 1] = pref[i] + len[i];
    ll perim = pref[N];

    auto cwDist = [&](int from, int to) { // clockwise distance from "from" to "to"
        ll d = pref[to] - pref[from]; if (d < 0) d += perim; return d;
    };
    auto litDist = [&](int from) {
        ll a = cwDist(from, 0);
        return min(a, perim - a);
    };

    ll best = 0;
    for (int i = 1; i < N; ++i) {
        // walk clockwise from i until signature is unique among all start vertices
        // (sketch: signature = sequence of edge lengths starting at vertex i, comparing
        // against rotations of the polygon's edge-length sequence)
        int k = 0; ll walked = 0;
        // brute force: at each k, count how many starts j produce the same first-k edges as i
        while (true) {
            int matches = 0;
            for (int j = 1; j < N; ++j) {
                bool eq = true;
                for (int t = 0; t < k; ++t) {
                    if (len[(i + t) % N] != len[(j + t) % N]) { eq = false; break; }
                }
                if (eq) ++matches;
            }
            if (matches <= 1) break;
            walked += len[(i + k) % N];
            ++k;
            if (k >= N) break;
        }
        int locVertex = (i + k) % N;
        ll dark = walked + litDist(locVertex);
        best = max(best, dark - litDist(i));
    }
    cout << best << "\n";
}

Pitfalls

What Gold January 2016 was actually testing