USACO Bronze practice problems explained: simulation and complete search
8 min readUpdated
Most USACO Bronze problems use one of two ideas: simulate exactly what the problem describes, or try every possible answer when the input is small. This guide solves one original practice problem of each kind in Java and shows how to tell, from the limits, whether trying everything is fast enough.
Problem 1 (simulation): passing the ball
N students stand in a circle, numbered 0 to N-1. Student 0 holds the ball. Each turn, the student holding the ball passes it K places clockwise. After T turns, who holds the ball? The direct approach is to do exactly what the story says, one turn at a time.
public class PassTheBall {
public static int holderAfter(int n, int k, int turns) {
int holder = 0;
for (int t = 0; t < turns; t++) {
holder = (holder + k) % n;
}
return holder;
}
public static void main(String[] args) {
System.out.println(holderAfter(5, 2, 3));
System.out.println(holderAfter(7, 3, 10));
System.out.println(holderAfter(4, 4, 100));
}
}
Output
1 2 0
The % (remainder) operator wraps the position back around the circle. Simulation problems often hide a wrap-around like this.
Problem 2 (complete search): the best fence
You are given the heights of N fence posts in a row. Choose two posts; the score is the distance between them multiplied by the shorter post's height. Find the best score. With N up to 1,000, checking every pair (about 500,000 pairs) is easily fast enough.
public class BestFence {
public static int bestScore(int[] heights) {
int best = 0;
for (int i = 0; i < heights.length; i++) {
for (int j = i + 1; j < heights.length; j++) {
int score = (j - i) * Math.min(heights[i], heights[j]);
best = Math.max(best, score);
}
}
return best;
}
public static void main(String[] args) {
System.out.println(bestScore(new int[] {1, 8, 6, 2, 5, 4, 8, 3, 7}));
System.out.println(bestScore(new int[] {4, 4}));
}
}
Output
49 4
Is trying everything fast enough?
A useful rule: a contest computer runs roughly 100 million simple steps per second. Estimate your loops from the limits before writing code.
| Largest N | Loops that usually fit | Typical Bronze idea |
|---|---|---|
| Up to about 20 | Every subset (2^N) | Try all combinations |
| Up to about 100 | Three nested loops (N^3) | Try every triple |
| Up to about 1,000 to 5,000 | Two nested loops (N^2) | Try every pair |
| Up to about 1,000,000 | One loop or a sort (N log N) | Simulate once, or sort then scan |
A routine for every Bronze problem
- Read the limits first and decide whether complete search fits.
- Work the sample input by hand until you could explain it to a friend.
- Write the simplest correct solution.
- Test the smallest case, the largest case and cases where all values are equal.
- Only then think about speeding it up.
Frequently asked questions
What topics are in USACO Bronze?
Mostly simulation, complete search (trying every option when the input is small), sorting and careful reading. Advanced algorithms are not needed.
Is Java fast enough for USACO?
Yes for Bronze and Silver. Use BufferedReader for large inputs and the same solutions as C++ will usually pass.
How many problems should I practise before a USACO contest?
Quality matters more than count: 2 to 3 past problems a week, each fully understood and re-coded, beats racing through dozens.
Learn it step by step
Practise this, step by step
Short lessons with quizzes, practice and interview questions, from your first program to job-ready.