U USACO Prep

USACO 2018 February · Bronze · all three problems

← Full February 2018 set · Official results

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

Statement

Farmer John must haul a pile of manure from position a to position b along a straight road. He owns one teleporter with endpoints x and y; entering at one endpoint instantly emerges at the other at zero hauling cost. The tractor travels at unit cost per unit of distance. Compute the minimum total hauling distance.

Constraints

Key idea

Only three strategies are ever optimal: don't use the teleporter (cost |b−a|), use it as x→y (cost |a−x| + |y−b|), or use it reversed y→x (cost |a−y| + |x−b|). Output the minimum of the three.

Complexity target

O(1). Pure arithmetic; no loops needed.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, x, y;
    cin >> a >> b >> x >> y;

    // Three candidate strategies:
    int direct = abs(b - a);
    int viaXY  = abs(a - x) + abs(y - b);  // enter at x, exit at y
    int viaYX  = abs(a - y) + abs(x - b);  // enter at y, exit at x

    cout << min({direct, viaXY, viaYX}) << "\n";
}

Pitfalls

Problem 2 — Hoofball

Statement

N cows stand at distinct positions on a number line. Every cow with a ball passes it to its single nearest neighbor (ties broken to the lower-positioned neighbor). Find the minimum number of cows that must each start with a ball so that every cow ends up holding (or having held) at least one ball.

Constraints

Key idea

Sort cows by position. Each cow points to its nearer of the two neighbors (the only cow it can throw to), so we get a functional graph with one outgoing edge per cow. The required starting cows are exactly those with in-degree zero, plus one extra ball per "mutual pair" cycle component that has no external feeder. Sweep left-to-right computing each cow's target; count in-degrees; then add one for each 2-cycle whose members have no other in-edges.

Complexity target

O(N log N) for the sort; O(N) for the sweep. Trivial at N ≤ 100.

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;
    vector<int> x(N);
    for (auto& v : x) cin >> v;
    sort(x.begin(), x.end());

    // target[i] = index that cow i throws to (its nearer neighbor;
    // ties go to the lower-indexed neighbor i-1).
    vector<int> target(N), indeg(N, 0);
    for (int i = 0; i < N; ++i) {
        if (N == 1) { target[i] = i; continue; }
        if (i == 0)              target[i] = 1;
        else if (i == N - 1)     target[i] = N - 2;
        else {
            int dl = x[i] - x[i - 1], dr = x[i + 1] - x[i];
            target[i] = (dl <= dr) ? i - 1 : i + 1;
        }
        indeg[target[i]]++;
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) if (indeg[i] == 0) ans++;

    // Mutual-pair cycles with no outside in-edges still need one ball.
    for (int i = 0; i + 1 < N; ++i) {
        if (target[i] == i + 1 && target[i + 1] == i
            && indeg[i] == 1 && indeg[i + 1] == 1) ans++;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Taming the Herd

Statement

Farmer John has a log a1, …, aN: on day i, ai is "the number of consecutive days ending on day i with no breakout" (so ai = 0 means a breakout occurred on day i, and ai = ai−1 + 1 otherwise). Some entries are −1 (unknown). Day 1 must be a breakout (a1 = 0). Report the minimum and maximum number of breakouts consistent with the log.

Constraints

Key idea

Walk through the log greedily for the minimum. Whenever a known value ai = k pins the position of the last breakout to day i−k, mark that day as a breakout; otherwise, postpone (keep counting up using already-resolved unknowns). For the maximum, every day not forced by some downstream constraint to be non-zero may itself be a breakout — propagate: ai = k forbids breakouts on days i−k+1..i. Then any remaining day (including all those still −1) is a candidate breakout.

Complexity target

O(N²) is plenty (N ≤ 100). The cleanest implementation does two linear sweeps after a forward fill of forced values.

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;
    vector<int> a(N);
    for (auto& v : a) cin >> v;

    // forbidden[i] = true means day i must NOT be a breakout (a[i] != 0 implied).
    // forced[i]    = true means day i must BE a breakout (a[i] == 0 implied).
    vector<bool> forbidden(N, false), forced(N, false);
    forced[0] = true; // Day 1 is always a breakout.
    for (int i = 0; i < N; ++i) {
        if (a[i] < 0) continue;
        if (a[i] == 0) forced[i] = true;
        else {
            // Last breakout is at day i - a[i]; days i-a[i]+1 .. i are NOT.
            forced[i - a[i]] = true;
            for (int j = i - a[i] + 1; j <= i; ++j) forbidden[j] = true;
        }
    }
    // Minimum: place breakouts only when forced. We still must satisfy
    // unspecified days with the smallest legal run; greedy left-to-right
    // never adds a breakout unless something later forces it.
    int mn = 0, mx = 0;
    for (int i = 0; i < N; ++i) {
        if (forced[i]) { mn++; mx++; }
        else if (!forbidden[i]) mx++; // free to be a breakout in the max
    }
    cout << mn << " " << mx << "\n";
    // NOTE: the official problem also asks for a third number — the count of
    // days definitively breakouts — handled identically by reading 'forced'.
    // [verify exact required outputs] cpid=809
}

Pitfalls

What Bronze February 2018 was actually testing