The Essential USACO Guide

What is in the Essential USACO Guide?

Within the Essential USACO Guide you will learn more about What is the USACO, contest mechanics, choosing a language, and how to prepare for the competition. Additionally there are details about program speed and why this is important, as well as contest strategy, tips, and tricks.

What is the USACO?

In order to start this USACO Guide, we first must define that The USA Computing Olympiad (“USACO”, https://www.usaco.org ) is a programming competition aimed at high school students in the US, but in practice middle school and high school students participate from all around the world. The contest is for individuals competing online, so anyone with a computer and an internet connection can participate.

The USACO competition is fairly prestigious, as it is a national qualifying contest. Like similar contests such as the USA Math Olympiad or USA Physics Olympiad, the USA Computing Olympiad’s top 4 students represent the USA in the International Olympiad of Informatics (“IOI”). Note that although non-US students can participate in the USACO, they cannot be part of the USA IOI team even if they rank top 4 in the US.

There are four contests a year, typically in December, January, February, and March. Each contest occurs over a weekend (Friday – Monday, US Time), and students must login during that time with a free account to participate. Once the student clicks on a ‘start’ button on the website, they will be given 4 hours to submit the code for three computer programs that solve three ‘problems’. However, the March contest regularly lasts 5 hours instead of 4 hours, and is therefore called the “US Open”, even though it is otherwise identical to the other contests.

During each USACO contest students are split into levels (“divisions”): bronze, silver, gold, and platinum. New students are placed in the ‘bronze’ division and can only work on bronze problems. The contest organizers set a threshold score for each contest, and if students exceed that score, they get promoted to the next division (e.g. from Bronze to Silver). Thus, students who make it to Silver or beyond often include this accomplishment on their college applications or future resume’s when applying for jobs.

Students can see their rank in the profile of their free online account on usaco.org . Students who score well in Gold or Platinum division problems also get their names posted on the USACO website ( e.g. http://usaco.org/current/data/open21_gold_results.html ). The top 16 students in platinum are invited to a in-person ‘camp’, where USACO organizers pick the 4 students of the USA representative team.

Contest Mechanics

The USACO is an online contest where student code is run against ‘test cases’. The student programs produce no graphical output, and there is no interaction with any user interface. Instead, the program reads in an input file (or sometimes reads a file from console input), typically containing a list of numbers, and writes an output file (which are often also numbers). These output files are compared against the correct values, and the student’s score is computed by how many outputs match the expected outputs.

Here’s an example of a problem written in the format of the USACO:

Problem: “Given a number, N, where N is between 1 and 1000000000, print the sum of all even numbers between 2 and N (inclusive)”

Example Solution (in Java). Note that in actual contests, filenames “input.in” and “output.out” may differ:

import java.io.*;
import java.util.Scanner;
public class Example {
	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner("input.in");
		int n = sc.nextInt();
		int output = 0;
		for(int i = 2; i <= n; i += 2) output += i;
		PrintWriter pw = new PrintWriter("output.out");
		pw.print(output);
		pw.close();
		sc.close();
	}
}

Once the student writes a solution, such as the one above, they upload the file to the USACO website for grading, and the website tries many (for example 10) input files (“input.in”). For each input file, the student’s code can exhibit one of the following common behaviors:

1. The code cannot be run because it does not compiled (“Compile error”)
2. The code runs, but it takes too long to print the output. Programs written in Java or Python are given 4 seconds to produce an output. Programs written in C or C++ are given 2 seconds.
3. The code runs out of memory (typically 256 megabytes) or crashes during execution
4. The code completes but prints the wrong answer (the output file differs from the ‘correct’ output).
5. The code completes and prints the right answer

For example, if the problem has 10 such problems each weighted 30 points, then the student will score between 0 to 300 for this problem based off of the number of times it completes and prints the right answer.

Cheating

This USACO Guide wants to make sure prospective participants know that cheating is not tolerated. Students who are caught doing any of the following things may be banned permanently from participating:

1. Creating multiple accounts, e.g. with a name other than their real name
2. Collaborating with other people during the contest
3. Copying code from other contest participants. The USACO uses algorithms to detect similarities between student solutions.
4. Uploading code that attempts to bypass or evade the grading system (this is also inhibited by the grading system which prevents the code from accessing other students’ code as well as the internet)

Choosing a language

As part of this USACO Guide we want you to know that the competition supports several programming languages, including C, C++, Java, Python 2, and Python 3. According to the USACO rules “We generally try to ensure that all problems are fully solvable in C/C++/Java, and that all bronze-level problems are also fully-solvable in Python.” Therefore, students are recommended to do the contest in either Java or C++, since silver and higher level problems may not be solvable in Python.

Advantages of Java

One goal of this USACO Guide is to let prospective participants know that KTBYTE generally recommends Java for most students, since this is also the language used on the AP Computer Science A exam. A Java program executes slightly slower than a C++ program, but this is more than compensated by the 4 seconds of execution time the USACO allocates to Java, compared to the 2 seconds allocated to C++ programs. Since JVM runtime initialization and array allocation overhead often contribute to 200 to 500 milliseconds of execution time, students often have more freedom when writing in Java as well.

Another advantage of Java is that students don’t need to switch languages if they also want to write graphical applications, cell phone apps, and web servers.

Advanced note: Students who choose to use Java should note that the competition encourages pre-allocating arrays, and using speed efficient data-structures such as ArrayList rather than LinkedList. There are also slight performance advantages when using StringTokenizer over Scanner.

Advantages of C++

C++ is an older language than Java, and therefore has had a long history of popularity in programming contests. Many other contests, especially at the collegiate level, prefer C++, since they may not give extra time for Java/JVM programs.

C++ is also a lower level language than Java. Although this comes with some challenges when it comes to debugging and writing memory safe code, C and C++ are popular choices for certain applications such as robotics and micro-controller programming.

How to prepare for USACO

The USACO is a very difficult contest. Although it targets high school students, many professional software engineers would find this contest difficult. At the higher levels, students should expect to practice hours every week in order to place. Even at the lower levels, students often need to participate in the contest several times before passing a level.

Thus one key to doing well is starting early. Although the contest targets high school students, many of KTBYTE’s middle school students start reviewing this USACO Guide and practicing for years before starting the competition. This is especially the case if they begin learning programming in early middle school, which allows them to do college level material by high school. To learn more you can view our USACO FAQ to get detailed information about preparing for the contest.

Then, the first step in this USACO Guide that we recommend is preparing for the competition by participating and practicing, even if the student expects to get a low score. New students should aim to become familiar with the common program styles, and submit answers to historical problems on the USACO website. Students can start by copying or modifying existing solutions posted after the contest has finished. This is important, because even a seasoned programmers may be caught by some of the unique requirements (required file names, output formats, etc). Practicing these as warmups ensure students can focus on the problems themselves during the contest.

Secondly, students should become familiar with common algorithms during the contest. These are covered in KTBYTE’s USACO prep classes, CS90, CS91, and CS92. They include searching algorithms such as binary search, ‘dynamic programming’ algorithms, graph traversal algorithms, flood fill, prefix sum, and much more. Students should be prepared to combine multiple of these types of algorithms at the higher levels, and so it is critical they can write them quickly without needing to debug or test the program. Since they may only have 4 hours to do 3 problems, this means they might spend only an hour on a problem. Given that understanding the problem and debugging a solution can easily take half an hour, students may find they have less than half an hour to actually write the solution. Aiming to write a clean canonical algorithm within 10 minutes is therefore a good start.

Thirdly, students benefit from seeing multiple solutions to a problem, and to walk through those solutions with others. If you don’t take a class at KTBYTE, then look for clubs or local organizations where you can meet other competition participants.

Finally, we want to those reading this USACO Guide to know that perseverance is key. There are no consequences to scoring poorly in the competition besides a bruised ego, so consistent participation eventually yields dividends.

Understanding program speed

The USACO problems are designed to take solution programs a long time to run. This means that an inefficient solution will typically run out of time and score a less than perfect score. Since a program may only have enough time to perform 10-100 million operations within the given 2-4 seconds, those operations must be chosen wisely:

1. For loops written within loops, care must be taken that the time it takes to complete a double loop is the product of the sizes of the two ranges. Since 10,000*10,000 is 100 million, students need to be careful not to run double loops over larger datasets.
2. Triple loops similarly run in cubic time
3. Some algorithms or permutations run in exponential time, and thus only work for inputs of size within the single digits.

Students who have studied data-structures will recognize the measurement of program speed as “computational complexity” or “Big-O notation”. These advanced students can benefit from memorizing the complexity of some common algorithms, which will typically be expressed as:

1. O(1) constant time
2. O(log(n)) logarithmic time
3. O(n) linear time
4. O(n*log(n)) linear times logarithmic, which is close to linear time
5. O(n*n) quadratic time
6. O(n*n*n) cubic time
7. O(x^n) exponential time

USACO Guide to contest strategy, tips and tricks

1. Before the contest, prepare some templates to copy/paste for reading inputs and writing outputs
2. Before the contest, prepare some templates of commonly used algorithms as references. Use your own templates, and avoid copying others!
3. Be well rested and have a quiet workspace with good ergonomics and internet connectivity
4. Have your IDE or programming environment set up before clicking the start button.
5. Read ALL problems before starting on any one problem. The easiest problem for some students may not be the first problem.
6. Pay attention to the input size of each problem. For example, if there is an input N which ranges from 1 to 10,000,000 , then there is a good chance your program is constant, linear or logarithmic in nature when looping through values of N.
7. Review our student panel post and videos where past KTBYTE students discuss ways to win at USACO.

Debugging

Inevitably, programs will crash out produce the wrong output during a contest, and so it is vital for students to be familiar with a debugging interface. Since errors tend to be compile errors, crashes, time outs, or incorrect answers, students can use this outline to begin debugging:

Compile

• Try deleting sections of code in a binary search if you can’t find which line doesn’t compile
• Use an IDEtin with automatic library imports, and be familiar with autocomplete keyboard shortcuts

Crashes

• Check the exception type (null pointer? divide by zero? infinite recursion? out of memory?)
• If no exception is available, try uploading code that avoids possible errors, and binary search to find out area of the code is likely crashing

Time outs

• Watch out for array instantiations. Try to instantiate everything at the program start
• Try to count how many operations are run. Use a variable if necessary
• Try to replace data-structures like List or Map with standard pre-allocated arrays
• For higher level problems, check if dynamic programming or memo-ization is possible

Incorrect answers

• Check to see if spacing and format is consistent between your code and the correct solution
• Check for integer overflow
• Check for NaN or undefined integer arithmetic
• If there is time, try to make your own custom input and compare the output with your expected output. You can even compare the specific values used as intermediary computations.

Don’t forget to have fun!

Even though the USACO Guide may be overwhelming, it will help you start to prepare for this challenging contest. But keep in mind that you want to make sure to have fun studying and participating, and enjoy even the smallest accomplishments. This contest usually far exceeds the difficulty of other school work, so be proud of everything you have done!