U USACO Prep

USACO 2019 February · Bronze · all three problems

← Full February 2019 set · Official results

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

Statement

Three cows sit at distinct integer positions on a number line. In one move FJ takes the cow currently at the minimum or maximum position and places it at any unoccupied integer position, with the constraint that after the move the relocated cow is no longer at an endpoint (i.e. it lands strictly between the other two). The goal is three consecutive integers. Output the minimum and maximum number of moves.

Constraints

Key idea

Sort the three positions to a, b, c. Minimum: if already consecutive (c − a = 2), answer 0; if either gap is 1 or 2 (i.e. b − a ≤ 2 or c − b ≤ 2 with the right alignment giving a 1-move finish), answer 1; otherwise 2 moves always suffice. Maximum: at each step you can shrink whichever side gap is larger by exactly 1 (you slide the far endpoint just inside the other one). So max = max(b − a, c − b) − 1.

Complexity target

O(1) after reading three integers.

Reference solution (C++)

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

int main() {
    int x[3];
    for (int i = 0; i < 3; ++i) cin >> x[i];
    sort(x, x + 3);
    int a = x[0], b = x[1], c = x[2];

    // Minimum moves.
    int mn;
    if (c - a == 2) {
        mn = 0;                             // already consecutive
    } else if (b - a <= 2 || c - b <= 2) {
        mn = 1;                             // one move closes a gap-of-2 hole
    } else {
        mn = 2;                             // always doable in two
    }

    // Maximum moves: shave the larger gap down to 1 step at a time.
    int mx = max(b - a, c - b) - 1;

    cout << mn << "\n" << mx << "\n";
}

Pitfalls

Problem 2 — The Great Revegetation

Statement

FJ has N pastures and 4 types of grass (1..4). M cows each have two favorite pastures and demand they receive different grass types. Each pasture is the favorite of at most 3 cows. Output the lexicographically smallest valid assignment as an N-digit string.

Constraints

Key idea

Each pasture has at most 3 neighbors (via the cow constraints). When you process pastures in order 1..N and greedily pick the smallest type 1..4 not used by any already-assigned neighbor, you are guaranteed a choice — at most 3 forbidden values out of 4. The greedy answer is lexicographically minimum because each position commits to the smallest legal type independently of later positions.

Complexity target

O(N + M): build adjacency, then a single sweep with a constant-size used-set check.

Reference solution (C++)

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

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> color(N + 1, 0);            // 0 = unassigned, else 1..4
    for (int i = 1; i <= N; ++i) {
        bool used[5] = {false, false, false, false, false};
        for (int j : adj[i]) if (color[j]) used[color[j]] = true;
        for (int c = 1; c <= 4; ++c) if (!used[c]) {
            color[i] = c; break;
        }
        // Greedy is safe: at most 3 forbidden values, 4 colors available.
    }

    for (int i = 1; i <= N; ++i) cout << color[i];
    cout << "\n";
}

Pitfalls

Problem 3 — Measuring Traffic

Statement

A highway runs through N consecutive mile-long segments. Each segment is one of: a main-road sensor (reads [lo, hi] of through-traffic on that mile), an on-ramp (reads [lo, hi] cars merging in), or an off-ramp (reads [lo, hi] cars exiting). Given the readings, output the tightest possible range [lo, hi] for traffic entering segment 1 and exiting segment N that is consistent with every sensor.

Constraints

Key idea

Sweep left to right starting from the "unknown" inflow range [0, ∞]. A main-road segment intersects the current range with its sensor reading. An on-ramp shifts the range up by [lo, hi] (it adds traffic), and an off-ramp shifts it down. Then sweep right to left the same way to compute the outflow range. Each sweep is independent; intersect with main-road readings whenever encountered.

Complexity target

O(N) per direction, two sweeps total.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<string> type(N);
    vector<int> lo(N), hi(N);
    for (int i = 0; i < N; ++i) cin >> type[i] >> lo[i] >> hi[i];

    const int INF = 1'000'000;

    // Forward sweep: figure out [pre-N flow] given inflow is anything.
    auto sweep = [&](bool reverse) {
        int L = 0, H = INF;
        auto step = [&](int i) {
            if (type[i] == "none")        { L = max(L, lo[i]); H = min(H, hi[i]); }
            else if (type[i] == "on")     { if (!reverse) { L += lo[i]; H += hi[i]; } else { L -= hi[i]; H -= lo[i]; } }
            else /* "off" */              { if (!reverse) { L -= hi[i]; H -= lo[i]; } else { L += lo[i]; H += hi[i]; } }
            L = max(L, 0); H = min(H, INF);
        };
        if (!reverse) for (int i = 0; i < N; ++i) step(i);
        else          for (int i = N - 1; i >= 0; --i) step(i);
        return pair<int,int>{L, H};
    };

    auto [a, b] = sweep(true);      // start from end, walk backwards -> inflow range
    auto [c, d] = sweep(false);     // start from start, walk forwards -> outflow range
    cout << a << " " << b << "\n" << c << " " << d << "\n";
}

Pitfalls

What Bronze February 2019 was actually testing