Appendix B: USACO Problem Set

This appendix provides a curated list of 20 USACO problems organized by topic. These problems are carefully selected to reinforce the techniques covered in this book. All are available for free on usaco.org.

How to Use This Problem Set

Work through these problems roughly in order. For each problem:

1. Read the problem carefully and try to solve it independently for at least 1–2 hours
2. If stuck, look at the hint below (not the full editorial)
3. If still stuck after another 30 minutes, read the editorial on the USACO website
4. After solving (or reading the editorial), implement the solution yourself from scratch

Learning happens most when you struggle and then understand — not when you read a solution passively.

Section 1: Simulation & Brute Force (Bronze)

Problem 1: Blocked Billboard

Contest: USACO 2017 December Bronze Topic: 2D geometry, rectangles Link: usaco.org — 2017 December Bronze

Description: Two billboards and a truck (all rectangles). Find the area of the billboards not covered by the truck.

Key Insight: Compute the intersection of the truck with each billboard. Area of billboard - area of intersection = visible area.

Techniques: 2D rectangle intersection, careful arithmetic Difficulty: ⭐⭐

Problem 2: The Cow-Signal

Contest: USACO 2016 February Bronze Topic: 2D array manipulation Link: usaco.org — 2016 February Bronze

Description: Given a pattern of characters in a K×L grid, "scale" it up by factor R (repeat each character R times in each direction).

Key Insight: Character at position (i,j) in the output comes from ((i-1)/R + 1, (j-1)/R + 1) in the input.

Techniques: 2D array indexing, integer division Difficulty: ⭐

Problem 3: Shell Game

Contest: USACO 2016 January Bronze Topic: Simulation Link: usaco.org — 2016 January Bronze

Description: Elsie plays a shell game. Track where a ball ends up after a sequence of swaps.

Key Insight: Track the ball's position through each swap. The pea starts under one of the three shells; try all three starting positions.

Techniques: Simulation, brute force over starting positions Difficulty: ⭐

Problem 4: Counting Haybales

Contest: USACO 2016 November Bronze Topic: Sorting, searching Link: usaco.org — 2016 November Bronze

Description: N haybales at positions. Q queries asking how many haybales are in range [A, B].

Key Insight: Sort haybale positions, then use binary search (lower_bound/upper_bound) for each query.

Techniques: Sorting, binary search Difficulty: ⭐⭐

Problem 5: Mowing the Field

Contest: USACO 2016 January Bronze Topic: Grid simulation Link: usaco.org — 2016 January Bronze

Description: FJ mows a field by following N instructions. Count how many cells he mows more than once.

Key Insight: Track all visited positions in a set/map. When a cell is visited again, it's double-mowed.

Techniques: Set/map for tracking visited cells, direction simulation Difficulty: ⭐⭐

Section 2: Arrays & Prefix Sums (Bronze/Silver)

Problem 6: Breed Counting

Contest: USACO 2015 December Bronze Topic: Prefix sums Link: usaco.org — 2015 December Bronze

Description: N cows each with breed 1, 2, or 3. Q queries: how many cows of breed B in range [L, R]?

Key Insight: Build a prefix sum array for each of the 3 breeds. Answer each query in O(1).

Techniques: Prefix sums, multiple arrays Difficulty: ⭐⭐

Problem 7: Hoof, Paper, Scissors

Contest: USACO 2019 January Silver Topic: DP Link: usaco.org — 2019 January Silver

Description: Bessie plays N rounds of Hoof-Paper-Scissors. She can change her gesture at most K times. Maximize wins.

Key Insight: DP state: (round, changes used, current gesture). See Chapter 6.2 for full solution.

Techniques: 3D DP Difficulty: ⭐⭐⭐

Section 3: Sorting & Binary Search (Bronze/Silver)

Problem 8: Angry Cows

Contest: USACO 2016 February Bronze Topic: Sorting, simulation Link: usaco.org — 2016 February Bronze

Description: Cows placed on a number line. One cow fires a "blast" that spreads outward, setting off other cows. Find the minimum initial blast radius to set off all cows.

Key Insight: Binary search on the blast radius. For a given radius, simulate which cows get set off.

Techniques: Binary search on answer, sorting, simulation Difficulty: ⭐⭐⭐

Problem 9: Aggressive Cows

Contest: USACO 2011 March Silver Topic: Binary search on answer Link: usaco.org — 2011 March Silver

Description: N stalls at given positions. Place C cows to maximize the minimum distance between any two cows.

Key Insight: Binary search on the answer (minimum distance). For each candidate distance, greedily check if C cows can be placed.

Techniques: Binary search on answer, greedy check Difficulty: ⭐⭐⭐

Problem 10: Convention

Contest: USACO 2018 February Silver Topic: Binary search on answer + greedy Link: usaco.org — 2018 February Silver

Description: N cows arrive at times t[i] and board M buses of capacity C. Minimize the maximum waiting time.

Key Insight: Binary search on the maximum wait time. For each candidate, greedily assign cows to buses.

Techniques: Binary search on answer, greedy simulation, sorting Difficulty: ⭐⭐⭐

Section 4: Graph Algorithms (Silver)

Problem 11: Closing the Farm

Contest: USACO 2016 January Silver Topic: DSU (Union-Find), offline processing Link: usaco.org — 2016 January Silver

Description: A farm has N fields and M paths. Remove fields one by one. After each removal, determine if the remaining fields are still all connected.

