ICPC Regional Contests: The Complete Story

2012

The story has to begin with the 2012 regional contest. The fact that I entered at all was something of an accident.

I had started competitive programming in high school, also by chance. A teacher came to promote it to our class with stories of exceptional students who competed internationally, earned full scholarships worth tens of thousands of dollars, and were admitted to Princeton. Our provincial contest cost about 30 yuan to enter. He reduced the proposition to one memorable line: pay thirty yuan, earn three hundred thousand.

So I signed up, became absorbed in it, won a silver medal at the national competition, and secured admission to Shanghai Jiao Tong University.

I knew what caliber of student attended SJTU; many were far stronger than I was. Its ICPC team was stronger still, with several world championships behind it. I therefore entered university with no intention of continuing. I clearly had no chance.

That changed when I arrived in the United States in 2012. I was in a 2+2 program: two years at SJTU, two at the University of Michigan, and degrees from both. I came to Michigan as a junior. Michigan had just placed second and won gold at the 2011 World Finals, the best result in school history, and the department displayed the achievement prominently in its main building.

I noticed it and moved on. My roommate saw an opportunity. SJTU was formidable, he reasoned, but perhaps Michigan was not. He investigated and discovered that the 2011 team—qualified through the 2010 regional—had depended on two extraordinary contestants: one later retired and became our student coach, while the other was a one-semester exchange student and former member of China’s IOI team. Neither remained eligible afterward. Without them, the program collapsed and did not even reach the 2012 World Finals.

My roommate read the 2011 regional problems, studied the standings, and reached a simple conclusion: he could do this too.

The contest required teams of three, so he approached me with the one line that worked: “Don’t you want another chance at that dream?”

He produced the 2011 problem set. This one was trivial, he said. So was the next. We examined six problems, all apparently easy. “See?” he said. “That’s qualification right there.”

I joined him.

Our team selection that year took several turns, then broke altogether.

Before the internal qualifier, we asked the coach how teams would be formed. Could the two of us lock ourselves into one team? No, he said. For fairness, the top three would form Team One, the next three Team Two, and so forth. Did that mean we had to manipulate our scores?

In practice there seemed little reason. We had placed first and second in every practice contest before the qualifier.

Then the qualifier went badly. My roommate had grown overconfident and spent too long on a difficult problem, leaving several easy ones untouched. Worse, the qualifier ran on two days over a weekend, and contestants could choose either day. We both competed on day one. Even after his mistakes he remained second, so all seemed well. On day two, however, two unexpected contenders appeared. Neither had attended any practice, so we had not known they existed. Both passed him easily.

The plan fell apart. I would apparently team with those two, both Chinese international students. I did not particularly mind, but for my roommate it was the familiar story of asking a friend to accompany you to an audition, only to watch the friend get the part.

I finished first with 7 problems, the next two solved 6 each, and my roommate solved 4. The gap was too large to challenge unless one of the others withdrew voluntarily.

Neither did. I joined them instead. I will call them my problem-reading teammate and my passenger teammate. The first would become the teammate who concentrated on analyzing problems during our two World Finals appearances, although at this point he still did plenty of implementation.

The passenger teammate supposedly had a considerable reputation in high school and was once spoken of alongside Cao Qinxiang, winner of China’s 2008 National Olympiad in Informatics. That sounded formidable.

He then let us down on a truly impressive scale.

Before the regional, we heard that our region would receive a wildcard. We believed it normally sent three teams and would therefore send four. Its three leading programs—Carnegie Mellon, Waterloo, and Toronto—were exceptionally strong. The first two regularly approached the World Finals medal positions; Toronto, we heard, had a former national IOI team member that year.

Those three were elite not merely within the region but throughout North America. Waterloo and CMU frequently finished as the top North American school at the World Finals. The balance changed only later, when MIT attracted a number of strong Chinese contestants.

Judging from World Finals results in those years, North America was a comparatively weak region: stronger than Africa, the Arab region, and South America, but well behind Europe and Asia on average. Within that weaker region, ours was among the strongest.

