Morocco

After our dismal performance the previous year, we decided to prepare properly this time.

The division of labor among the three of us was now quite clear. I handled implementation-heavy problems and the more exotic algorithms, so over the year I learned a great many techniques I had never even heard of before—half-plane intersection and the Aho–Corasick automaton, for example. Their names sounded suitably elaborate, but they were also genuinely useful. My own training method was to work through problems from previous regional contests, which covered most of the standard algorithms reasonably well.

The other teammate who wrote code handled mathematics, dynamic programming, greedy algorithms, and anything else with even a hint of math. He trained by competing on Codeforces and Topcoder. Their problems differed substantially from the ICPC style: almost every problem involved mathematics to some degree, and the shorter contest format limited how much code a solution could require. That made them well suited to learning this side of competitive programming.

Our third teammate, who did not code at all, was responsible for knowing all the strange things. Our expectation was simple: he did not need to implement them, but he needed broad exposure to everything. His training method was to open an online judge and read the problems in order. If he could not solve one, he read the editorial. Whenever he encountered an unusual technique, he remembered it and told us if it seemed like something the rest of the team ought to know.

Beyond individual practice, we trained together vastly more than the year before. To prepare for the contest, all three of us took the minimum course load in our final semester—and easy courses at that—so we could devote more time to training. My mathematics teammate and I were first-year graduate students; our problem-reading teammate was a senior. We began at roughly one team contest per week, increased to two near the end of the semester, and practiced every day once vacation began. A contest alone lasted five hours. Add the time needed afterward to finish every problem we believed we should have solved, and the entire day was gone, sometimes with work still left.

As the training accumulated, so did our confidence. We ran five-hour virtual contests on Codeforces and noticed that many teams heading to that year’s World Finals were practicing the same sets, though virtual participation meant we did not start at the same time. We encountered teams from Tsinghua, Peking University, Shanghai Jiao Tong, and several European universities. The more contests everyone played, the more often even excellent teams had an off day. In other words, we eventually managed to beat nearly every strong team we could find at least once. Our conclusion was irresistible: if our luck and form were good enough, was there any team we simply could not beat? After some thought, only tourist’s team came to mind. Our goal for the year was a medal.

The contest eventually demonstrated that “if our luck and form were good enough” was a rather demanding condition. On the day, our performance was merely normal, perhaps slightly below normal.

There was a more serious problem. Most of the virtual contests we practiced on Codeforces came from Russian training camps. Russia had exceptionally strong teams—ITMO University in St. Petersburg, tourist’s school, had already dominated the championship for years—but those camp problems differed markedly from the World Finals. Their style was closer to Codeforces itself: heavy on mathematics and light on implementation. Put simply, those contests may have trained my teammate very well while doing almost nothing for my own ability to implement pure coding problems. Unfortunately, I did not recognize this until our post-contest review.

That year the three contestants, our coach, and the assistant coach who had been unable to travel to Russia the year before all flew to Morocco together. I remember almost nothing about the organized sightseeing in the days before the contest. My mind was probably occupied entirely by the competition.

What I do remember is the heat. Going outside felt unbearable; all I wanted was to stay in an air-conditioned room. A friendly man on the street noticed how hot I was and began talking to me about the weather. I understood none of what followed until he pointed into the distance and declared, “the great Sahara!” That part I understood. I assume he was proudly reminding me that the Sahara was nearby.

One incident remains especially vivid. Our assistant coach, who was of Russian background, could be remarkably fearless. In a market in central Marrakesh, we came across a tattoo artist working from a street stall. Do not ask why a tattoo artist had a street stall. It looked unreliable at first glance and not much more convincing at second. Our assistant coach suddenly decided that perhaps he should have a tiger tattooed on his arm. The artist asked him to draw the design, so he sketched what looked like a cartoon cat on his arm.

All three of us had exactly the same thought: if you go through with this, do you still want that arm? In the end, for reasons I do not remember, he did not get the tattoo. Perhaps he eventually decided that the operation looked as dubious as we thought it did.