Key Insight: Reverse the process — add fields in reverse order. Use DSU to track connectivity as fields are added.

Techniques: DSU, reverse processing Difficulty: ⭐⭐⭐

Problem 12: Moocast

Contest: USACO 2016 February Silver Topic: DSU / BFS Link: usaco.org — 2016 February Silver

Description: N cows on a field. Cow i has walkie-talkie range p[i]. Can cow i directly contact cow j? Find the minimum range such that all cows can communicate (directly or via relays).

Key Insight: Binary search on the minimum range. For a given range, build a graph and check connectivity.

Techniques: Binary search on answer, BFS/DFS connectivity, or Kruskal's MST Difficulty: ⭐⭐⭐

Problem 13: BFS Shortest Path

Contest: USACO 2016 February Bronze: Milk Pails (modified) Topic: BFS on state space Link: usaco.org — 2016 February Bronze

Description: Two buckets with capacities X and Y. Fill/empty/pour operations. Find minimum operations to get exactly M liters in either bucket.

Key Insight: Model (amount in bucket 1, amount in bucket 2) as a graph state. BFS finds the minimum operations.

Techniques: BFS on state graph Difficulty: ⭐⭐⭐

Problem 14: Grass Cownoisseur

Contest: USACO 2015 December Silver Topic: SCC (Strongly Connected Components), BFS on DAG Link: usaco.org — 2015 December Silver

Description: Directed graph of pastures. Bessie can reverse one edge for free. Find the maximum number of pastures reachable in a round trip from pasture 1.

Key Insight: Contract SCCs into super-nodes, then BFS on the DAG. For each edge that could be reversed, check improvement.

Techniques: SCC, BFS, graph contraction Difficulty: ⭐⭐⭐⭐ (Gold-level thinking, Silver contest)

Section 5: Dynamic Programming (Silver)

Problem 15: Rectangular Pasture

Contest: USACO 2021 January Silver Topic: 2D prefix sums, DP Link: usaco.org — 2021 January Silver

Description: N cows on a 2D grid (all at distinct x and y coordinates). Count the number of axis-aligned rectangles that contain exactly K cows.

Key Insight: Sort by x, then for each pair of columns, use a DP over rows. 2D prefix sums for fast rectangle counting.

Techniques: 2D prefix sums, combinatorics Difficulty: ⭐⭐⭐

Problem 16: Lemonade Line

Contest: USACO 2017 February Bronze Topic: Greedy Link: usaco.org — 2017 February Bronze

Description: N cows. Cow i will join a lemonade line if there are at most p[i] cows already in line. Find the maximum number of cows in line.

Key Insight: Sort cows by patience (p[i]) in decreasing order. Greedily add each cow if possible.

Techniques: Sorting, greedy Difficulty: ⭐⭐

Problem 17: Tallest Cow

Contest: USACO 2016 February Silver Topic: Difference arrays Link: usaco.org — 2016 February Silver

Description: N cows in a line. H[i] is the height of cow i. Given pairs (A, B) meaning cow A can see cow B (implies all cows between them are shorter), find maximum possible height of each cow.

Key Insight: Use difference arrays to track height constraints. For each (A, B) pair, all cows strictly between A and B must be shorter than both.

Techniques: Difference arrays, prefix sums Difficulty: ⭐⭐⭐

Section 6: Mixed (Silver)

Problem 18: Balancing Act

Contest: USACO 2018 January Silver Topic: Tree DP, centroid Link: usaco.org — 2018 January Silver

Description: Find the "centroid" of a tree — the node whose removal creates the most balanced partition (minimizes the size of the largest remaining component).

Key Insight: Compute subtree sizes via DFS. For each node, the largest component when it's removed is max(subtree size of each child, N - subtree size of this node).

Techniques: Tree DP, subtree sizes Difficulty: ⭐⭐⭐

Problem 19: Concatenation Nation

Contest: USACO 2016 January Bronze Topic: String manipulation, sorting Link: usaco.org — 2016 January Bronze

Description: Given N strings, for each pair (i, j) with i < j, form the string s_i + s_j. Count how many such concatenated strings are palindromes.

Key Insight: Check each pair; O(N² × L) where L is string length. For N ≤ 1000, this works.

Techniques: String manipulation, palindrome check Difficulty: ⭐⭐

Problem 20: Berry Picking

Contest: USACO 2020 January Silver Topic: Greedy, DP Link: usaco.org — 2020 January Silver

Description: Bessie picks berries from N trees. She has K baskets; each basket can hold berries from only one tree. Maximize total berries given that each basket in a group must hold the same amount.

Key Insight: Optimal: use K/2 baskets for Bessie, K/2 for Elsie. Sort trees. For each possible basket-size for Elsie's trees, binary search to find Bessie's optimal allocation.

Techniques: Sorting, binary search, greedy Difficulty: ⭐⭐⭐⭐

Quick Reference: Problems by Technique

Tips for Practicing

1. Use the USACO training gate at train.usaco.org for auto-grading
2. Read editorials at usaco.org after each problem — even for problems you solved
3. Keep a problem journal — write the key insight for each problem you solve
4. Difficulty progression: do easy problems from recent years, then medium from older years

Additional Problem Sources

CSES Problem Set at cses.fi/problemset is especially recommended — it has ~300 carefully curated problems covering all USACO Silver topics, auto-graded, free.