Darren Yao
2020, Jun 26    

Some frequently (and not-so-frequently) asked questions about the USA Computing Olympiad.

Hello, everyone!

My name is Darren Yao, and I’m a current competitor in the USACO Platinum division (top ~200 US). I’m also the author of the book An Introduction to the USA Computing Olympiad, a core contributer to the USACO Guide and CPI projects, among other things.

Recently, I’ve received a number of questions along the lines of “how do I get better at programming contests?,” or “how do I achieve X rank in Y time,” from beginners. Anyway, due to the drastic increase in new competitors I’m seeing lately, I decided to write some articles on programming olympiads, perhaps as a programming counterpart to Evan Chen’s math blog, because I think it’d be helpful. By far the most common question I receive is “can I get from some level to some higher level in some amount of time?” I mostly get this from beginners, and probably as a result of the fact that quarantine killed a lot of extracurriculars, so students are looking for something else to do. To answer the question: advancing fast in programming competitions is certainly possible, but you’ll need to be extremely dedicated and productive. You’ll also need to make sure that you don’t burn yourself out, so consider yourself warned about that.

Welcome to the world of competitive programming! I’m going to start off by reiterating a phrase seen often on AoPS: stop looking for the “right” training. There certainly does not exist a method that will guarantee you X rank in Y amount of time, because as with all contests, there are other factors involved: luck, innate talent, efficiency and productivity of your training time, and so forth. Most importantly, everyone learns differently, and your training should be structured around your own strengths and weaknesses so that it fits you. That being said, I’m going to provide some useful resources below. Readers are encouraged to use their best judgement and skip around the books or go through chapters faster or slower as they see fit; in the end, it is up to you to make your own learning effective.

Now let’s get to the actual FAQ:

How do I prepare for USACO?

Short answer: Learn algorithms, do practice problems, and reflect on why you’re missing problems. Make sure you learn from every problem you do, and you’ll improve over time.

Long answer: read the rest of this article.

What language should I use?

USACO supports five languages: C, C++, Java, Pascal, and Python. Firstly, hardly anyone uses Pascal, and C is a strictly inferior version of C++ for competitive programming because it has less functionality, so you shouldn’t use either of them. Now, for the three languages that actually get used:

  • Python is the easiest to learn, but it also runs slowly, which is often problematic despite the longer runtime. USACO problemsetters have stated that they don’t test Python solutions, and many problems are simply impossible to pass in Python.
  • C++ is the most commonly used language across all levels of competition, and for good reason; it runs the fastest, and code is short. C++ also has macros, defines, and other similar things for shortening code (although often at the expense of readability…) It also has a standard library containing many data structures that you’ll use often.
  • Java is also commonly used. It runs slower than C++, but is given a longer runtime. Java is viable at all levels of competition (A member of the 2020 USA IOI team used Java). Its standard library is very similar to that of C++. Java code, however, tends to be rather verbose.

Personally, I prefer Java for several reasons: it’s very intuitive, debugging is easy, and in my opinion some things in Java are easier to use than their C++ counterparts (I prefer Java TreeSet higher and lower functions over C++ ordered set upper bound and lower bound, for example).

What resources should I use?

If you don’t know how to code, you need to learn that first; this should be pretty easy to do from resources available online. The two primary languages used in competition are C++ and Java; C++ code is shorter, runs faster and is thus favored by the majority of contestants, but Java is granted extra runtime on the USACO to compensate and I personally find it more intuitive and easier to debug. At the high platinum and camp levels, using C++ is an advantage, but Java still remains viable. Python generally is not an acceptable language due to its slow runtime.

A solid background in competition math can make the learning curve easier, because you’ve already developed the intuition needed to solve problems. This generally allows you to get through bronze material very quickly, and also speeds up the learning of more advanced concepts. That being said, the advantage you gain from having previously done competition math is diminishing – USACO wants to make Platinum qualification a major goal in and of itself, rather than a mere side-quest for the math contest elite.

At the bronze and silver level, you should read my book An Introduction to the USA Computing Olympiad, and do the accompanying practice problems at the end of each chapter. Links are below:

Intro to USACO, Java Edition

Intro to USACO, C++ Edition

