U USACO Prep

USACO 2021 February · Bronze · 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 — Year of the Cow

Statement

Bessie was born in a year of the Ox. You are given N relational statements, each of the form "cow X was born in the previous/next year-of-<zodiac> relative to cow Y." Using the 12-animal Chinese zodiac cycle (Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat), compute the absolute age difference (in years) between Bessie and Elsie.

Constraints

Key idea

Maintain a year[name] map keyed by cow name, with year["Bessie"] = 0. For each statement "X was born in the previous/next year-of-Z relative to Y", scan years from Y's year stepping by ±1 until you find the nearest occurrence of zodiac sign Z (a year y has zodiac (y mod 12) in some fixed ordering with Ox = 0). The answer is |year["Elsie"] - year["Bessie"]|.

Complexity target

O(N · 12) — at most 12 single-step probes per statement to find the next/previous occurrence of a zodiac sign.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> zodiac = {"Ox","Tiger","Rabbit","Dragon","Snake","Horse",
                              "Goat","Monkey","Rooster","Dog","Pig","Rat"};
    auto idx = [&](const string& s) {
        for (int i = 0; i < 12; ++i) if (zodiac[i] == s) return i;
        return -1;
    };

    int N; cin >> N;
    unordered_map<string,int> year;
    year["Bessie"] = 0;     // Bessie was born in year 0, an Ox year.

    for (int i = 0; i < N; ++i) {
        // Format: <X> born in the <previous|next> <Z> year from <Y>
        string X, _in, _born, _the, dir, Z, _year, _from, Y;
        cin >> X >> _born >> _in >> _the >> dir >> Z >> _year >> _from >> Y;
        int step = (dir == "previous") ? -1 : 1;
        int y = year[Y] + step;
        int target = idx(Z);
        // Ox = year 0, so zodiac of year y = ((y mod 12) + 12) mod 12.
        while (((y % 12) + 12) % 12 != target) y += step;
        year[X] = y;
    }
    cout << abs(year["Elsie"] - year["Bessie"]) << "\n";
}

Pitfalls

Problem 2 — Comfortable Cows

Statement

Farmer John adds N cows to a 2D grid one at a time, each at a distinct (x, y). A cow is "comfortable" if it has exactly three orthogonal neighbours (up/down/left/right) currently containing a cow. After each addition, output the current total number of comfortable cows.

Constraints

Key idea

Track a hash set (or 1001×1001 bit grid) of occupied cells, and a counter comfort. When adding cow at (x, y): count its current occupied neighbours k. The newly placed cow is comfortable iff k == 3, so adjust comfort by +1 if so. Then, for each of its (up to 4) occupied neighbours, recompute their comfort status: if a neighbour's neighbour-count went from 3 to 4 decrement comfort; if it went from 2 to 3 increment comfort. Print comfort after each step.

Complexity target

O(N) with constant per-step work (≤ 4 neighbour updates).

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;
    const int S = 1005;
    static bool occ[S][S] = {};
    auto nbrCount = [&](int x, int y) {
        int c = 0;
        if (x > 0)         c += occ[x - 1][y];
        if (x + 1 < S)     c += occ[x + 1][y];
        if (y > 0)         c += occ[x][y - 1];
        if (y + 1 < S)     c += occ[x][y + 1];
        return c;
    };
    int comfort = 0;
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    for (int i = 0; i < N; ++i) {
        int x, y; cin >> x >> y;
        // Place the new cow.
        occ[x][y] = true;
        if (nbrCount(x, y) == 3) ++comfort;
        // Each previously placed neighbour gains one neighbour.
        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]) continue;
            int c = nbrCount(nx, ny);
            if (c == 3) ++comfort;       // was 2 before this placement
            else if (c == 4) --comfort;  // was 3 before this placement
        }
        cout << comfort << "\n";
    }
}

Pitfalls

Problem 3 — Clockwise Fence

Statement

For each of T test cases you are given a string of characters in {N, E, S, W} describing the walk Bessie takes around a closed fence; each character is a 1-metre step in that compass direction. The walk returns to its start and the enclosed region is non-self-intersecting. Output CW if Bessie walked clockwise around the region (interior on her right) and CCW otherwise.

Constraints

Key idea

Convert the walk to vertices (xi, yi) and compute twice the signed area via the shoelace formula 2A = Σ (xi · yi+1 − xi+1 · yi). With the standard math-orientation (y increases northward), 2A > 0 means counter-clockwise; 2A < 0 means clockwise. Output accordingly.

Complexity target

O(|s|) per test, trivial.

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 T; cin >> T;
    while (T--) {
        string s; cin >> s;
        ll x = 0, y = 0, twoA = 0;
        for (char c : s) {
            ll nx = x, ny = y;
            if      (c == 'N') ++ny;
            else if (c == 'S') --ny;
            else if (c == 'E') ++nx;
            else               --nx;   // 'W'
            twoA += x * ny - nx * y;   // shoelace contribution for edge (x,y)->(nx,ny)
            x = nx; y = ny;
        }
        cout << (twoA > 0 ? "CCW" : "CW") << "\n";
    }
}

Pitfalls

What Bronze February 2021 was actually testing