U USACO Prep

USACO 2019 US Open · Bronze · all three problems

← Full 2019 US Open set · Official results

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

Subtask structure

Single test, no subtasks — full credit on a fixed 10×10 grid.

Statement

A 10×10 grid contains one barn 'B', one lake 'L', some impassable rocks 'R', and empty cells '.'. Cows stand on empty cells and pass buckets to 4-adjacent neighbours. Find the minimum number of cows needed so that a connected chain links the lake to the barn (the lake-adjacent cow and barn-adjacent cow are each counted; the lake and barn cells themselves are not cows).

Constraints

Key idea

Plain BFS on a 4-connected grid from L (or its neighbours) to B, treating '.' and the endpoints as passable and 'R' as blocked. The answer is shortest-path-length minus 1 (don't count the endpoint cells themselves). On 100 cells it's instant.

Complexity target

O(100) BFS — trivial.

Reference solution (C++)

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

int main() {
    vector<string> g(10);
    for (auto& r : g) cin >> r;

    int sx = -1, sy = -1, tx = -1, ty = -1;
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j) {
            if (g[i][j] == 'L') sx = i, sy = j;
            if (g[i][j] == 'B') tx = i, ty = j;
        }

    // BFS from L; passable cells are '.', 'L', 'B'. 'R' is blocked.
    vector<vector<int>> dist(10, vector<int>(10, -1));
    queue<pair<int,int>> q;
    dist[sx][sy] = 0; q.push({sx, sy});
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= 10 || ny < 0 || ny >= 10) continue;
            if (g[nx][ny] == 'R') continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    // # cows = path-length - 1 (exclude L and B themselves, but include neighbours).
    cout << dist[tx][ty] - 1 << "\n";
}

Pitfalls

Problem 2 — Milk Factory

Subtask structure

No partial-credit subtasks — single full-credit test set with N ≤ 100.

Statement

A factory has N stations and N−1 directed conveyor belts ai → bi. The underlying undirected graph is a tree. Find the smallest station id that every other station can reach by following directed belts (i.e. the unique "sink" reachable from all sources). If no such station exists, print −1.

Constraints

Key idea

N ≤ 100 — brute force. For every candidate station v, do a directed DFS on the reverse graph from v; if it visits all N stations, then every station can reach v. Return the smallest such v.

Complexity target

O(N · (N + edges)) = O(N²) ≈ 104 ops. Trivial.

Reference solution (C++)

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

int N;
vector<vector<int>> radj;  // reverse adjacency
vector<char> vis;

void dfs(int u) {
    vis[u] = 1;
    for (int v : radj[u]) if (!vis[v]) dfs(v);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    radj.assign(N + 1, {});
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b;
        radj[b].push_back(a);  // reverse edge: from b we can walk back to a
    }
    for (int v = 1; v <= N; ++v) {
        vis.assign(N + 1, 0);
        dfs(v);
        int cnt = 0;
        for (int i = 1; i <= N; ++i) if (vis[i]) ++cnt;
        if (cnt == N) { cout << v << "\n"; return 0; }
    }
    cout << -1 << "\n";
}

Pitfalls

Problem 3 — Cow Evolution

Subtask structure

Single full-credit test set with N ≤ 25.

Statement

There are N sub-populations of cows; each has a set of characteristic strings (e.g. "horns", "spots"). A "proper" evolutionary tree is one where each feature evolves on exactly one edge. Decide whether such a tree exists for the given feature sets. Output "yes" or "no".

Constraints

Key idea

Equivalent reformulation: a proper tree exists iff no two features f₁, f₂ "cross" — i.e. the four combinations (both, only f₁, only f₂, neither) cannot all appear across the N sub-populations. So enumerate every pair (f₁, f₂) of distinct features and check whether all four bit-patterns 00/01/10/11 occur as restrictions of the input sets to {f₁, f₂}. If any pair hits all four, print "no"; otherwise "yes".

Complexity target

O(F² · N) where F is the number of distinct features. F, N ≤ 25 — trivial.

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;
    map<string, int> id;             // feature -> bit index
    vector<int> mask(N, 0);          // bitmask of features per population

    for (int i = 0; i < N; ++i) {
        int K; cin >> K;
        for (int j = 0; j < K; ++j) {
            string s; cin >> s;
            if (!id.count(s)) { int n = id.size(); id[s] = n; }
            mask[i] |= 1 << id[s];
        }
    }
    int F = id.size();
    // Pair check: for every (a,b), do all 4 patterns appear?
    for (int a = 0; a < F; ++a)
      for (int b = a + 1; b < F; ++b) {
        int seen = 0;
        for (int i = 0; i < N; ++i) {
            int pa = (mask[i] >> a) & 1, pb = (mask[i] >> b) & 1;
            seen |= 1 << (pa * 2 + pb);
        }
        if (seen == 15) { cout << "no\n"; return 0; }
      }
    cout << "yes\n";
}

Pitfalls

What Bronze 2019 US Open was actually testing