We thought the wildcard solved everything. Remove the three established powers and we were the obvious next choice; the other schools that year did not appear competitive.

We were relaxed, concerned only with preserving fourth place. We did some university-organized practice but nothing extra. I barely knew my new teammates.

Contest day brought nine problems, of which the first eight were straightforward. They still required some code. By World Finals standards the implementation was negligible, but our coding was ordinary then, and we spent considerable time on those easy problems. CMU solved the first six in ninety minutes and reached eight around the three-hour mark, finishing everything before the scoreboard freeze.

My problem-reading teammate and I needed more than four hours to implement and debug six. Meanwhile, the passenger teammate began with the final—and hardest—problem. Problems are not normally arranged by difficulty; by coincidence the last one was hardest, and by coincidence he read in reverse order.

It was geometry. With any experience, we would have recognized it as the sort of deliberately formidable regional problem meant to keep the strongest teams occupied. Our teammate was extremely confident, declared it manageable, and began coding. He produced a program of just over 60 lines near the start and failed to debug it for the rest of the contest. No surprise: the official solution required more than 200 lines of case analysis. Sixty lines were unlikely to cover it.

It consumed much of our early computer time. Midway through, he abandoned geometry and moved to Problem 7, another easy one involving currency conversion and shortest paths. The catch was that floating-point arithmetic introduced too much error; fractions had to be maintained with 64-bit integers. He used floating point and failed again.

An hour later, the problem-reading teammate recognized the issue and rewrote it with fractions. It still failed. We solved neither problem. Afterward we discovered that one array had simply never been initialized. Set it to zero and the solution passed.

Problem 8, the only one I never even read, was basic network flow. I could have solved it. The contest never gave me the chance: all our computer time went into debugging the other two.

We finished with 6. CMU completed the set; Waterloo and Toronto reached 8 around three hours but did not finish everything.

In the postmortem, the passenger teammate suddenly realized he had effectively contributed nothing: two attempted problems, neither accepted, zero additions to the score, and a great deal of computer time consumed.

My roommate competed on Team Two and had an even worse day. One teammate was an American whose name, rendered phonetically in Chinese, sounded rather unintelligent. We had thought little of it beforehand. After the contest my roommate was furious, and the unfortunate implication of the name became the man’s permanent nickname in our stories.

My roommate knew his team was essentially along for the ride, so he did not take the contest very seriously and spent much of it coaxing this teammate through code. The experience was startling: algorithms went unexplained and implementations went unwritten, painful to watch at every turn.

We placed eighth overall, behind four CMU teams, two Waterloo teams, and one Toronto team. Looking at that list, qualifying might itself have been awkward.

After a month of waiting, we learned that we had not qualified. Our region did not normally have three places after all; it had two, and the third was already the wildcard it regularly received for being strong. There would be no fourth.

Misfortune can conceal good fortune. In retrospect, not qualifying spared us a World Finals appearance in which we would merely have made up the numbers. The passenger teammate was no longer eligible after that season. The problem-reading teammate, my roommate—now the mathematics teammate—and I decided to train properly, compete seriously, and stop treating the World Finals as merely a vacation.

This was alarming. We had only wanted a trip. How had we suddenly acquired ambition?

I could not have imagined how much further my relationship with the World Finals would extend.

In early 2013, the latter half of that season, the three of us trained frequently with others from Michigan. CMU’s student coach and ours were friends and both served on the USACO committee, so we often trained at CMU, occasionally alongside members of the U.S. IOI team, who demolished us. We had entered no official contest as a trio, though we had done many informal ones. The difficulty with informal practice was that our roles remained casual: whoever felt like coding did so. We had not yet settled into the roles that would later define our problem-reading and mathematics teammates.

Searching through emails more than a decade later, I found this ancient photograph sent by our assistant coach.

2013

