U USACO Prep

USACO 2019 January · Silver · all three problems

← Full January 2019 set · Official results

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

Statement

Farmer John has a farm laid out as a tree on N fields with N−1 paths between them. He wants to plant a type of grass on every path so that any two paths sharing a field have different types. Determine the minimum number of grass types needed.

Constraints

Key idea

"Edges sharing a vertex must differ" is exactly edge coloring. For a tree the edge-chromatic number equals the maximum vertex degree Δ (a special case of Vizing's theorem). So compute Δ in one pass: count adjacency-list sizes and take the maximum.

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; cin >> N;
    vector<int> deg(N + 1, 0);
    for (int i = 0; i < N - 1; ++i) {
        int u, v; cin >> u >> v;
        ++deg[u];
        ++deg[v];
    }
    int ans = 0;
    for (int i = 1; i <= N; ++i) ans = max(ans, deg[i]);
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Sleepy Cow Sorting (Silver)

Statement

Given a permutation a1..N, in one move you take the first cow and reinsert it somewhere into the remaining suffix (which must stay in its current order). Output (1) the minimum number K of moves to sort the line, and (2) for each of the K moves, how many cows the chosen front cow must be "stepped past" to land in the right slot inside the sorted suffix.

Constraints

Key idea

As in Bronze, K = N − L where L is the length of the longest already-sorted suffix. For the second output: process the first K cows left-to-right. When inserting cow ai, we must count how many cows currently "after position i" in the line are less than ai. Maintain a Fenwick (BIT) over cow labels indexed by value: initialize it with the sorted suffix (values seen at positions K..N−1). For each i = 0..K−1 ask "how many in BIT are < a[i]?", then insert a[i].

Complexity target

O(N log N) via a Fenwick tree of counts.

Reference solution (C++)

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

struct BIT {
    int n; vector<int> t;
    BIT(int n) : n(n), t(n + 1, 0) {}
    void upd(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; }
    int qry(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(N);
    for (auto& x : a) cin >> x;

    int i = N - 1;
    while (i > 0 && a[i - 1] < a[i]) --i;
    int K = i; // number of cows to move
    cout << K << "\n";

    BIT bit(N);
    for (int j = K; j < N; ++j) bit.upd(a[j], 1); // sorted suffix already in line
    for (int j = 0; j < K; ++j) {
        // Cows currently after a[j] and smaller than a[j] must be stepped past.
        int steps = bit.qry(a[j] - 1);
        cout << steps << " \n"[j == K - 1];
        bit.upd(a[j], 1); // a[j] joins the suffix
    }
}

Pitfalls

Problem 3 — Icy Perimeter

Statement

Given an N×N grid of '#' (ice cream) and '.' (empty), find the 4-connected '#' component with the largest area. Break ties by smallest perimeter. Output its area and perimeter.

Constraints

Key idea

Flood-fill (BFS/DFS) each '#' component. While visiting a cell, add 1 to area; for each of its 4 neighbors, if the neighbor is out of bounds or '.', add 1 to perimeter. Track the best (area, −perimeter) pair lexicographically (largest area, then smallest perimeter).

Complexity target

O(N²) total.

Reference solution (C++)

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

int N;
vector<string> g;
vector<vector<char>> seen;
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

pair<int,int> flood(int sr, int sc) {
    int area = 0, peri = 0;
    stack<pair<int,int>> st;
    st.push({sr, sc}); seen[sr][sc] = 1;
    while (!st.empty()) {
        auto [r, c] = st.top(); st.pop();
        ++area;
        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 || g[nr][nc] == '.') {
                ++peri;
            } else if (!seen[nr][nc]) {
                seen[nr][nc] = 1;
                st.push({nr, nc});
            }
        }
    }
    return {area, peri};
}

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

    int bestA = 0, bestP = INT_MAX;
    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j)
        if (g[i][j] == '#' && !seen[i][j]) {
            auto [a, p] = flood(i, j);
            if (a > bestA || (a == bestA && p < bestP)) { bestA = a; bestP = p; }
        }
    cout << bestA << " " << bestP << "\n";
}

Pitfalls

What Silver January 2019 was actually testing