Kazakhstan

That September, I was back for the annual World Finals—for the third time that year. It should have been once that year and twice the year before, but the Egypt contest had been moved into 2024 as well.

This was my third World Finals as a judge. I felt much calmer than before, as though it had already become part of the routine.

At the time, Chinese citizens could enter Kazakhstan without a visa. I assumed this would be my smoothest trip yet. International air travel promptly taught me otherwise.

I had originally booked a round trip on Lufthansa: San Francisco to Frankfurt, then onward to Astana. The uncertainty was the connection in Frankfurt, which required taking the airport train to another terminal. I could not determine whether that meant formally entering Germany. In theory, an international hub as large as Frankfurt surely had a fully enclosed transit zone with unrestricted access to the train. Yet after searching both the airline’s and the airport’s websites, I could find no definitive statement that my particular connection would be fine. Everything I read seemed to imply that there was a separate “international transit area” and that no entry formalities were required as long as one remained inside it. I was never entirely certain, but chose to trust that interpretation.

The larger problem came three weeks before departure: the return flight from Astana to Frankfurt was canceled. That invalidated the entire itinerary. Ordinarily, when one flight is canceled, the airline moves you to another departure. But there was only one flight that day. Taking the next day’s flight would not work either, because the onward service from Frankfurt to the United States was also on an every-other-day schedule. I would have been stuck at Frankfurt Airport for more than twenty-four hours. That was impossible for me.

The route was no longer viable, so I had to rebook everything. I received a full refund, but the process was troublesome, and airfares generally rise as departure approaches. I searched again and found no workable European connection for my own passport and visa situation. One option went through Britain but required changing airports; I did not have a British visa. Another involved twenty hours at Warsaw Airport, with the two legs operated by different airlines. I could not establish whether I would need to enter Poland, and I did not have a Schengen visa. Looking through those fares was deeply discouraging. Some well-timed options, including connections through Istanbul, had already disappeared because the date was so close.

Was that it? Was I simply not going?

Once I calmed down, I realized that Astana was almost exactly twelve hours ahead of San Francisco. Why not look in the other direction? I began searching for an eastbound route around the world, and there it was: the best place to “connect” was China. Google did not show such options because they were not really connections at all. They required separate tickets and, in all likelihood, entering the country. I searched independently for a round trip between the United States and China and another between China and Kazakhstan. The timings fit remarkably well, and entering China posed no problem for me. The decision was immediate. I booked it.

Beijing Airport saved the trip. Without that route, I doubt I would have reached the World Finals at all.

After considerable effort, I finally arrived in Astana. Talking with others, I learned that many had also been booked on the canceled flight and had rearranged their travel. Those carrying American passports had far more flexibility when connecting through Europe and avoided most of the complications I faced.

One notable change that year was the arrival of Gennady Korotkevich—tourist, then ranked number one in the world on Codeforces—on the judging team. Judging requires strong problem-solving ability, but not necessarily the ability to solve at competition speed. Many judges either do not compete online or do not have especially high ratings. As a result, when a judge occasionally explained what had happened during a contest on a forum, someone would ask, in effect, “And who are you?” That particular problem was unlikely to arise again.

It was also the first year that we used AI to generate illustrations for some of our problems. The results were excellent.

In the days before the contest, we found a free day for sightseeing in Astana. The main excursion was simply a walk to the Astana Grand Mosque.

It looked exactly like the photographs online. The interior was exceptionally intricate, and obtaining a photograph with no one in it was an achievement in itself.

On the walk back, we saw many posters like these along the street. I could not read the text, but the images appeared to advertise traditional Kazakh sporting events. A sincere question: does training an eagle count as a sport?

The opening ceremony was held in the main hall of the Presidential Center. Security was nearly as strict as at an airport. Since almost every bag had to be opened and inspected, the official advice was not to bring one. Given the schedule, however, contestants who had joined the preceding activities could hardly avoid carrying bags unless they handed them to their coaches to take back to the hotel. Many arrived with them.

I had skipped the earlier activities entirely and reached the venue very early. No one was there yet except the welcoming band.

I then watched the contestants arrive with their bags. An hour later, security was still processing them.

There is little to say about the opening ceremony itself. After attending more of them than I can count, they do begin to resemble one another.

The day before the contest, the organizers arranged another excursion, this time to something resembling a science museum. From outside, it looked like this: a spherical building whose stacked levels were visible through the exterior. Visitors took an elevator to the top, then descended one floor at a time through the exhibits.

Most of the explanatory text in the venue appeared in three languages: Kazakh, Russian, and English. Many of the staff spoke all three, which was impressive. I ran into a former assistant coach from my university who spoke Russian. I asked how different Russian and Kazakh were. To me, the alphabets looked similar—possibly because I could read neither. He said they were very different, entirely separate languages, and that he could not understand Kazakh at all.

This was the contest venue.

Inside were numerous entertainment areas and technology exhibits. That, too, is a long-standing tradition. Contestants can use them during the surrounding days; once competition begins, the coaches and assorted bystanders take over. Downstairs from our hotel there was even a yurt-like structure whose interior looked like this.