By 2013, it was time to contemplate score management again. After more than half a year of serious, if hardly relentless, training, our fundamentals were vastly stronger.

Would unexpected rivals appear? We did not know. None did, and given what we knew of the school, none should have. All three of us had earned first prizes in Chinese provincial informatics competitions. Against students who began programming at university, there was little reason for us to lose.

We passed the internal qualifier safely in the top three. One newcomer with astonishing typing speed stood out: he implemented 3 of 7 problems faster than either teammate. But speed was his limit. He finished with 4 while each of us solved at least 5.

At the regional, our goal was qualification; our coach’s was beating Waterloo. Michigan had once taken World Finals silver ahead of Waterloo but had never beaten it at the regional, and Waterloo was consistently strong. The coach had made this a longstanding objective.

We still allocated implementation almost at random. The problem-reading teammate coded at least two solutions and, after finding his own disastrous bug, passed a simulation problem. The mathematics teammate stared at the final problem, I, an easy one, wondering whether intermediate values could exceed 18 digits and require big integers. When another Michigan team passed it, we knew big integers were unnecessary: we knew their level, and they certainly could not implement them. He took over and passed almost immediately.

We discarded Problem G, a geometry problem, on sight. Was this meant for human beings? That was the correct decision. The judges’ implementation was nearly 300 lines. The contest later appeared on Codeforces for the world’s strongest contestants to attempt; ten years later, nobody had solved it within five hours.

The main drama was Problem E, a network-flow problem whose modeling was already difficult. When the problem-reading teammate and I found the formulation, it was deeply satisfying. We coded it, submitted, and timed out. We replaced the initial linear search with binary search, submitted again, and still timed out.

The margin seemed substantial. Each submission took five minutes to return, suggesting a genuinely long run.

We ran out of ideas. With linear search, we knew in theory that the graph need not be rebuilt each time; one could continue augmenting the existing graph. We did not know how to implement that, though it was probably the intended solution.

With 12 minutes left, we tried speculative and constant-factor optimizations and submitted frantically. Judging was so slow that every submission remained queued.

About five minutes before the end, one passed—the submission from seven minutes earlier. By then, countless later attempts were stuck in the judging system. When the acceptance appeared, all three of us shouted loudly enough for the room to hear. Someone applauded, then others joined, and soon contestants across the hall were applauding us.

It was a remarkably friendly response. They did not even know what had happened; accepted submissions after the scoreboard freeze were not displayed.

We qualified in second with 7 problems, tied with first on solved count. We also beat Waterloo—and pushed them into fourth, out of the World Finals entirely. Later we learned that even without the final acceptance, we would still have qualified and remained second in the school standings, which rank only each school’s best team. We had been safer than we realized.

Training that year remained much like the previous year: team sessions when schedules allowed and individual work otherwise. The problem-reading teammate and I took a graduate algorithms course, one of the hardest courses most students encountered. I later spent five years as its teaching assistant during my PhD and came to understand that very well.

At the time, however, we treated it as an easy elective. We sat at the back discussing World Finals problems, barely listened, and both earned A+ grades.

We also entered NAIPC, the North American Invitational Programming Contest. Its predecessor was the University of Chicago invitational the previous year; now renamed, it invited North America’s World Finals qualifiers to compete. It was not an official qualifier. After North America’s contest structure was reorganized, it gradually evolved into NAC and entered the formal qualification system.

That year’s NAIPC was lavish. The venue was a grand library reading room that looked remarkably like Hogwarts. Competing together in person was excellent, and the prize pool aspired to World Finals scale: $12,000 for the champion, $6,000 for second, and $3,000 for teams in the silver award tier.

We placed fourth, received a silver award, and collected $3,000—the first and only prize money of my competitive career. Our timing was fortunate. The prize pool collapsed over the next few years, eventually becoming a $250 Amazon gift card for a gold award. Apparently the first year had consumed the next decade’s budget.

There were 21 teams. Our region’s three World Finals qualifiers placed third, fourth, and sixth. Within North America, our region really was exceptionally strong.