The market also had vendors selling freshly squeezed orange juice. The press looked extraordinarily wasteful. An orange was cut in half, one hemisphere was placed peel-side down in the machine, and a lever crushed it. The juice came out; the half orange was finished. Even by sight, the yield looked terrible. Still, the juice was excellent. Perhaps the waste was the reason: none of the peel, or even the membrane around the flesh, made it into the drink. There was no bitterness at all, only sweetness.

I had never seen a machine like it. Several years later, on a trip back to China, I encountered the same technique at an airport in a fully automated vending machine. You paid, and it cut three oranges in half and pressed them on the spot. The machine was evidently not very precise. It jammed midway through, stole one of my oranges, and left me with a cup only two-thirds full. There was, naturally, nobody to whom I could appeal. A few years after that, I never saw those machines again. Perhaps the ingredients were too expensive, the machines too unreliable, and the complaints too numerous for the business to survive.

Back to the contest. The three of us discussed running one final practice round on site, then abandoned the idea. It sounded unnecessarily painful, and we could not see what last-minute cramming would accomplish.

On contest day, we entered the hall and found balloons in thirteen colors. That meant thirteen problems, an unprecedented number. By all logic, one of them ought to be exceptionally easy—a free point. That was exactly what happened.

Someone solved A five minutes after the start. It was indeed the giveaway. We followed and accepted it at minute 11.

Then we looked for the next problem. B was geometry and appeared hopeless, so we discarded it immediately. F and M were implementation problems that did not seem conceptually difficult but would take time. D looked at first glance like a mathematical problem involving calculus. Our problem reader identified C as a straightforward network-flow problem. I checked it, agreed, and began coding.

At minutes 28, 29, and 30, teams solved F, C, and D in succession. That reinforced our belief that C was simple network flow. I finished the implementation at minute 35, submitted it, and received a wrong answer. Awkward. I read the code twice, found nothing, and we were stuck.

We asked our problem-reading teammate to debug C while I began implementing F and our mathematics teammate derived the formula for D. At around the one-hour mark, the debugger found a missing case in C. We added it, revised the code, and accepted the problem at minute 63.

I probably spent more than half an hour coding F, then another twenty minutes debugging it against the sample. My implementation skills were simply not good enough. I submitted at minute 93 and got a wrong answer. We printed the code and continued debugging offline.

Our mathematics teammate began coding D. He had written very little geometry before, so I warned him to use a sufficiently long constant for pi—I had been burned by that before—and to use long double, not double, anywhere performance did not matter. During that time I found the problem in F, took the computer briefly to fix it, and accepted F at minute 102.

D was accepted on the first attempt at minute 112.

We now had four problems. When we looked up at the scoreboard, the contest had transformed. L, J, and I had received first solves at minutes 39, 47, and 53; E and H followed at 115 and 118. Nine problems had now been solved by someone, while the leader—I remember it as the University of Tokyo—already had seven. Seven problems in two hours was unprecedented. According to an analysis we had previously heard from a Carnegie Mellon coach, when nine problems were solved within two hours, a medal would require ten and gold would require twelve.

Our mathematics teammate started on L while I coded I. I was a simple interval-merging problem: given several groups of segments, compute the total length covered by every group. Our first idea was a segment tree, specifically a coordinate-compressed one because the endpoints were real numbers. That seemed implausibly elaborate given how many teams had already solved the problem. Were they all implementing compressed segment trees? Then again, this was the World Finals; perhaps they were. We eventually learned that we had badly overthought it. If we represented every uncovered portion as a segment, the task became finding the length covered by at least one such segment. Subtract that from the full range, and one sort was enough.

Instead, we wrestled with the compressed segment tree. It was not an especially complicated data structure, but we had never implemented one in this form. Our first wrong submission came at minute 126. There were countless boundary cases and comparisons between real values waiting to go wrong, so a very long debugging session began. I consumed more time on I than on any other problem. We submitted roughly once every half hour, accumulated four wrong attempts, and finally accepted it at minute 269. From beginning to acceptance, I had probably spent more than three hours on what was supposed to be a simple problem.

