What is USACO Gold?
The USA Computing Olympiad is a prestigious competition divided into four divisions: Bronze, Silver, Gold, and Platinum. Making it past the Gold division is the final step in the journey of reaching the Platinum division. So what makes Gold different from the previous divisions? While Silver consists of a large jump in terms of required problem solving skills and algorithmic knowledge required, the main difference with Gold-level problems is that it requires competitors to have a deep familiarity with the wide range of new concepts introduced. Problem-solving skills are nonetheless important in Gold, however the jump isn’t as big compared to Silver. If you are currently still in Silver, check out our comprehensive guide for promoting to Gold here.
Like Silver, passing Gold requires participants to dedicate a substantial amount of time to learn new algorithms and improve their problem-solving skills. In this comprehensive blog post, we aim to provide an in-depth understanding of the USACO Gold division, covering everything necessary to advance to USACO Platinum in your next competition!
Note that the rest of the blog assumes that you have already passed Silver (or are already very familiar with the division), and thus will not cover prerequisite information from Silver. Refer to the Silver blog for more information.
Concepts You Need to Learn For USACO Gold
To begin preparing for Gold, we recommend starting by learning each concept individually before practicing on past contest problems. Jumping straight into practicing on past problems before learning the concepts can often be counter productive, because it’s very difficult to figure out these concepts on your own (especially while trying to solve a problem) and will spoil the problem for future practice. Instead, the recommended approach is to learn each topic individually, followed by practicing with a curated list of problems (e.g., the USACO Guide or Codeforces) that require that concept.
Beyond the wide range of topics already covered in USACO Silver, USACO Gold introduces an even wider variety of new concepts.
Dynamic Programming
Dynamic Programming (DP) is by far the most important concept introduced in the Gold division. Every contest will always have at least one DP problem, so mastering DP is a must-do if you want to reach Platinum.
Dynamic programming is an incredibly versatile technique. At its core, it consists of breaking a large problem into smaller subproblems, solving each of these subproblems just once, and storing their solutions – typically using an array. The key difference from recursion is that DP uses these stored solutions to formulate solutions to bigger problems, thus avoiding the computation of the same subproblem multiple times.
Beyond the general idea of dynamic programming, there’s a few important subcategories of dynamic programming that often show up.
Knapsack
The knapsack problem is a classic algorithmic challenge that involves selecting items with given weights and values to maximize total value without exceeding the weight capacity of the knapsack. Dynamic programming solves it by building up a table that represents the maximum value achievable for each subcapacity, from 0 up to the total capacity, considering each item at a time. Generally, you should use this technique whenever you’re trying to maximize some value by choosing items under the constraint of some other value.
Graph/Tree
DP on graphs is a very broad technique – as in the name, the technique is classified as whenever you apply dynamic programming to graphs. Typically, the DP “state” will always include a node, and any other relevant information necessary for the problem.
This idea can also be extended to DP on grids if we represent each cell as a node and form edges between all adjacent nodes. Often, DP on grids is used to count the total number of paths from point A to B, with various constraints involved.
DP on Ranges
The range DP technique aims to find a consecutive range of values, typically in an array, that maximize/minimize some condition. It works by combining the answers from consecutive smaller ranges to build to the answer for larger ranges, thus saving repetitive computational time.
Digit DP
Digit DP questions are always in the form, “how many integers between A and B satisfy some property?” A and B are typically very large (around a magnitude of 10^18), so iterating through all the integers between A and B will never suffice. Digit DP incrementally builds up the solution by considering each digit position and its possible values, increasing its efficiency using memoization to avoid recalculating overlapping subproblems.
Bitmask DP
Bitmasking is the technique of taking advantage of the binary representation of numbers to represent subsets of a set. Specifically, the value of each bit in the number specifies whether a corresponding element is included in the set (1 if the element is included, and 0 if not). Applying bitmasks to DP can typically be used to efficiently count the number of permutations of a set that satisfy some property, reducing the time complexity from O(n!) down to O(2^n).
More on Graphs
Gold also introduces several new graph algorithms and techniques. Make sure that you also have a strong familiarity with silver-level graph concepts, as Gold problems often tend to involve the same concepts.
Shortest Path Algorithms
As in the name, the shortest path problem involves finding the shortest path between two nodes in a graph. It works differently for unweighted and weighted graphs.
In an unweighted graph, the shortest path between two nodes A and B can be determined via a breadth-first traversal of the graph starting from one of the nodes, terminating when the other node is visited for the first time.
Finding the shortest path in weighted graphs can be solved via Djikstra’s algorithm, which functions similarly to breadth-first search but instead uses a priority queue to handle the queue of nodes, rather than a simple queue. Other useful shortest path algorithms include Bellman-Ford and Floyd-Warshall. Note that these shortest path algorithms often work only if the graph does not include negative edge weights.
Union Find
The union find algorithm provides an efficient way of determining whether two nodes are in the same connected component, while supporting efficient edge insertions as well. It’s very useful whenever you need to dynamically keep track of connected components within a graph.
Topological Sort
Topological sort is an important concept for directed graphs. It can not only detect cycles within them, but it also provides a way to order the vertices in a way such that each vertex appears before any of its descendants (assuming the graph is acyclic). It’s useful whenever you need to determine ordering within some hierarchical structure (e.g. finding a milking order where some cows need to be milked before others).
Minimum Spanning Tree
The minimum spanning tree is an important concept for weighted, undirected graphs. It involves choosing edges in a connected graph such that:
The edges chosen connect all the vertices together (i.e., if we took out all of the edges that weren’t chosen, the graph would still be connected)
The sum of chosen edge weights is minimal across all spanning trees
There are two greedy algorithms for determining the MST of a weighted graph: Kruksal’s and Prim’s algorithm. Since both algorithms are rather efficient, they are generally interchangeable with one another (however they do have some tradeoffs with time and space complexity).
Point Update Range Sum
Point update range sum data structures are designed to efficiently process two types of operations on an array: updating the value at a specific index (point update) and calculating the sum of a range of elements (range sum). They’re kind of like a more powerful version of prefix sums.
Data structures such as Binary Indexed Trees (BITs) or Segment Trees are commonly used to perform these operations in logarithmic time, making them suitable for scenarios with a combination of frequent updates and range queries.
Math
While no problem will have a solution that purely involves math, problems often require a general understanding of important math principles.
The most important concept for Gold is combinatorics, which often works hand in hand with dynamic programming. Be sure to familiarize yourself with basic counting (permutations and combinations), binomial coefficients, recurrence relations, and the principle of inclusion-exclusion.
Some other relevant concepts include modular arithmetic, operations with binary numbers, and number systems. Knowing these concepts will provide a sufficient math understanding to solve any Gold problem.
Resources and How to Prepare For USACO Gold
A comprehensive list of resources available can be found on the USACO Resources Page. Below, we’ve listed resources that competitors have historically found to be most useful for each stage in preparing for Gold: learning each concept, practicing each concept, and preparing for contests.
Learning Gold Concepts
If you have already passed the Silver division, you likely already have a reliable method of learning new concepts in your division. This will likely also be the best way to learn new topics in the Gold division. If you’re looking for further resources to learn concepts on your own, the rest of this section provides useful links to look into.
There are a ton of free resources available online to learn and master each concept required in USACO Gold. In particular, the USACO Guide does a great job at providing links to videos, articles, and textbooks that explain each concept in detail.
If you want to follow a textbook specifically geared for competitive programming, a great resource is the Competitive Programmer’s Handbook by Antti Laaksonen (note: not all of the concepts covered apply to the Gold division).
Another way to learn Gold concepts is to take an online algorithms course provided by a college. Coursera hosts many good courses, most notably Algorithms Specialization by Stanford University and Algorithms Part I and II by Princeton University. While they cost money, Coursera allows you to audit them for free, or to apply for a fee waiver (it’s pretty easy to get approved as a high school student). In addition to covering relevant topics for USACO, they provide interesting projects and exercises to apply what you’ve learned, which can help place these concepts in a broader context and give you a taste for what college-level computer science classes are like. If your only goal is to prepare for USACO, however, these courses won’t be as efficient of a way to learn the concepts you need.
If you prefer learning in a more structured manner, or don’t learn on your own effectively, you may want to consider signing up for a USACO class. Classes follow a set curriculum and pace, and provide more personalized help through teachers. However, classes do cost money, and quality may vary between different organizations – do your research before signing up for one!
Practicing Gold Concepts
After learning each concept and how to implement them, the next step is to practice using that concept in past problems. Like with learning concepts, you can probably just stick with the same routine as you did in Silver.
Often, it’s wise to organize your practice by topic – for example focusing on practicing DFS one week and then practicing two pointers another week.
The USACO Guide, once again, is an amazing resource to practice concepts once you’ve learned them. It provides a curated list of problems for each concept, enabling targeted practice once you have learned each one.
Another useful resource for targeted practice is Codeforces, which is the biggest online site that hosts competitive programming contests. It’s also a great resource if you want to practice, but want to save past USACO problems for when you feel more comfortable. To organize your practice by concept, navigate to the problem set tab and filter the problems by a specific tag (i.e. the concept you want to practice) and difficulty range (1500 - 2200 is generally a good range for Gold). For a comprehensive guide on how to effectively use Codeforces to prepare for USACO, check out our blog here.
How to Prepare For USACO Gold
Once you feel comfortable with all the concepts tested in the Gold division, as well as how to implement them in real problems, it’s time to prepare for upcoming contests. In order to do so, do not continue practicing with concept lists! While they are great for learning concepts initially, relying on topic lists to prepare for contests can be counterproductive, as it’s much easier to solve a problem if you already know what algorithm/data structure you are supposed to use beforehand.
The best way to prepare for upcoming contests is simply to practice on past problems! A great way to do this is to go through problems in the past contests page on USACO, start from the 2016-2017 contest season and work your way through to the more recent contests. Newer contests are typically harder than older ones, so by practicing in chronological order, you’ll gradually face harder problems as you improve through more practice.
If you have run out of USACO problems to practice, or want to save the remaining ones for later, Codeforces is a great resource to find a ton more problems and contests.
What to do If You’re Stuck in USACO Gold
Maybe you’ve learned all the Gold concepts and have practiced them on a bunch of problems already, or you’ve been able to solve 50% of all past Gold problems already. In these cases, would it be reasonable to expect to be promoted in the next contest? In many cases (unless you’re naturally super talented), no! Our blog post about Closing the Gap Between Expectations and Reality goes into this topic in depth. Essentially, even if you’ve solved 50% of all past Gold problems already, the problems you’ve solved are likely to be roughly the easiest 50%. However, modern contest problems are all typically on the harder end of the difficulty spectrum, meaning even though you could solve half of the Gold problems, you won’t be able to solve any problems in a contest because the level of difficulty you can handle does not encompass the contest difficulty.
If you truly want to anticipate success for an upcoming contest, you should reach a point where you can solve more than 90% of all Gold problems. At this point, it is a lot more likely that all three contest problems will fall within the range of what you can handle — and thus you should expect success in these cases.
What if you’ve reached a point where you can solve all past Gold problems, but you still find yourself struggling in contests? This brings us to the next topic: contest strategy.
Contest Strategy For USACO Gold
Having a strong contest strategy can make or break your contest performance. In fact, during USACO camp each year, the coaches host a special lecture focused solely on developing a strong contest strategy. And every time, the campers see their scores shoot up after implementing the contest strategy.
So, what makes a good contest strategy? The key distinction between practicing on your own time and competing in contests is the time limit. While 4 or 5 hours may seem like a lot of time – it really isn’t. Thus, being able to allocate your time well is absolutely crucial for succeeding in contests.
Riya filmed a great video detailing contest strategy in depth. The key takeaway from the video is to take practice contests with the same time constraints as a real contest. During these contests (and actual contests too), keep a contest log where you note down what you are currently working on every 15 minutes. Maintaining this log can help you identify time leaks during contests: if you notice that you’ve been working on the same problem for 1 and a half hours without significant progress, you should choose to cut your losses and move on to a different problem, coming back to the current problem later.
After the contest is over, analyze your performance. Did you allocate too much time on a single problem? Were you too caught up in debugging because you didn’t plan out implementation well enough? Could you have solved a problem with better time management? Asking questions like these can help you identify mistakes you’ve made and learn from them, making sure that you do not repeat these mistakes in the future.
How Much You Should Practice To Pass USACO Gold
A lot of competitors often ask the question, “how many hours a week should I put into USACO to pass X division in Y time?” The answer to this question is different for everyone. It could take some competitors 2 months to pass Gold practicing 2 hours a week, and other competitors 10 months practicing 5 hours a week.
Instead of comparing yourself to how much others practice, or frantically searching online to find a routine that worked for someone else, you need to figure out what works for you. In order to do so, create some goal in which you hope to promote by, and allocate time throughout your schedule so that you can consistently make progress every week. If you find that you’re not progressing as fast as you need to, either put more hours into practicing every week or reconsider if your goal is realistic. Another option is to find a USACO coach, which can often make your practice and improvement a lot faster, giving you time to focus on strengthening the rest of your college application.
At VPlanet, have private coaching programs starting from USACO Bronze all the way up to USACO Platinum.
Coaching from VPlanet Coding
If you’re super busy, then you need our program, so that you can advance faster and spend your time more efficiently. If you can get half your time back, then all those remaining hours can be spent on something else to make your college apps that much more competitive.
Here are 5 key benefits that we provide over other alternatives:
Comprehensive curriculum for each division
VPlanet provides dozens of hours of video content with in-depth algorithms and problem walkthroughs, covering all the knowledge a student needs to know to become successful. Additionally, our curriculum teaches the essential problem-solving skills that are required beyond the knowledge of algorithms.
Carefully curated problems
Practicing on your own can be frustrating and inefficient. We know what it’s like to spend 2 hours thinking through a problem just to give up and read a solution you can barely understand. VPlanet has handpicked 100+ problems for each division, ensuring that the problems students work on are never too easy or too hard. We guarantee that each problem has just the right level of difficulty to optimize students’ improvement trajectory.
Daily support from coaches
If students are ever stuck or confused, VPlanet provides daily support in the form of Facebook group discussions, Q&A, and one-on-one sessions with highly-experienced coaches. These sessions maintain a very small ratio between students and coaches to ensure that everyone receives as much personalized help as possible.
In contrast, a typical USACO class can have as many as 30 students assigned to one teacher, with only 1-2 class sessions per week to ask for help. This class environment makes it difficult to ask for help and risks leaving many students behind.
Work at your own pace
An inevitable issue with USACO classes is that they fail to account for each student’s individual skill level. This issue guarantees that either a significant number of students are falling behind in class, or the class is too slow for many high-achieving students. VPlanet overcomes this issue, enabling students to go at the pace they want with regular support from coaches.
Advance faster
We find that VPlanet students tend to advance at a much faster pace than others. Our carefully crafted curriculum and sessions with coaches provides just the right amount of content and personalized support for students to improve as fast as possible. This leaves our students with more time to focus on other activities to strengthen their college applications.
Conclusion
Mastering the USACO Gold division requires a multifaceted approach, delving into an array of advanced concepts and problem-solving strategies. This comprehensive guide serves as a roadmap for aspiring participants, emphasizing the importance of deeply understanding concepts, targeted practice, and realistic expectations. Transitioning from theoretical comprehension to practical implementation is pivotal, coupled with an emphasis on effective contest strategies to manage time and learning from mistakes. By embracing these principles, individuals can navigate the challenges of Gold, enhancing their competitive programming skills and setting a solid foundation for future success in higher USACO divisions.