I remember little of the contest itself beyond passing our last problem around three hours and then knowing nothing else for the remaining two.

Before the World Finals, I returned to SJTU to graduate while both teammates stayed in America. That was the end of organized preparation; we did no serious training.

2014

A new season began. Having learned from the previous World Finals, we had to train properly. We had been far too casual.

How had this become more serious every year?

Human appetite is endless. Once something is attained, one wants more. We began merely hoping to travel to the World Finals; now we wanted a medal.

Team selection brought a new complication. I had graduated and begun a PhD. Many strong classmates from SJTU also came to Michigan for graduate study. More worrying, the mathematics teammate discovered that a graduate student from National Taiwan University had won World Finals gold and was Codeforces red-rated—among the platform’s elite. We called him the red-rated star.

If he competed, one of us would certainly lose a place.

Fortunately, we met him at the information session and learned that he was no longer eligible. We relaxed.

None of the other strong arrivals from SJTU entered either. The three of us again swept the top positions and stayed together.

The regional was anything but calm, though the result was never seriously in doubt. After its Waterloo the previous year—apparently ending a very long streak of World Finals appearances—the University of Waterloo returned seeking revenge and won with 8. Two schools followed with 7; the next had only 5. The top three schools were far ahead.

The contest itself was unnerving. Perhaps the problem setters had imitated the previous World Finals’ extreme difficulty. For the opening 20 minutes, the room was silent and nobody solved anything—abnormal even at the World Finals. Waterloo’s winning team recorded its first acceptance at 42 minutes; the runner-up and our team did not score until after an hour. The set began at medium difficulty, with no easy entry problem. Teams below 22nd solved only one, and those below 42nd solved none. For ordinary contestants, it must have been miserable.

No problem particularly stayed with me at the time. Only later did I revisit Problem I and appreciate how good it was: computational geometry preprocessing followed by network flow, genuinely World Finals caliber. We discarded it immediately. Waterloo solved it after the freeze, fully deserving the title.

We finished third and grew slightly nervous. Strictly speaking our region still had only two guaranteed places; third depended on a wildcard. Given these results, surely the wildcard would come to us.

It did, and we qualified without further drama.

We again entered NAIPC and placed sixth for a silver award. The prize was already incomparable to the previous year: a $150 Amazon gift card per person. Had the contest gone bankrupt after one edition?

We trained a great deal that year, hoping for a strong World Finals result.

2016

I did not participate the previous year because our student coach was still in place. In 2016, during the fifth year of his PhD, this exceptional competitor simply left the program to start a company.

I was astonished. From the Chinese perspective I knew, leaving in year five was almost incomprehensible. Graduation was close; why abandon that investment rather than endure a little longer?

Americans, however, often made such decisions more freely. He wanted to found a company, so he did.

Michigan was left with a vacuum. The faculty coaches generally did not manage student training; the student coach did. When he departed, I stepped in, feeling as though I had been summoned in an emergency.

I worried over every aspect of the program, beginning with recruitment. All three of us had retired the previous year, and Michigan’s regional results had predictably collapsed. Team Two did best in 12th, followed by Teams Three and Four, while Team One fell below 30th. So much for a qualifier that supposedly assigned teams strictly by rank.

Knowing the talent pool was empty, I recruited personally. That summer I assisted an introductory algorithms course and invited every high-finishing student to compete. They did not look strong enough to qualify, but they were better than nobody.

At the start of term I prepared practice contests, contacted the leading students one by one, and found a younger student from SJTU with contest experience. After considerable persuasion, he agreed to enter.

Eventually I found three contestants who had each earned first prizes at Chinese provincial competitions. That ought to have been enough for qualification.

Reality disagreed. Their weak implementation prevented them from qualifying—and they did not even survive our internal team selection intact.

They had consistently occupied the top three in practice, so I relaxed. Then the official qualifier produced another surprise.

