A month from now, I’ll be teaching the inaugural run of our new USACO Silver course! As our Bronze course students can tell you, there are already lots of excellent problems and algorithmic strategies at the Bronze level. But the Silver level is where I think the beauty of algorithmic problem-solving really begins to shine through.

At the heart of Silver is the powerful idea of recursion. At AoPS, we’re all about introducing concepts via problems, so let’s go visit:

An Elephant In A Room

Let’s suppose that an elephant is in the top left corner of a 3 x 2 grid, and she is facing right. She knows how to do two things:

• Walk forward 1 cell, or
• Make a 90 degree turn to the right and then walk forward 1 cell.

She isn’t allowed to return to a cell she has already visited, and she must keep choosing among these options until she runs out of possible moves – she can’t stop any earlier than that.

Here are the three possible journeys that obey these rules:

We can find all three of those by hand without too much trouble. But we might wonder more generally: for a grid with r rows and c columns, how many possible journeys are there?

Even for a 4 x 4 grid, it turns out that there are 20 solutions:

It would be easy for us humans to miss one (or more) of these if we just used trial and error! And we can’t just tell a program to “use trial and error”, anyway – we have to create a clear algorithm for it to follow.

Backtracking and Self-Similarity

One option is careful backtracking, using an exhaustive strategy like what we might use to try to get through a corn maze in real life. We make choices until we get stuck, then back up to the most recently made choice and try making the other choice instead. After fully exploring that whole branch, we backtrack again to the next latest choice we made, and explore that other branch, and so on, until we’ve found all of the possible paths (or gotten out of our corn maze!)

Backtracking is a useful technique in its own right, and we teach it in Silver as part of depth-first search. But in this problem, any solution that has to discover each of the possible paths one by one is going to be too slow for large grids, just because the number of possible paths blows up exponentially.

Fortunately, this problem has another beautiful idea lurking: self-similarity. Competitive programmers are always looking out for ways to take a problem and reduce it to a smaller instance of the same problem, with the key word being smaller.

In our 4x4 grid example, our elephant will proceed forward in the top row, and will turn right at some point. Let’s say she turns in the third column, as in the six solutions below.

Once she does so, notice that:

1. she can never get back to the top row again
2. she can never get to the column to the right of the one where she made that first turn

Both of these follow from the rules: she can only make right turns, and she cannot cross her own path. Therefore, she must move in an ever-shrinking spiral.

In fact, we can say something even stronger. Once our elephant turns to the right in the third column, she is essentially facing a smaller version of the original problem, but tilted 90 degrees to the right. (Tilting your own head to the right might help you to see it.)

Specifically, by turning at the third column and moving, she is now facing a 3x3 version of the original problem. If she had instead turned at the first, second, or fourth columns, she would instead be facing a 1x3 problem, a 2x3 problem, or a 4x3 problem, respectively.

Moreover, all of these branches produce different solutions, as we can verify from the full set of solutions above. So if we let A(r, c) denote the number of solutions for the problem with r rows and c columns, in this case we can write:

A(4, 4) = A(1, 3) + A(2, 3) + A(3, 3) + A(4, 3)

But how does that help us? Well, then we can make the same kind of argument about, say, A(3, 3) as well – it turns out to break down into A(1, 2) + A(2, 2) + A(3, 2).

And the problems can’t keep getting smaller forever! We can treat A(1, 3) – or anything of the form A(1, c) – as a base case, since once we are trapped in that narrow grid, all we can do is move to the end. So A(1, c) = 1 for any c, and similarly, A(r, 1) = 1 for any r.

Here's the Magic!

Something magical quietly happened along the way here. We are no longer drawing out individual solutions – we have found a way to count them without actually enumerating them one by one. This is what will allow our code to spit out the answer for, say, a 20 x 20 grid (which is 35345263800) immediately, without making our poor elephant bumble her way through all 35345263800 paths.