While I debugged I on paper, our mathematics teammate implemented L. It was not particularly complicated, and he accepted it on the first try at minute 173.

Then there was J, the strangest problem of the contest. It looked mathematical. After reading it, our mathematics teammate asked whether either of us knew an algorithm for multiplying two very large integers quickly. We did not. The answer was the fast Fourier transform, FFT. None of our practice contests had included an FFT problem, so none of us knew it. Our teammate had identified exactly what was needed, lacking only an FFT implementation. What could we do? Submit a lookup table.

The input contained only one integer, which made the problem ideal for hardcoding precomputed checkpoints into the source. We estimated the size and realized that the table might actually fit. The required file size depended on the sampling interval. If we stored one value for every hundred numbers, we would submit a program of roughly 100 KB, but a query falling between stored values would require computing as many as one hundred additional cases at runtime. Storing every fiftieth value would produce a 200 KB program but halve that work. We did not know the maximum permitted source-file size, so we decided to stop worrying and try it.

That began our long battle with the table. It should not have been so difficult, except that the contest laptop was painfully slow. My teammate tried to save a 100 KB source file and the computer froze, nearly crashing. The cursor spun for a full thirty seconds before the save completed. Every save was terrifying because we expected the machine to die. We had to operate carefully; copying and pasting too much data at once might freeze it again. Saving frequently is normally a good programming habit. Here it became a liability. Whenever my teammate instinctively pressed the shortcut before he was finished, he would immediately swear and ask why his hand had betrayed him again.

The next two hours consisted mostly of me debugging the compressed segment tree while he debugged the enormous table. We took turns at the computer, took turns submitting, and took turns being wrong.

Before the scoreboard freeze, the minimum number of problems in medal position had already risen to eight. We were stuck on two and had no idea how to free ourselves. Since our goal was a medal, we had to open another problem. While the mathematics teammate and I were occupied, our problem reader started E and judged it solvable with a simple greedy algorithm. I quickly implemented that greedy idea and got two wrong answers. He could not tell whether the algorithm or the code was at fault. We were now stuck on three problems. Then the mathematics teammate glanced at it, said the greedy approach was obviously wrong, and produced a counterexample in thirty seconds. E became completely inaccessible, returning us to being stuck on only two.

Our final submission of the hardcoded J solution came four minutes before the contest ended. It was accepted, with considerable difficulty, and that concluded our contest.

The one distinction worth mentioning is that we solved J with a lookup table, and we were the only team in the contest to do so. The official post-contest analysis specifically noted that hardcoding was possible, and that one team in the field had actually used that approach. That team was us.

At the time, I wondered whether the problem setters had never considered hardcoding at all—whether our submission made them realize it was possible, prompting them to add that paragraph to the analysis. Ten years later, after becoming a Judge myself and learning both the people involved and the standards of problem preparation, I consider it overwhelmingly likely that the Judges knew from the beginning that a table would work and deliberately allowed it.

We finished with seven problems. Ignoring penalty time, we were tied for 28th. With penalties included, we placed exactly 50th—the lowest-ranked of all teams that solved seven.

Afterward, we told our coach that we had solved every easy problem and therefore completed the basic assignment. But I and J had consumed so much time that we had none left for anything else. If we had not overthought I, and if we had known FFT for J, each problem could have saved us at least an hour. With that time, M, a pure implementation problem, might have been within reach. Our mathematics teammate would also have had a strong chance on H, a purely mathematical problem.

Reality offers no such revisions, so we were left with a few regrets. Congratulations went to tourist’s ITMO team, which solved the entire set before time expired, won with a perfect score, and became the first—and remains the only—team ever to finish a World Finals early by solving every problem. The hall erupted during the Resolver. Evidently everyone wanted to witness history.

Each contestant may appear at the ICPC World Finals at most twice. With that, my career as an ICPC contestant officially ended.