Two American contestants who really were brothers—the older and younger brothers—finished first and third. Unlike our 2012 surprise arrivals, they had attended practice and performed reasonably, but never this well. Apparently they had chosen the right moment to peak.

My three recruits landed second, fourth, and fifth. Team formation became awkward. They naturally wanted to stay together, particularly because one spoke very poor English and pairing him with Americans would have made everyone uncomfortable.

I entered a prolonged argument with the faculty coach, who insisted that the top three form Team One. I urged him to consider the contestants’ preferences. After several rounds, he agreed if the two brothers consented.

They did. My impression was that they had no strong preference; merely placing this high was unexpected, and qualification for the World Finals probably had not entered their minds.

Ranks 1, 3, and 6 formed Team One; ranks 2, 4, and 5 formed Team Two.

The sixth-place contestant now entered the story. I called him the Hong Kong Correspondent. He was Chinese, studied in Hong Kong, and was at Michigan for a single exchange semester. He was not a journalist; the nickname reflected his extraordinary command of contest gossip. Ask him anything and he knew it, living up to the old joke about reporters who somehow reach every corner of the world before their Western counterparts.

After selection, he asked about training and essential algorithms. He had begun programming at university and competitive programming only that semester, so his foundation was thin. I did know one shortcut. After years in this regional, I knew its style: nearly every contest included network flow, and the flow problems had grown easier. I had even placed two in the internal qualifier specifically to identify contestants who could solve them.

I told him to ignore everything else and concentrate entirely on network flow.

That advice proved invaluable. Neither brother knew flow. The Correspondent solved the regional’s flow problem, giving the team enough solved problems to surge into second place in the final 10 minutes and qualify. Otherwise they likely would have finished outside the top ten.

At the time, however, I devoted more attention to Team Two. They were easier to summon informally and always came when asked; Team One generally appeared only for official practice.

The three recruits’ implementation ability stunned me. Once, nobody attended my office hour, so I brought them in to practice a basic single-source shortest-path problem. I came apart watching three provincial first-prize winners fail to code it in ninety minutes. Had I really been this weak in my first season?

They continued failing to debug easy practice problems. At the regional, weak coding again cost them straightforward problems, and Team One completely outclassed them.

The older American was an exceptional implementer, both fast and disciplined. According to the Correspondent, he followed OOP rigorously, defining classes rather than relying on loose functions and global variables. That was rare in contests because it increased code volume and usually reduced speed. Its benefit was equally clear: when something failed, his structured code was much easier to debug.

Team One qualified, and I was delighted: another World Finals trip. Then we learned it would be held in the United States, and I was disappointed.

The Correspondent returned to Hong Kong after the semester, and the team barely practiced together. I later heard they did some online training, but we all know how effective that tends to be. At SJTU, we too had claimed to practice online.

Everyone else remained. Their algorithmic foundations were so weak—or nonexistent—that I began an informal class.

It was entirely volunteer work. I mainly wanted the two brothers to learn the standard algorithms before appearing at the World Finals.

Then another contestant came into focus: a different American whom I will call American Two. He had finished seventh in the qualifier, led Team Three, and was clearly dissatisfied with that outcome.

The brothers attended perhaps 60 percent of the class. American Two came every time. I taught extremely quickly because time was short and the syllabus broad; within three or four weeks attendance had nearly vanished. Once, he was the only person there, and I delivered the entire session to an audience of one.

Over the semester I felt I had passed everything I knew to him. How much he absorbed remained unclear.

2017

Another season arrived.

I again recruited everywhere, though I now had some confidence in the American contestants, particularly after American Two had learned many algorithms and the older American had reportedly become even faster.

At the information session I met two Peking University graduates beginning graduate study at Michigan. Unlike the previous year’s three recruits, both had competed on Peking University’s ICPC teams—perhaps not Team One, but Teams Two, Three, or Four. They possessed genuine ICPC experience and should at least have reliable implementation. I was excited. I probably could not have made SJTU’s fourth team; surely someone from Peking’s second could handle a regional without my help.