There’s also USACO Guide, which is a free collection of curated, high-quality resources covering topics from all four divisions.

For additional practice, CodeForces has an extensive set of problems, sorted by rating, topic, or pretty much any other criterion you can think of.

The website CSES has an excellent selection of standard problems. I recommend solving all of Introductory Problems except the last two problems, roughly the first half of Sorting and Searching, and the first six problems from Graph Algorithms.

When should I read the solution?

In general, I think it’s fine to read the solution relatively early on, as long as you’ve made several different attempts at the problem and you can learn effectively from the solution.

On a bronze problem, read the solution after 15-20 minutes of no meaningful progress, after you’ve exhausted every idea you can think of.

On a silver problem, read the solution after 30-40 minutes of no meaningful progress.

When you get stuck and consult the solution, you don’t necessarily need to read the entire solution at once, and you certainly shouldn’t look at the solution code. Instead, it’s better to read the solution step by step until you get unstuck, at which point you should go back and finish the problem, and implement it yourself. Reading the full solution or its code should be seen as a last resort.

Problems that you practice with should be of the appropriate difficulty. You don’t necessarily need to complete all the exercises at the end of each chapter, just do what you think is right for you. A problem at the right level of difficulty should be one of two types: either you struggle with the problem for a while before coming up with a working solution, or you miss it slightly and need to consult the solution for some small part. If you instantly come up with the solution, a problem is likely too easy, and if you’re missing multiple steps, it might be too hard.

Should I implement every problem that I solve?

Usually, yes. Solving competitive programming problems consists of two parts: coming up with the algorithm, and implementing the algorithm. You should implement so that you practice both parts.

Is it possible to go from X division to Y division in Z amount of time?

I don’t know, only you can answer this question. It depends on the amount of hours you put in, how effective your practice time is, and other factors that I probably don’t know about you.

What topics do I need to know for each of the USACO divisions?

Copied and pasted from a previous post.

  • Bronze: Simulation, brute force/complete search, implementation, intersections of 2 and 3 squares, ad-hoc problems. The general focus of the Bronze division is not on any specific techniques, but rather basic algorithmic thinking, mastery of your chosen programming language, and intuition and ability to think through problems.
  • Silver: Sorting, prefix sums, binary search, graph theory, standard library data structures, implementation, ad-hoc problems. The main theme of the Silver division is applications of relatively simple algorithms. However, just because the algorithms themselves are relatively simple does not make the problems easy; in fact, silver problems require a lot of ingenuity, which makes passing silver a major bottleneck for many. Again, this is where practice comes in – once you’ve done enough problems, you get much better at recognizing how you should attack any given problem.
  • Gold: More graph theory (shortest-path algorithms, minimum spanning tree), tree algorithms, dynamic programming, data structures (Fenwick tree, possibly segment tree), topological sort, combinatorics (PIE) and number theory. Gold features a much wider breadth of material than silver. The main thing you’ll need to pass gold is knowledge of all the algorithms, and extensive practice.
  • Platinum: The topics that show up on platinum contests aren’t particularly well defined, and there is essentially no upper limit on problem difficulty. Anything is fair game (including topics explicitly banned from IOI, like heavy-light decomposition)

What CodeForces rating corresponds to each of the USACO divisions?

This is my subjective opinion, and others may feel differently. The reason why problem ratings differ from user ratings, is because CF emphasizes solving problems quickly (6-8 problems under 2 hours time constraint), while USACO has harder problems and more time (3 problems in 4-5 hours).

  • USACO Bronze users are probably <1400 rated on CF, and Bronze problems correspond to 900-1500 rated CF problems.
  • USACO Silver users are probably 1300-1600 rated on CF, and Silver problems correspond to 1200-1900 rated CF problems.
  • USACO Gold users are probably 1600-1900 rated on CF, and Gold problems correspond to 1500-2200 rated CF problems.
  • USACO Platinum users are probably 1750+ rated on CF, and Platinum problems correspond to 1900+ rated CF problems.

Some Final Notes

This and this are two blog posts by Evan Chen that I find quite insightful. The blog is primarily a math blog, but the posts discuss such things as time management, the problem-solving process, and other tips that you may find useful.

I think this is all that I wanted to say, so I’ll leave off here. Best of luck!