A Circular Bucket Brigade
Farmer John’s two hundred thousand cows are arranged in a circle, and each is holding a bucket of milk. Some cows may have just one liter in their bucket, whereas others may (somehow) be holding as many as 109 – that’s a billion – liters. This is weird. Despite the farm setting, we’re clearly not in Kansas anymore.
The herd has just begun an eerily precise ritual in which, every minute, each cow tries to pour a liter of milk from her bucket into a designated neighboring cow’s bucket – either the right neighbor or the left neighbor. (The choice never changes for any given cow.) Any overflowing milk is lost forever, but Farmer John doesn’t seem to be crying over it.
He doesn’t question the purpose of the bizarre process unfolding before him; he only wonders how much milk will be left a billion minutes later. But – although his farm is the setting for dozens of curiously specific mathematical situations each year – he can never solve his own problems alone. He needs your help: specifically, your programming skills!
This problem comes from the February 2024 Bronze-level contest of the USACO (USA Computing Olympiad), and yes, the setup is deliciously absurd. Why is this happening? No reason is given; it’s far from the weirdest thing that happens on John’s farm. Why the farm and the cows? There’s an official reason (the USACO was founded in Wisconsin) and also an obvious unofficial one (there are endless per-moo-tations of cow puns out there). And why the huge numbers? That one has a more complex answer…
(We will have a lot more to say about this problem later in the article, but if you’d like to see the full original text, it’s here!)
How AoPS Can Help
If this sort of algorithmic problem-solving sounds intriguing, we welcome you to consider one of our USACO-focused courses. We are now offering a USACO Bronze course which will help get you through the Bronze level and into Silver. For more advanced solvers who are already at the high Silver or Gold levels, there’s also our CodeWOOT course. (We’re also working on a USACO Silver course to bridge the gap; it will be available sometime next year.)
The USACO is about practice, practice, practice, but it is not about cramming: students need to be comfortable enough with ideas and algorithms to be able to reproduce them from memory, as the USACO requires. Trying to memorize and regurgitate particular bits of code is just not sustainable – there’s no substitute, in the long term, for genuine understanding.
We build toward that understanding by working through problems together in class. Instead of dumping new ideas on you out of nowhere, we carefully choose problems that motivate and demonstrate key algorithms, data structures, and strategies – and we arrive at those ideas together, interactively. (We do not use past USACO problems, since those are already available for free on USACO’s site; we encourage you to practice with them as a supplement!)
These problems take time to code up, and we prefer to reserve class time to talk about what we do best – problem solving! Coding takes place outside of class, and students can use our interactive judge system (which closely mimics USACO’s) to submit solutions anytime – day or night – and get results immediately. (But don’t stay up solving cow problems pasture bedtime!)
Talking through a problem in class brings some insight, but actually writing up a successful solution cements that understanding. It may take multiple attempts, and perhaps some help from our course assistants (and one’s peers) on the course forums… but there’s nothing like the satisfaction of seeing all those green stars light up (meaning that the code was correct and fast enough to pass all test cases).
Each homework problem set includes the in-class problems plus several more related problems of varying difficulty, including some that would challenge almost anyone. Think of it like a buffet. There’s more food available than almost anyone could possibly eat… but you can eat – er, problem-solve – until you are satisfied!
Although we want you to succeed in the USACO in particular, there is more to life than this one contest! We want you to come away with a strong problem-solving foundation that can serve you well in future personal and professional coding projects, and even in technical interviews. It’s unlikely that you will need to monitor a circular milk bucket brigade in real life, but the ideas in USACO (and other competitive programming problems) come up all over the place in math, computer science, and code used in industry. The cows are just friends along the way.
And back to our cows:
As you recall, Farmer John’s cows are arranged in a circle, and each is holding a full bucket of milk, though the buckets may be of wildly different sizes. Every minute, each cow simultaneously tries to pour a liter of milk from her bucket into a designated neighboring cow’s bucket – either the right neighbor’s or the left neighbor’s and the choice never changes for any given cow.
If two cows pour a liter into each others’ buckets, then somehow none of that milk is lost, even if one or both buckets were full initially. And if a cow would ever end up with too much milk in her bucket, that excess milk is lost. For example, if two cows A and C each pour a liter into some cow B’s full bucket just as B pours a liter into cow A’s bucket, for example, then one of those two liters going into B’s bucket disappears.
To make this curious situation clearer, let’s consider a small example with only four cows who start with full buckets of various sizes. The following diagrams show what happens in the first, second, and third minutes, and how many liters of milk the cows have at the start of each minute.
Notice that we go from having eight liters of milk in total, to seven, and then to six! (You may wish to think about: what would happen in the next minute? And in the minute after that? We’ll come back to those questions later…)
Farmer John wonders how to handle a more general problem and needs your help!
Given a number of cows, the initial amounts of milk in each cow’s bucket, the choice of neighbor for each cow, and a number of minutes, how much total milk will be left after that many minutes?
If the number of cows, the cows’ amounts of milk, and the number of minutes were pretty small – say, in the thousands – we could write brute force code that takes only a couple of seconds to run. That is, our code could simulate the process in each minute’s round, keep running for the appropriate number of rounds, and finally report the total amount of milk lost.
But in this problem, there can be two hundred thousand cows, each cow can have up to a billion liters of milk, and the process can go on for a billion seconds. It would take a very long time indeed for brute force code to find an answer; we need to think of something more clever…
Let’s get some more insight into this problem. (If you want to avoid spoilers and solve the problem yourself, you should do that before proceeding!)
Even though this is a typical problem in the introductory Bronze level of the contest, brute force simulation would only get us so far. We’d submit to the automated judge and see that only the first block of test cases passed, with the rest having timed out:
This would be good enough for partial credit, which on its own would not be enough for advancement to Silver. The USACO authors want contestants to discover underlying rules and patterns that enable much more elegant (and much faster!) solutions.
Playing around with small examples is a great way to get a feel for a problem and to notice those hidden features. Let’s return to our example from before:
The cow on the left quickly loses its liter of milk, but that liter doesn’t actually disappear from the system until the bottom cow tries to pour it into the right cow’s bucket, which is already being refilled by the top cow. We can convince ourselves that this is the only way that milk can disappear.
If we run this example for one more minute, we end up in this state…
…and then we remain this way for all future minutes. No more milk is ever lost.
It looks like, generally speaking, we have “chains” (like the left and bottom cows here) pointing into “pairs” (like the top + right cows here). Pairs never lose any milk, but the milk in each chain goes away at a rate of one liter per second. So we really just need to know how much total milk is in each chain to start with. If we think about it, we see that there’s no difference between a chain of two cows with one liter each, and a chain of a single cow with two liters – both chains still lose one liter per minute.
Before we declare victory, though, it’s worth playing with some more examples, because they can reveal phenomena we haven’t noticed. For instance, there could be two chains pointing into the same pair, and it’s even possible for there to be no pairs at all! (What happens in that latter situation?)
Even once we understand this, coding up the idea can be a lot harder than it might initially seem. For starters, we need to be able to detect and handle the case where there is just one big cycle. Otherwise, we need to find the chains and compute how much total milk is in each one. We also have to figure out how much milk is lost from each chain after our given number of minutes. There’s lots of potential for off-by-one errors, edge issues like incorrectly handling a pair between cows 1 and N, and other miscellaneous bugs. (We encourage you to try writing a solution and submitting it for automatic judging on the USACO site!)
But once we code up our improved idea, we return an answer almost instantly; our solution is no longer a simulation, and no longer takes time proportional to the number of minutes. It passes all of the cases, and we take a moment to congratulate ourselves… before moo-ving on to the next problem.
The problem solving journey is easier in the company of instructors and peers, and we invite you ruminate on these legen-dairy problems with us! For more information, be sure to visit our USACO Bronze Problem Series course page!
