What is USACO?

The United States of America Computing Olympiad, or USACO, is a programming competition that occurs four times a year (December, January, February, and March). USACO’s goal is to select the official USA team, which competes in the International Olympiad in Informatics (IOI).

​

What is the format of the competition?

USACO is a digital test, which can be taken remotely, on the official usaco.org website. It is split into 4 divisions of varying difficulty: Bronze, Silver, Gold, and Platinum. Everyone begins in the Bronze division. Typically, each of the four divisions contains three equally weighted problems that add to a total of 1000 points, meaning each problem is worth around 333 points. Each problem contains between 10 to 30 test cases, which are worth an identical number of points. A test case is a set of numbers and/or characters that the USACO judging server will use to test whether or not your code correctly solves the problem. For instance, if a problem consisted of 15 test cases, each test case would be worth approximately 333 / 15 = 22 points. In general, the cutoff to advance to the next division is 750 or 800 points. Contestants must submit their solutions utilizing C, C++, Java, or Python in the allotted time. The contestant must read the problem statement and submit their solutions within a contiguous period that begins once they choose to start the contest. Though the designated time for each contest varies, a person can expect to receive 4 hours on the December, January, and February contests and 5 hours on the Open contest in March. The testing window is generally from Friday through Monday.

 

For Platinum division participants, contestants located in the USA can choose to receive a certified score by starting on Saturday at 12:00 ET, which is when Platinum problems are first released. While receiving a certified score is not mandatory, USACO introduced the scoring method to ensure contest integrity; USACO highly encourages contestants to get their certified score if their goal is to participate in the USACO summer training camp, which consists of around 20 finalists who performed particularly well on the Platinum contests that year.

 

What is tested in the competition?

As the contest is split into four distinct divisions, the topics tested in each division vary. Each of the divisions may include topics required for previous divisions, in addition to rare topics not included in the above lists. 

​

Bronze: A Bronze contestant can expect to be tested on brute force techniques (simulation, complete search, recursion), sorting, greedy, graph, and various ad hoc problems.

As suggested by its name, brute force algorithms test all possibilities, generally to determine the number of satisfactory situations. Sorting problems generally require you to sort the input before processing, allowing you to simplify calculations, and thereby speeding up the algorithm such that it will run within the time constraints. Greedy problems involve taking the locally optimal decision to eventually come up with the globally optimal decision. Graph problems are problems that involve nodes and edges. They often make use of brute force techniques at the Bronze level. Ad hoc problems are simply problems that do not fall into any standard categories. Such problems require some creativity to solve.

​

Silver: In addition to Bronze topics, a Silver contestant can expect to be tested on prefix sums, two pointers, sorting, binary search, graph traversal (depth first search and breadth first search), flood fill, and bitwise operations. Prefix sums involve pre-computing the sum of the first “x” elements of an array to quickly find the sum of any subarray in constant time. It is especially useful in problems that ask you about range sums. Two pointers make use of iterating two “pointers” (that represent indices) through an array to find a pair of indices that satisfy a certain condition. Two pointer algorithms run in linear time as the pointers only move in one direction. As in Bronze, sorting is important because it allows you to simplify calculations to optimize your algorithm. Furthermore, sorting allows you to run a binary search on your array. Binary search allows you to find a target value in a sorted array of “n” elements in log  time Binary search is especially useful in problems where all numbers larger than a certain number will satisfy the condition, while all other numbers will not, or vice versa. One of the most frequent algorithms used in Silver problems is graph traversal algorithms, such as DFS and BFS. These algorithms can also be used to floodfill in order to find connected components in a graph. Lastly, bitwise operations (eg. AND, OR, XOR, etc) sometimes appear in Silver problems, though these occur quite rarely.

​

Gold: A Gold contestant can expect to be tested on math (modular arithmetic and combinatorics), dynamic programming (including Knapsack, paths on grids, and bitmask), graphs (shortest path algorithms, disjoint set union, topological sort, and minimum spanning trees), complex data structures (sliding window and point update range sum), and trees (Euler tour and dynamic programming on trees). Gold problems make use of Silver techniques in addition to a plethora of other algorithms. Number theory, especially modular arithmetic, and combinatorial knowledge (eg. the product rule for independent events) can appear in Gold problems. However, the most well-known algorithm in the Gold division is dynamic programming, or DP. DP is the idea of speeding up naive brute force recursive solutions through memoization; in other words, DP allows you to split the problem into smaller subtasks that are generally easier to solve. A comprehensive list of DP topics can be found here. Similarly to Silver, Gold requires various graph algorithms. Due to the vast number of graph algorithms, we highly recommend looking over the USACO Guide webpage. Some rarer topics in Gold include data structures, such as sliding windows (similar to two-pointers) and point update range sum (a more advanced version of prefix sums that allows you to alter the values in a range as well by the use of segment trees). Lastly, Gold topics can touch on tree algorithms, such as the Euler tour technique, which is a data structure used to view a tree as an array to update and query subtrees more efficiently.

​

Platinum: A Platinum contestant can expect to be tested on range queries (segment trees and sweep line), trees (primarily binary jumping), and geometry (primarily convex hull).

A more comprehensive guide on what may be tested can be found on USACO Guide.

​

What can I do to prepare for USACO?

To prepare adequately for USACO, the USACO Guide serves as a phenomenal free resource to follow. By working through every problem in your respective division, you should have an extraordinarily high chance of qualifying for the next division. For additional practice, Codeforces provides thousands of high-quality competitive programming problems, sorted by difficulty and topic.

​

General tips!

• Practice. Though perhaps a cliche, the importance of practice cannot be overstated. A familiarity and deep understanding of each algorithm is critical to USACO. Once again, the USACO Guide and Codeforces are phenomenal free resources.

• Time management. The problems are NOT sorted in order of difficulty. Read each problem at the start of the contest and begin to work on the easiest problems. If you are unable to make nontrivial progress on a problem in 15 minutes, it may be time to start another problem.

• Debugging. Debugging is never fun and can take a long time. While debugging, you need to be able to quickly deduce whether your code is having a runtime error, syntax error, or logical error. The first two errors should be relatively easy to fix, though the latter may take a lot of time. It is highly suggested, especially for the later divisions, to learn how to stress test.

• Thinking. It is highly unproductive to stare at a problem statement! If you do not think of a solution idea immediately after reading the problem, come up with your own test cases. Noticing patterns among test cases is key to finding a solution.

• Have fun! After all, the goal of USACO is to help inspire you to pursue computer science.

​

This page was written by our USACO Subject Expert, Hansen He.