So I gave them none.

Both underperformed in team selection. I thought the contest itself was excellent: every problem was solved by at least two people, nobody solved all 12, and the winner finished with 9—the most balanced outcome I could imagine.

My one regret was a mathematics problem whose derivation seemed wonderfully elegant. In practice, contestants either knew the result and solved it immediately or had no avenue to derive it during the contest. That was poor design.

With enough problems and separation, the qualifier remained dramatic to the end. I invited my former mathematics teammate to watch online. The final 30 minutes brought repeated reversals: American Two used his solid algorithms to reach first with 9 at 15 minutes remaining; then, with four minutes left, the older American found the mathematical result and jumped to second with 8. Until then we had blamed that problem for potentially excluding him from Team One. He rescued himself on merit.

The top three became the older American, American Two, and an unfamiliar American I will call American Three. The two Peking graduates finished fourth and fifth, hurt chiefly by penalty time and perhaps by my mathematics problem. The Americans seemed to know the result; neither Peking contestant did. Without it, both might have reached Team One.

I liked the resulting structure. With the older American and American Two anchoring Team One, regional-level strength was secure; who the newcomer was scarcely mattered. The two Peking contestants made Team Two so strong that, as a joke, its third member almost seemed optional. The top five were far ahead: fifth solved 8, sixth only 5.

At the regional, Team One justified that confidence. The older American was extraordinary. Others read the problems, but he wrote every solution, coding 6 accepted problems in 1 hour 14 minutes and taking the lead. Progress slowed afterward, but they added two more and qualified as the region’s second-ranked school.

Team Two matched their solved count with more penalty. Without Team One, their third-place school position would probably also have qualified.

Nothing more was needed that year. Both Peking contestants planned to return, so the next season looked secure.

Then I learned the World Finals would be in China. So much for free international travel; I would treat it as a university-funded trip home.

2018

Another season began.

Both Peking contestants returned. We seriously discussed whether they were still eligible. People generally believed students more than five years into university could not compete. Reading the rules closely, however, we understood the two conditions to be alternatives: either the enrollment-year requirement or the birth-date requirement might establish eligibility. That was our understanding at the time.

While serving as a teaching assistant for algorithms, I recruited one more contestant: a fellow SJTU alumnus who was now a PhD student, with contest experience but none in ICPC. That seemed fine. The Peking pair could implement; he could concentrate on analysis. After considerable persuasion, I had another all-Chinese trio. The World Finals location was already known to be Portugal, so the four of us created a chat called the “Portugal Tour Group.” Results there hardly mattered; qualification was enough to secure the trip.

Team selection ruined the plan. The first Peking contestant, the SJTU contestant, and the second Peking contestant solved 8, 5, and 4, placing first, third, and fifth. Pulling fifth into Team One would be difficult. Second place belonged to American Three, with 6. In short, first was far ahead and everyone else occupied supporting roles.

The fifth-place contestant had only himself to blame. A little over an hour in, he attacked the hardest problem and remained stuck until the end, at one point questioning the data. When I explained the solution afterward, he realized his approach was wrong. Who plays a contest like that?

The second Peking contestant withdrew from consideration. The first Peking contestant, the SJTU contestant, and American Three formed Team One. Our Portugal Tour Group officially disbanded.

With reasonable execution, this team could still have reached the Finals. Instead, at the regional, they again failed to implement easy problems. They did finish as the region’s third-ranked school, but first solved 9, second 8, and they solved 5; no wildcard was awarded.

It was frustrating because their only opponent seemed to be themselves. They were going to finish third regardless; a marginally better performance might have secured the wildcard.

The Portugal Tour Group was formally dissolved.

My coaching career ended there. Across six visits to the same regional site, I qualified twice as a contestant and coached two more qualifying teams. It had, on balance, been a distinguished run.

I did not yet know that an entirely new chapter of the World Finals was about to begin for me.