Russia

This was my first ICPC World Finals, and I was tremendously excited. At the time, it was still called the ACM-ICPC World Finals.

I will skip the path through regional competition here. For us, that road seemed to lead through Grand Rapids, Michigan, every year; the full story belongs in a separate account of the qualifiers.

I do have to say something about the Russian visa, because it was among the most difficult I have encountered. The application required the original invitation issued by the event. First, the organizers had to be authorized to issue such a document at all; then the physical original had to survive international shipping. It looked appropriately formidable: special brownish-yellow paper covered in text I could not read, with a serial number, my name, signatures, and stamps. That document then had to cross an ocean from Russia to the United States. If it had disappeared in transit, I suspect the practical answer would have been to give up. We eventually hired a travel agency to handle the visa and book the tickets. As far as I remember, the visa alone cost each of us more than $300. Fortunately, the university reimbursed it.

Before the contest, I was in China while both teammates were in the United States, so we had almost no team practice. We attempted two online sessions, coding while connected by video call. They were essentially useless. Before I returned to China, our academic schedules had allowed only a handful of practices together; otherwise, everyone trained alone. We were walking into the World Finals with almost no team preparation.

The trip itself began with a request for leave. I never imagined that I would need formal permission to miss time at a university, much less that obtaining it could become this complicated.

I was enrolled in the 2+2 program at the University of Michigan–Shanghai Jiao Tong University Joint Institute. I spent the first two years at SJTU and the next two at Michigan, then returned to Shanghai for a final-semester capstone project. Completing it meant receiving degrees from both universities. Students could choose not to return, in which case they would receive only the Michigan degree. In practice, many people who planned to work in the United States stayed there instead. From that perspective, returning to Shanghai for the second degree seemed less useful than spending the semester on another U.S. internship, which was far more likely to help with recruiting. The result was an unusually low completion rate for the dual-degree path. As far as I remember—and my memory may be off—it was under 80 percent, probably near the bottom at SJTU.

I was now back at SJTU for that final capstone semester. I already had enough credits, so the project was my only course. I had returned largely because I still did not know where I wanted to build my career and thought it prudent to secure both degrees first, even though I would most likely work in the United States. That made me remarkably relaxed about the consequences. If I somehow failed to graduate from SJTU, I could live with it; I would simply have spent a summer in China with friends.

That was the background. Then contest week approached. University students skip class all the time; this is hardly unique to China, and professors at Michigan rarely took attendance either. What surprised me was that, in an environment where quietly missing class was routine, formally asking permission to miss it seemed almost unforgivable.

I had not planned to request leave at all. There were only two class meetings that week, and I could simply have skipped them. Unfortunately, the second capstone presentation fell in the same week and counted for 5 percent of the final grade. I was not concerned about losing those points; passing the course should not have been a problem. But when I spoke to the faculty member leading the capstone supervisors, he told me I could not miss it: failing to attend any presentation meant failing the entire capstone.

I was stunned. How could missing something worth 5 percent automatically mean failing the course? I searched the syllabus, grading documents, and every other piece of course information I could find. None mentioned such a rule. I might have understood it for the final defense, but this was only the second presentation, with two more still to come. I could not understand the decision. With the limited perspective I had then, I could only interpret it as my request having bruised his pride.

There was little I could say beyond explaining that this was an important competition—the World Finals—and asking whether formal university leave would make the absence acceptable. He said he might consider it if the leave were official. So I had no choice but to begin the process.

That meant going to my student advisor. I no longer remember how many signatures were ultimately required—perhaps three—but his approval came first. I explained that I needed leave for the competition. His manner was gentler than the faculty supervisor’s, but the underlying questions were similar: Why did I need to go? Was the capstone not important? Did I truly have to attend? My answer was firm: yes, I had to go. As I said above, I privately placed little value on the SJTU degree if I ended up working in the United States and was prepared to do without it. I did not say that aloud, of course, but it made my outward position very clear. I was going.

Perhaps my advisor was persuaded by that resolve, and perhaps by my earlier record at SJTU: I had ranked second in the institute by GPA and received an academic achievement award, so I had a well-established reputation as a good student. He finally approved the leave and told me to compete well and bring honor to the university.