After guiding our students to this key idea of recursively breaking down the problem, we leave it to them to turn it into code. There are still some significant “implementation details” to work out – in particular, once we have solved a subproblem like A(3, 2), we should never waste time solving it again, even if it appears in other branches, because we already know the answer. Implementation really is half the battle, and it’s one of the big differences between CS contests and math contests.

There is actually an even slicker recursive formula for this problem, but I think it’s a lot harder to find and justify. But feel free to keep thinking about that if you’re interested!

AoPS's USACO Silver Problem Series

There are so many more great topics in Silver, and I encourage you to check out the syllabus. For example, recursion is closely related to the idea of a tree – think about how our elephant faced a series of branching decisions in our problem above. “Do I move forward, or do I make a right turn and then move forward?” And these branching networks, or trees, are themselves special cases of graphs, which capture the idea of connections between things more generally, and which can be used to study everything from social networks to circuit board designs to the eternal problem of finding a short commute.

As a bonus, the USACO Silver content has lots of overlap with university-level second courses in computer science, technical interviews, and real-world software engineering, so being “Silver-level good” at algorithms and data structures is a leg up in so many areas.

This Silver course will complete our USACO course sequence, filling the gap between our USACO Bronze course and our CodeWOOT course covering Gold and Platinum material. Of course, we will continue to refine our courses as USACO evolves.

Now, there’s something I haven’t mentioned yet, and it’s time that I did:

The Elephant In The Room

The last few years – and especially the last year, with its remarkable advances in generative AI – have been an era of upheaval for USACO. Competitive programmers can no longer dismissively say that AI can “only solve standard programming problems that it has memorized from LeetCode”. So coding contest problems keep getting harder and more arcane, perhaps partly as an attempt to thwart AI. More than ever, just knowing the standard techniques is necessary, but no longer sufficient!

The very structure of the contest has had to change – this year we saw USACO move partially toward in-person proctoring (for the final US Open round, which ironically is now invitation-only), and that trend will likely continue.

It’s amazing to be alive in an era of machines that can solve tricky problems that once seemed to require a human’s creative mind. But it can also feel daunting – if AI can solve Silver problems, a student may think, why should I bother trying to get good enough to solve them myself?

Well, for one thing, we’re not yet at the stage where AI can just demolish any problem, and it’s not clear that we will ever reach this stage simply by scaling up large language models. (An ongoing study shows that there are still a significant number of USACO problems that no current model can solve. More anecdotally, I have seen Claude, Gemini, etc., flail on new problem ideas that I’ve proposed.)

And as popular as vibecoding has become, it remains evident at all levels that the greater the user's experience and wisdom with code, the better the results will be. This is as true as ever in the age of AI. LLMs, left to their own devices, frequently take overly complex, inefficient, or ugly approaches to new problems, sometimes in subtle ways that are quite difficult to detect and debug. As more software initiatives use vibe-coded components, the demand for humans with the deepest knowledge of code will likely grow. Those are the engineers who can explain the problems clearly, plan effective strategies, break down tasks into components that the AI can execute cleanly, and verify, debug, and improve the results. 

Part of what I’ve always loved about teaching computer science is that coding empowers people to express themselves in a new way. It’s great that AI is making that means of expression even more widely accessible. I benefit from that myself – I would say I am not the most spatially gifted person, and I used Claude to write small bits of code to render the illustrations above. That frees up more time to come up with original problems and explanations – tasks I will never offload to AI!

But the “themselves” part of “express themselves” is still important – I don’t think it will ever go out of style to deeply understand what you are doing, and why. We don’t all need to be experts in, say, ARM assembly language to write code… of course, but we should know something about what’s going on under the hood and how it influences performance. We don’t all need to be experts in the fine points of the syntax of our favorite programming language, but we should be able to know when an AI has produced code that is misguided, hard to maintain, or just plain unsafe.

Studying the USACO Silver material is a great way to empower oneself by building this kind of domain knowledge and problem-solving confidence. I hope to see your student in our class!

Interested in USACO Bronze and the AoPS approach to these classes? Be sure to read Ian's article, Of Cows and Coding: Preparing for the USA Computing Olympiad, to learn more.