On a free afternoon, one could lie down in there and quite happily remain for the rest of the day.

By then, I thought the contest would proceed smoothly. The largest crisis arrived on the evening before it began.

I was at the hotel, had showered, and was preparing for bed. Three calls came while I was in the shower, all of which I missed. When I checked my phone afterward, the message was essentially: serious problem with a problem; come immediately. They called me because I was the author. I will not identify which problem it was. Readers familiar with the complete set may be able to work it out for themselves.

The situation began this way. On the day before the contest, we generally share the problems with the broadcast analysts so that they can learn what each asks and how it is solved. This allows them to record explanations in advance and analyze the contest more effectively while it is under way. The solution to this particular problem began with a case analysis: according to the greedy argument, there were only two cases. As the analysts recorded their explanation, however, the argument felt increasingly suspicious. Why, they asked, were there only two?

In the spirit of proper verification, someone wrote a brute-force solution that enumerated every possibility and selected the optimum. Its output did not match the official data. The brute-force program found a better answer.

That was bad. The exhaustive search was almost certainly right, which meant the official output was wrong and all the judges’ implementations were wrong with it.

It was nearly nine in the evening, with about twelve hours remaining before the contest. Calls went out, and many of us were summoned downstairs. We quickly discovered how easy the problem was to misunderstand. Every one of us who had solved it had independently and quite naturally overlooked the same additional case.

The senior members of the judging team considered how the problem might be changed quickly enough to rescue it. The rest of us asked whether it could be rescued without changing the statement at all.

Something similar had happened at an earlier World Finals. I was not a judge then, but later read the official post-contest analysis. According to that account, on the night before the contest the judges discovered that one problem was fundamentally wrong and could not be repaired, while the problem sets had already been printed, stapled, and sealed. They spent the night opening every packet, removing the staples, taking out the bad problem, inserting a replacement, stapling the set again, and resealing it. The work reportedly lasted nearly all night. By the end, everyone had become an expert staple remover.

Our situation did not appear quite that severe. The missed case mattered only within a particular portion of the input range. If we halved the range, the case would no longer need to be considered. The correction would even look unusually benign: given how the original bound was written, halving it on paper would resemble a simple printing correction rather than a substantive change to the problem. We could have fixed the issue without disrupting the contest, with only a general announcement at the venue.

The senior judges began calling the relevant people to explain that this might be necessary the following morning and that preparations should be made.

The rest of us continued asking whether the problem could survive unchanged. To our surprise, it could. We had indeed missed a case, but apparently only one. Adding it would not change the time complexity of the intended solution. Several of us began modifying our implementations. By then, it was ten o’clock.

Twenty minutes later, the first revised program was ready. Five minutes after that, mine was ready too. Over the next stretch of time, more implementations arrived, including some rewritten from scratch. We cross-checked them against one another and found no discrepancy. We then tested them on cases generated by the brute-force program, and those results matched as well. We now had a correct solution. The crisis had been contained.

We reran the entire dataset with the new judges’ implementation and added many tests for the newly identified case. By the time everything was complete, it was half past eleven. The good news was that no announcement was needed and the problem statement required no change; the issue had been resolved without affecting the contest at all. The bad news was that the problem had become considerably harder. The missing case was genuinely difficult to notice. If a submission failed during the contest, a team would have little way to know whether the implementation contained a bug or whether the underlying analysis had missed a case. If necessary, they might have to spend precious computer time—three contestants share a single machine—writing a brute-force solution for cross-checking.

The next morning, the contest began normally. As the problem author, I soon realized that it was much harder than I had originally imagined. Even setting aside the extra case, I had expected many teams to submit and then fail because of it. In reality, there were hardly any submissions at all. The first accepted solution did not arrive until three hours into the contest, making it one of the three hardest problems in the set.

We watched every submission to it closely. At the time, every team’s first attempt omitted the additional case. Not one succeeded immediately. The trap was every bit as effective as we had feared.

In other words, had we not found the issue the previous night, the contest might still have proceeded normally. No one would have noticed, and no team would likely have been affected, because no one identified the missing case before first receiving a wrong answer. Only much later, after the data became public, would someone probably have returned to perform the postmortem.

During the contest, a judge with time to spare gave the problems to several AI systems. If I remember correctly, they produced complete, correct programs for only two or perhaps three problems—and not even the easiest ones. At that point, their competitive-programming ability still varied wildly and clearly needed both greater consistency and further improvement. Who could have imagined that barely a year later, AI systems would be solving entire ICPC-style problem sets?

Finally, congratulations to Peking University on another championship. A penalty-time lead of nearly 300 was itself a display of strength.

The most painful result was Tsinghua University’s. They finished one test case short of their first world championship. Looking only at the scoreboard, an outsider would see two problems with wrong submissions and think the result unfortunate. As judges, however, we could see that on one of those problems their program failed only the final test case. We examined that test repeatedly and found nothing remarkable about it, yet they never located the bug. Had they corrected the failure and passed that submission, they would have solved one more problem and won the championship. It was extraordinarily close.