The awkward part was that I was representing the University of Michigan. SJTU’s programming team was already exceptionally strong; it certainly did not need me, and I doubt I could have made that team anyway. Naturally, I said none of this. I still wonder what my advisor would have thought if he had known I was not competing for SJTU at all.

Eventually I obtained the leave and the necessary senior signatures. I returned to the faculty supervisor, who agreed to deduct the 5 percent without failing me outright.

It had taken an absurd amount of effort. As an introvert, I felt as though this one request had consumed my entire social quota for the year.

At last, with nothing left hanging over me, I could go compete.

I flew alone from Shanghai. My teammates and coach traveled from the United States. As noted earlier, many students chose to remain in America for internships rather than return to SJTU for graduation, and one teammate had done exactly that. His standard U.S. technology-company summer internship lasted twelve weeks—exactly twelve weeks—and he needed to miss an entire one of them. That could not have been easy either. His account also included some version of “I absolutely have to take this week.” Somehow he cleared every obstacle and secured the time off, despite the risk that it might hurt his chances of a return offer.

My flight connected in Moscow, as flights to many parts of Russia seemed to do. The transfer was smooth until immigration. The officer asked where I was going. I said, “Yekaterinburg.” He replied, “Екатеринбург?” I repeated, “Yekaterinburg.” He repeated, “Екатеринбург?” And around we went.

That is almost a transcript of what happened. I was speaking English, and he mostly was too, except that he pronounced the city in Russian. The Russian and English pronunciations differ substantially, especially in where the stress falls, and I had no idea what he was saying.

Eventually he seemed to understand me and let me through.

I reached Yekaterinburg, arrived at the hotel, and met my teammates. Then all three of us realized the same thing: nobody had brought a plug adapter.

It was not our first time abroad—we had all obviously been to the United States—but that had been different because we lived there long enough that buying adapters was unavoidable. This was probably the first trip for all three of us to a country where an adapter was genuinely necessary, and not one of us had thought to pack one.

We appointed a representative to ask the front desk whether we could borrow one. That representative was me. My English was not very good then. After I tried socket, power, and charger, the receptionist smiled and said, “I think what you want is an adapter.” To be honest, I did not know the word, but it sounded convincingly like the object I needed.

I obtained one adapter. For the rest of the week, all three team members gathered in one room every day and took turns charging our devices.

I barely remember what we did during those days. I think our coach took us to a few sights around the city, but I cannot recall what any of them were. Nobody on the team spoke Russian. Our assistant coach, as I remember it, may originally have been Russian but had moved to the United States for reasons he did not really spell out. According to him, if he entered Russia again, he might have great difficulty leaving. He phrased it carefully, and that was only how I understood it. Had he been with us, perhaps we would have seen more of the city.

Then contest day finally arrived. The problem set was catastrophically difficult. A rumor circulated that the Judges—the people who selected and prepared the problems—had deliberately made it brutal because they feared tourist might finish early by solving the entire set before the five hours were over. Gennady Korotkevich, known by the handle tourist, was widely regarded as the strongest competitive programmer in the world at the time. His team had come very close to finishing the previous year’s set. According to the official post-contest analysis, three extreme test cases had been added to the hardest problem shortly before the contest; without them, his team would have solved the entire 2013 problem set.

Whatever the origin of the rumor, and whatever caused the difficulty, the 2014 set was a disaster. Years later, after I became a World Finals Judge myself and learned how problems were selected, I found that year even harder to explain. I asked a number of people who had been involved, and their answers were variations of, “Was there something unusual about that year? I don’t remember.” The rumor was probably nonsense. To the Judges, it appears to have been an ordinary World Finals whose difficulty simply went badly off course.

Back to the contest.

The first solve on Problem K came at 17 minutes. By the 15-minute mark, we already knew something was wrong. In a normal year, the first solve would almost certainly have appeared around ten minutes; this time the entire scoreboard was still silent. Things did not improve after K was solved. Usually, once the first problem falls, every team turns to it and dozens have accepted it within an hour. Here, almost nobody followed. We read K, had no idea how to solve it, and fell quiet ourselves. We could tell it was a data-structure problem but could not see how to use one. We submitted a few improvised optimizations, accumulated eight wrong attempts, and never solved it. The solution required a range minimum query structure. At the time, we were nowhere near good enough: all three of us had heard of RMQ, but none had mastered even that basic technique well enough to recognize it.

