U USACO Prep

USACO 2016 January · Silver · 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 lie at integer positions on a number line. You have K cows of identical "power" R; each cow lands at any real position and detonates every bale within distance R (no chain reaction — Silver version is simple coverage). Find the minimum R such that K well-placed cows can cover every bale.

Constraints

Key idea

Binary search on R. For a candidate R, sort bales and greedily cover: place the first cow at x1 + R (covering [x1, x1 + 2R]); skip all bales ≤ x1 + 2R; repeat from the next uncovered bale. Feasible iff total cows used ≤ K. Binary search R over [0, max_x − min_x].

Complexity target

O(N log N) for the sort, O(N) per feasibility check, O(log(109)) binary search iterations ⇒ O(N log V).

Reference solution (C++)

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

int N, K;
vector<long long> X;

bool ok(long long R) {
    // Greedy: each cow covers [start, start + 2R]; place at first uncovered bale + R.
    int cows = 0;
    for (int i = 0; i < N; ) {
        ++cows;
        if (cows > K) return false;
        long long limit = X[i] + 2 * R;
        while (i < N && X[i] <= limit) ++i;
    }
    return cows <= K;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K; X.resize(N);
    for (auto& x : X) cin >> x;
    sort(X.begin(), X.end());
    long long lo = 0, hi = X.back() - X.front();
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (ok(mid)) hi = mid; else lo = mid + 1;
    }
    cout << lo << "\n";
}

Pitfalls

Problem 2 — Subsequences Summing to Sevens

Statement

Given N cow IDs in a row (non-negative integers), find the length of the longest contiguous sub-array whose sum is divisible by 7. Output 0 if no such non-empty sub-array exists.

Constraints

Key idea

Standard "longest sub-array sum ≡ 0 (mod m)" trick. Let Pi = (id1 + … + idi) mod 7. The sub-array (l, r] sums to 0 mod 7 iff Pr = Pl. To maximise length, for each residue r ∈ {0,…,6} remember the earliest index where it appears; for residue 0 the earliest index is 0 (empty prefix). For each i, answer candidate is i − firstSeen[Pi].

Complexity target

O(N) one pass.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    // first[r] = smallest prefix index i where P_i % 7 == r; -1 if unseen.
    array<int, 7> first; first.fill(-1);
    first[0] = 0;       // empty prefix has residue 0
    long long P = 0;
    int best = 0;
    for (int i = 1; i <= N; ++i) {
        long long x; cin >> x;
        P = (P + x) % 7;
        if (first[P] == -1) first[P] = i;
        else best = max(best, i - first[P]);
    }
    cout << best << "\n";
}

Pitfalls

Problem 3 — Build Gates

Statement

Farmer John starts at (0,0) and walks N unit steps over the cardinal directions, laying a fence as he goes. The fence may cross or overlap itself. Walking partitions the plane into regions (the fence itself plus the connected components of the complement). Output the minimum number of gates needed so that, treating each gate as a single hole in the fence, every region is connected to every other.

Constraints

Key idea

The number of regions minus 1 is exactly the number of gates needed (spanning-tree of the planar region graph). By Euler's formula on the planar graph induced by the fence segments, F = E − V + 1 + C, where V, E are vertices and edges of the graph after subdividing at every intersection, C is the number of connected components, and F counts bounded faces (= regions minus the outer face, plus the outer face — so total regions = F + 1 actually = E − V + 1 + C + 1). Practically: blow each grid cell up to 3×3 sub-cells, mark fence edges between sub-cells, then flood-fill the open sub-cells to count regions; subtract 1.

Complexity target

O((N · 3)2) flood fill on a 3000×3000 sub-grid is too big; instead bound by the bounding box of the path. Total visited cells ≤ N, so flood fill is O(N²) at worst, fine for N ≤ 1000.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; string s; cin >> N >> s;

    // Blow-up: map each integer cell (x,y) to a 3x3 block (3x+1, 3y+1) as its center,
    // (3x, 3y+1) west edge, (3x+2, 3y+1) east edge, etc. Walk the path and mark
    // fence sub-cells. Flood-fill the unmarked cells inside a bounding box (with
    // a 1-cell margin so the outer region is reachable).
    int x = 0, y = 0, minX = 0, maxX = 0, minY = 0, maxY = 0;
    vector<pair<int,int>> pts; pts.push_back({0, 0});
    for (char c : s) {
        if (c == 'N') ++y; else if (c == 'S') --y;
        else if (c == 'E') ++x; else --x;
        pts.push_back({x, y});
        minX = min(minX, x); maxX = max(maxX, x);
        minY = min(minY, y); maxY = max(maxY, y);
    }
    int W = 3 * (maxX - minX + 1) + 2;
    int H = 3 * (maxY - minY + 1) + 2;
    auto idx = [&](int X, int Y) { return Y * W + X; };
    vector<char> fence(W * H, 0);
    auto mark = [&](int gx, int gy) {
        int X = 3 * (gx - minX) + 1 + 1, Y = 3 * (gy - minY) + 1 + 1;
        fence[idx(X, Y)] = 1;
    };
    mark(pts[0].first, pts[0].second); // center vertex of starting cell
    for (size_t i = 1; i < pts.size(); ++i) {
        // mark the edge between pts[i-1] and pts[i]
        int X1 = 3*(pts[i-1].first - minX)+1+1, Y1 = 3*(pts[i-1].second - minY)+1+1;
        int X2 = 3*(pts[i  ].first - minX)+1+1, Y2 = 3*(pts[i  ].second - minY)+1+1;
        fence[idx((X1+X2)/2, (Y1+Y2)/2)] = 1;
        fence[idx(X2, Y2)] = 1;
    }
    // Flood-fill unmarked components.
    vector<char> vis(W * H, 0);
    int regions = 0;
    int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
    for (int Y = 0; Y < H; ++Y) for (int X = 0; X < W; ++X) {
        if (fence[idx(X, Y)] || vis[idx(X, Y)]) continue;
        ++regions;
        queue<pair<int,int>> q; q.push({X, Y}); vis[idx(X, Y)] = 1;
        while (!q.empty()) {
            auto [a, b] = q.front(); q.pop();
            for (int k = 0; k < 4; ++k) {
                int na = a + dx[k], nb = b + dy[k];
                if (na < 0 || na >= W || nb < 0 || nb >= H) continue;
                if (fence[idx(na, nb)] || vis[idx(na, nb)]) continue;
                vis[idx(na, nb)] = 1; q.push({na, nb});
            }
        }
    }
    cout << regions - 1 << "\n";
}

Pitfalls

What Silver January 2016 was actually testing