U USACO Prep

USACO 2021 February · Silver · all three problems

← Full February 2021 set · Official results

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

Statement

N cows are placed on a grid one at a time. A cow is "comfortable" if it has exactly three orthogonal neighbours. After each placement, Farmer John keeps adding cows at empty cells to "stabilise" the pasture: whenever a cow is comfortable, FJ adds a cow at its empty orthogonal neighbour; this may create new comfortable cows in turn. For each step i = 1..N, output the total number of cows FJ has added after stabilising the first i placements.

Constraints

Key idea

Maintain occ[x][y] and a counter added. After placing a user cow, push it on a queue. BFS-style propagation: pop a cell, count its occupied neighbours; if exactly 3, find the one empty orthogonal neighbour, fill it (set occ, increment added) and push both the filled cell and its (newly degree-changed) occupied neighbours on the queue. Stop when the queue drains. Each cell is filled at most once, so total propagation work is bounded by the grid area (≤ 106).

Complexity target

O((N + grid-cells-ever-filled) · 4) ≈ O(106) worst case.

Reference solution (C++)

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

static const int S = 1005;
static bool occ[S][S];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

inline int nbrCount(int x, int y) {
    int c = 0;
    for (int d = 0; d < 4; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx >= 0 && nx < S && ny >= 0 && ny < S && occ[nx][ny]) ++c;
    }
    return c;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    long long added = 0;
    queue<pair<int,int>> q;
    while (N--) {
        int x, y; cin >> x >> y;
        if (!occ[x][y]) { occ[x][y] = true; q.push({x, y}); }
        while (!q.empty()) {
            auto [a, b] = q.front(); q.pop();
            if (!occ[a][b]) continue;
            if (nbrCount(a, b) == 3) {
                for (int d = 0; d < 4; ++d) {
                    int nx = a + dx[d], ny = b + dy[d];
                    if (nx < 0 || nx >= S || ny < 0 || ny >= S) continue;
                    if (!occ[nx][ny]) {
                        occ[nx][ny] = true;
                        ++added;
                        q.push({nx, ny});
                        // The filled cell's other neighbours may now be comfortable.
                        for (int e = 0; e < 4; ++e) {
                            int mx = nx + dx[e], my = ny + dy[e];
                            if (mx >= 0 && mx < S && my >= 0 && my < S && occ[mx][my])
                                q.push({mx, my});
                        }
                        break;  // a cow with 3 neighbours has exactly one empty side
                    }
                }
            }
        }
        cout << added << "\n";
    }
}

Pitfalls

Problem 2 — Year of the Cow

Statement

Bessie wants to visit N ancestors, each born ai years ago (ai > 0). She starts in the present, walks the timeline at 1 year/step, and may use a time portal up to K times; each portal use teleports her exactly 12 years backwards (instantly, free of "time spent"). She must visit every ancestor and return to the present. Minimise the total number of years walked.

Constraints

Key idea

Sort the ancestors by year (most recent first). Bessie must walk from year 0 down to the oldest ancestor and back, so baseline cost is 2 · max(a). Between consecutive ancestors (after dedup), if their year gap is g years, a single portal-use saves 12 · floor(g / 12) years (it teleports 12-year multiples). Greedy: collect savings 12 · floor(gap/12) over every consecutive gap (including the final "return" gap from oldest to 0, which is just a, but the return leg shares the same path so cannot be re-portalled — handled by only counting forward gaps), sort descending, take the top K, subtract from baseline.

Complexity target

O(N log N) sorting.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<ll> a(N);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    // Baseline: walk to the oldest ancestor and back.
    // Each consecutive gap g admits a 12*(g/12)-year portal saving (used at most once per gap).
    ll oldest = a.back();
    ll baseline = 2 * oldest;
    vector<ll> save;
    save.reserve(a.size());
    save.push_back(12 * (a.front() / 12));   // gap from year 0 to nearest ancestor
    for (size_t i = 1; i < a.size(); ++i)
        save.push_back(12 * ((a[i] - a[i - 1]) / 12));

    sort(save.rbegin(), save.rend());
    ll total = baseline;
    for (int i = 0; i < K && i < (int)save.size(); ++i) total -= save[i];
    cout << total << "\n";
}
// [verify exact formulation, especially "return to present" cost]
//   https://usaco.org/index.php?page=viewproblem2&cpid=1111

Pitfalls

Problem 3 — Just Green Enough

Statement

Given an N×N grid of integers in [1, 200], count the number of axis-aligned rectangular sub-grids whose minimum value is exactly 100.

Constraints

Key idea

Let f(t) = number of rectangles whose minimum is ≥ t. The answer is f(100) − f(101). To compute f(t): build a 0/1 grid where 1 means value ≥ t, then count rectangles entirely of 1s. For each column compute "run length up to row i"; for each row treat that array as histogram bar heights and count submatrices ending at row i by summing, for each column, the heights weighted by how far left the height stays ≥ the current minimum — the standard monotonic-stack "all-1 submatrices" trick in O(N²) per evaluation. Total O(N²).

Complexity target

O(N²) for each of two evaluations of f, so O(N²) overall — about 2.5 · 105 ops.

Reference solution (C++)

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

// Count submatrices of all-1s in a binary N x N grid using monotonic stacks.
ll countAllOnes(const vector<vector<int>>& b) {
    int N = (int)b.size();
    vector<int> h(N, 0);
    ll total = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) h[j] = b[i][j] ? h[j] + 1 : 0;
        // sum[j] = number of all-1 rectangles with bottom-right corner at (i, j).
        vector<ll> sum(N, 0);
        stack<int> st;        // increasing heights
        for (int j = 0; j < N; ++j) {
            while (!st.empty() && h[st.top()] >= h[j]) st.pop();
            int prev = st.empty() ? -1 : st.top();
            sum[j] = (ll)(j - prev) * h[j] + (prev >= 0 ? sum[prev] : 0);
            total += sum[j];
            st.push(j);
        }
    }
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<vector<int>> g(N, vector<int>(N));
    for (auto& r : g) for (auto& v : r) cin >> v;

    vector<vector<int>> b100(N, vector<int>(N)), b101(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j) {
        b100[i][j] = (g[i][j] >= 100);
        b101[i][j] = (g[i][j] >= 101);
      }
    cout << (countAllOnes(b100) - countAllOnes(b101)) << "\n";
}

Pitfalls

What Silver February 2021 was actually testing