The deadlock lasted until minute 28, when someone solved D. We reread it and decided it might be manageable. Earlier we had not been sure; it was not an obvious easy problem. But if another team had solved it, then it had to be possible. One teammate took it on, and roughly an hour later we accepted D, our first solve of the contest.

Problem C received its first solve at minute 35. It was computational geometry: clearly solvable at first glance, but full of cases and difficult to get accepted. All three of us were weak at geometry, and whenever one appeared, I was usually the person sent in to improvise. As expected, C had case after case. We made six submissions and never solved it. During the contest, we thought we were close. Afterward, we downloaded our code and the official data and discovered that we were nowhere near the correct solution. The computation used real numbers but required integer output, demanding careful treatment of precision. When a result lay arbitrarily close to an integer, different cases required rounding up, rounding down, or taking the nearest value. Three computational-geometry novices were not equipped for that distinction. We had no realistic chance of getting C accepted.

At minute 68, someone solved I. We read it and could not solve it either—but this time our reaction was different. We looked at the team with the first solve and thought, Wait, that team solved I? Then surely there had to be some way to hack it. We still could not devise a clever heuristic, so we used the bluntest possible approach: brute-force search with deliberate time management. The program searched until it was close to the time limit, stopped, and printed the best answer it had found, whatever that happened to be. It worked. As a precaution, we randomized the input order first in case the data had been designed to punish a fixed ordering. Our first four submissions failed because the stopping threshold was wrong and the program exited too early. After tuning the parameters, our fifth submission was accepted. The team with the first solve on I did indeed finish the contest with only that one problem. That has to be one of the strangest one-problem performances in World Finals history.

The other solved problems had little to do with us. We would read one, realize we had no idea how to solve it, and quietly move on.

We recognized B as a knapsack dynamic program requiring the multiple-knapsack optimization, but nobody remembered how that optimization worked. In fact, the problem required taking the underlying idea and deriving an additional optimized formula. We were plainly not capable of doing that on site.

E was the most painful missed opportunity. We read it and found no direction at all. In reality, its entire logic matched DFA minimization, which one teammate and I had studied together only a year and a half earlier. Somehow neither of us remembered it. The problem should have been a gift, but in the contest we never saw the connection.

We also attempted A. Nobody solved it during the contest, including the unofficial teams. We tried largely because we could not do much else. It was a constructive, ad hoc problem rather than an algorithmic one, so one teammate spent three hours thinking about it from the middle of the contest onward. He submitted twice without success. Afterward, our coach asked whether those submissions had been serious. They had. A was in fact solvable, but the empty column on the scoreboard had frightened every team away. Someone later asked the Judges, who had apparently regarded it as the easiest problem in the set—something they expected to be the first solve and then widely accepted. That mismatch was remarkable. For the four cases of n mod 4, the true optimum was n in every case. My teammate had successfully derived n for three of them; for the last, he could only reach n+1. We had come painfully close to what might have been the first—and perhaps only—official solve of A.

We finished the contest with two problems solved.

The frustration afterward was palpable. A World Finals set this difficult felt almost unheard of, which helped the rumor about stopping tourist from finishing early spread quickly. An unofficial tourist team solved seven problems with a lower penalty time and would have placed first, but unofficial teams did not count in the standings. They nearly reached eight or more. One member spent an hour on A and still did not solve it, further evidence that it was not remotely trivial. J was ingenious: its broad direction was visible, but the derivation was punishing and the implementation enormous. Petr later described a moment in which the coding was finished, only for the team to realize they had forgotten the requirement for the lexicographically smallest answer—and abandon the attempt.

The Resolver then produced a dramatic reversal. At the scoreboard freeze, Moscow State University led with six solved problems while second place had only four. Given the difficulty, the championship looked all but certain. Instead, St. Petersburg State University solved three problems in the final hour, also finishing with seven and winning by 39 penalty minutes. Their last accepted submission came after eight wrong attempts, with only two minutes left in the contest. It could hardly have been closer.

Those stories aside, all three of us were deeply disappointed. We agreed on one thing: we would return the following year.