U USACO Prep

USACO 2017 February · Silver · all three problems

← Full February 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=feb17results. 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 — Why Did the Cow Cross the Road

Statement

There are C chickens, each available at a single time Ti, and N cows, each with an availability window [Aj, Bj]. A chicken can help cow j iff Aj ≤ Ti ≤ Bj. Each chicken helps at most one cow and each cow uses at most one chicken. Output the maximum number of pairings.

Constraints

Key idea

Classic interval-stabbing greedy. Sort cows by right endpoint Bj ascending. Sort the chicken times. Use a multiset of chicken times; for each cow in order, find the smallest available chicken time ≥ Aj. If it's ≤ Bj, pair them and erase the chicken. This is the standard "earliest-deadline-first" exchange argument: a cow with the earliest deadline gets the cheapest still-feasible chicken.

Complexity target

O((C + N) log C).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, N; cin >> C >> N;
    multiset<int> chickens;
    for (int i = 0; i < C; ++i) {
        int t; cin >> t; chickens.insert(t);
    }
    vector<pair<int,int>> cows(N);   // (B, A) so we sort by deadline
    for (auto& [b, a] : cows) cin >> a >> b;
    sort(cows.begin(), cows.end());

    int paired = 0;
    for (auto [b, a] : cows) {
        auto it = chickens.lower_bound(a);
        if (it != chickens.end() && *it <= b) {
            chickens.erase(it);
            ++paired;
        }
    }
    cout << paired << "\n";
}

Pitfalls

Problem 2 — Why Did the Cow Cross the Road II

Statement

N traffic signals along a road are numbered 1..N. B of them are broken. Find the minimum number of broken signals you must repair so that there is at least one contiguous block of K consecutive working signals.

Constraints

Key idea

Mark broken positions in a boolean array. The answer is the minimum number of broken signals inside any length-K window over [1..N]. Sliding-window sum in O(N).

Complexity target

O(N).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K, B; cin >> N >> K >> B;
    vector<int> broken(N + 2, 0);
    for (int i = 0; i < B; ++i) {
        int x; cin >> x; broken[x] = 1;
    }
    // Sliding window of size K over [1..N].
    int cur = 0;
    for (int i = 1; i <= K; ++i) cur += broken[i];
    int best = cur;
    for (int i = K + 1; i <= N; ++i) {
        cur += broken[i] - broken[i - K];
        best = min(best, cur);
    }
    cout << best << "\n";
}

Pitfalls

Problem 3 — Why Did the Cow Cross the Road III

Statement

An N×N grid of fields. R road segments separate adjacent fields. K cows stand at given cells. A pair of cows is "distant" if you cannot travel from one to the other across grid edges without crossing a road. Output the number of distant pairs.

Constraints

Key idea

Build an undirected graph on the N² cells. Connect (r,c) to its 4 neighbors except where a road separates them. Flood-fill components. For each cow record its component id. Group cows by component; if a component holds ci cows, the number of connected pairs is Σ C(ci,2). Distant pairs = C(K,2) − connected pairs.

Complexity target

O(N² + R + K). N=100 so N² = 104.

Reference solution (C++)

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

int N;
int idx(int r, int c) { return r * N + c; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int K, R; cin >> N >> K >> R;
    // blocked[a][b] = true if cell a and cell b have a road between them.
    set<pair<int,int>> blocked;
    for (int i = 0; i < R; ++i) {
        int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
        int a = idx(r1 - 1, c1 - 1), b = idx(r2 - 1, c2 - 1);
        blocked.insert({min(a,b), max(a,b)});
    }
    vector<int> comp(N * N, -1);
    int cid = 0;
    int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
    for (int s = 0; s < N * N; ++s) if (comp[s] == -1) {
        queue<int> q; q.push(s); comp[s] = cid;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            int r = u / N, c = u % N;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                int v = idx(nr, nc);
                if (blocked.count({min(u,v), max(u,v)})) continue;
                if (comp[v] != -1) continue;
                comp[v] = cid; q.push(v);
            }
        }
        ++cid;
    }
    map<int, ll> cnt;
    for (int i = 0; i < K; ++i) {
        int r, c; cin >> r >> c; cnt[comp[idx(r - 1, c - 1)]]++;
    }
    ll connected = 0;
    for (auto [_, v] : cnt) connected += v * (v - 1) / 2;
    ll total = (ll)K * (K - 1) / 2;
    cout << total - connected << "\n";
}

Pitfalls

What Silver February 2017 was actually testing