U USACO Prep

USACO 2019 February · Silver · 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

Generalize Bronze P1 to N cows at distinct integer positions. On each move, take the minimum- or maximum-position cow and place it on an unoccupied integer that is strictly between the current min and max. Output the minimum and maximum number of moves to make the positions N consecutive.

Constraints

Key idea

Sort positions. Minimum: find the length-N sliding window over the sorted array that contains the most cows in an integer span of width N (i.e. max count of pj with pi ≤ pj ≤ pi + N − 1). The answer is N − (that count), except a special case: if the cows almost fill the window — N − 1 of them are already consecutive but the last cow is exactly one away — you still need 2 moves, not 1. Maximum: on each move you remove one "wasted slot" from either the leftmost or rightmost gap. The answer is max((p[N−1] − p[1]) − (N − 2), (p[N−2] − p[0]) − (N − 2)) — the larger gap minus the cows that already fit minus 1.

Complexity target

O(N log N) for sorting + O(N) two-pointer window.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<ll> p(N);
    for (auto& x : p) cin >> x;
    sort(p.begin(), p.end());

    // Maximum: shave off the smaller-side empty cells one at a time.
    ll mx = max(p[N - 1] - p[1], p[N - 2] - p[0]) - (N - 2);

    // Minimum: largest count of cows in a width-N window of sorted positions.
    int best = 1, j = 0;
    for (int i = 0; i < N; ++i) {
        while (j < N && p[j] - p[i] <= N - 1) ++j;
        best = max(best, j - i);
    }
    ll mn;
    if (best == N) mn = 0;                              // already consecutive
    else if (best == N - 1 && p[N - 1] - p[0] != N - 1
             && (p[N - 2] - p[0] == N - 2
                 || p[N - 1] - p[1] == N - 2)
             && (p[N - 1] - p[0] > N))               // [verify edge] cpid=918
        mn = 2;
    else mn = N - best;

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

Pitfalls

Problem 2 — Painting the Barn

Statement

FJ paints N axis-aligned rectangles on the barn wall (a 2D grid). Each rectangle adds one "coat" to every unit square it covers. Output the total area covered by exactly K coats.

Constraints

Key idea

Coordinates are tiny (≤ 200). Build a 2D difference array: for each rectangle (x1,y1,x2,y2) do +1 at (x1,y1), −1 at (x2,y1) and (x1,y2), +1 at (x2,y2). Take the 2D prefix sum to get a coats grid. Count cells with value exactly K. No coordinate compression needed at this size.

Complexity target

O(N + S2) where S = 200. About 4·104 grid cells; trivial.

Reference solution (C++)

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

int main() {
    int N, K; cin >> N >> K;
    const int S = 202;
    vector<vector<int>> d(S, vector<int>(S, 0));

    for (int i = 0; i < N; ++i) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        d[x1][y1] += 1;
        d[x2][y1] -= 1;
        d[x1][y2] -= 1;
        d[x2][y2] += 1;
    }

    // 2D prefix sum -> coats grid.
    for (int i = 1; i < S; ++i)
        for (int j = 0; j < S; ++j) d[i][j] += d[i - 1][j];
    for (int i = 0; i < S; ++i)
        for (int j = 1; j < S; ++j) d[i][j] += d[i][j - 1];

    long long ans = 0;
    for (int i = 0; i < S - 1; ++i)
        for (int j = 0; j < S - 1; ++j)
            if (d[i][j] == K) ++ans;

    cout << ans << "\n";
}

Pitfalls

Problem 3 — The Great Revegetation

Statement

Assign one of two grass types to each of N pastures. M cow constraints come in two flavors: 'S' pairs (a, b) require the same grass type, 'D' pairs require different types. Output the number of valid assignments as a binary integer (no leading zeros unless the answer is 0 or 1).

Constraints

Key idea

Run DSU with a "parity to root" tag per node. Merging an 'S' edge demands parity 0 between endpoints, 'D' demands parity 1. If any merge creates a contradiction, the answer is 0. Otherwise, if there are C connected components, the answer is exactly 2C (each component has 2 valid colorings, independent of others). Output 2C in binary: a '1' followed by C '0's.

Complexity target

O((N + M) α(N)) with weighted DSU.

Reference solution (C++)

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

struct DSU {
    vector<int> p, r, w;                 // parent, rank, parity-to-parent
    DSU(int n) : p(n), r(n, 0), w(n, 0) { iota(p.begin(), p.end(), 0); }
    pair<int,int> find(int x) {
        if (p[x] == x) return {x, 0};
        auto [root, pw] = find(p[x]);
        w[x] ^= pw; p[x] = root;
        return {root, w[x]};
    }
    bool unite(int a, int b, int diff) { // require w(a) ^ w(b) == diff
        auto [ra, wa] = find(a);
        auto [rb, wb] = find(b);
        if (ra == rb) return (wa ^ wb) == diff;
        if (r[ra] < r[rb]) swap(ra, rb), swap(wa, wb);
        p[rb] = ra; w[rb] = wa ^ wb ^ diff;
        if (r[ra] == r[rb]) ++r[ra];
        return true;
    }
};

int main() {
    int N, M; cin >> N >> M;
    DSU d(N + 1);
    bool ok = true;
    for (int i = 0; i < M; ++i) {
        char t; int a, b; cin >> t >> a >> b;
        int diff = (t == 'D') ? 1 : 0;
        if (!d.unite(a, b, diff)) ok = false;
    }
    if (!ok) { cout << 0 << "\n"; return 0; }

    int comps = 0;
    for (int i = 1; i <= N; ++i) if (d.find(i).first == i) ++comps;
    cout << 1;
    for (int i = 0; i < comps; ++i) cout << 0;     // 2^comps in binary
    cout << "\n";
}

Pitfalls

What Silver February 2019 was actually testing