Tag → competitions

Olympiads: The Infinitely Overdue Retrospective

I put this question in my FAQ, because at least two people have asked me this question, and that’s how frequent a question needs to be to be on my FAQ: I got an IMO1 gold medal in 2012, as a ninth grader, and an IOI gold medal in 2014, as an eleventh grader. I could have kept going to either, or even decided to try taking the IPhO or something, but I didn’t. Why not?

The short answer: It was a rough utilitarian calculation. By continuing, I would probably displace somebody else who would gain more from being on an IMO/IOI team than I would. Besides, I wanted to do other things in high school, so I wasn’t losing much.

I think the short answer actually captures most of my thinking when I made the decision back then, and it’s not really new; I said as much at the end of 2013. But behind it was a lot of complex thoughts and feelings that I’ve been ruminating over and trying to put into words for the better part of a decade. Hence, this post.


There is a natural question that precedes the frequently asked one that I have never been asked, something I am now realizing I never honestly asked myself and never tried to answer deeply: Why did I participate in the IMO and the IOI in the first place?

Jam-Packed Fun and Games

Did I say “fun”? That was short for function calls. Which are fun too, admittedly. Blah, I always go to such lengths to come up with snappy yet justified post titles and end up achieving neither.

One more complimentary breakfast later:

This is it.

Google Code Jam World Finals. [Google Code Jam 2015 name tag with my name and handle and country] Let me take a moment to reflect. Seriously. I do not know how I made it this far this year. I guess I might be a top-500-ish competitive programmer globally, maybe even top-150-ish, but definitely not top-25-ish. And Log Set, the hard problem that got me through Round 3, doesn’t seem like it plays to my forte particularly either. It’s a bit mathy, but the math bits aren’t the hard part; I think it’s largely implementation, with one psychological hurdle where you have to realize that, because of how few distinct integers there are in S′, you can efficiently solve the subset-sum instances you need to produce the lexicographically earliest answer. I’m actually kind of impressed I got that. It seems like the sort of hurdle I usually get stuck on. How did this happen?

Maybe randomness. Maybe I was just particularly clear-minded during the round and wrote less buggy code than usual, because I had no expectation of making it whatsoever and so could look at the contest detachedly (until midway through the contest I accidentally noticed that my rank was under 20, and even then I tried very very hard not to think about it, and it kind of worked).

But it happened, and now I’m here. Time to roll.

In some emails much earlier in the Code Jam logistical process, Google had asked for “requests for changes and/or additions” to the software that would be installed on our competition computers, and I had sent them a long list:

Hi,
Here are some things I’d like if they were installed, in decreasing order of priority:

  1. The Vim plugin syntastic ( https://github.com/scrooloose/syntastic )
  2. a Haskell compiler (probably Haskell Platform 2014.2.0.0 https://www.haskell.org/platform/ even though it’s a year old)
  3. the Haskell package hdevtools ( https://hackage.haskell.org/package/hdevtools ) so that the above two may be integrated
  4. (I don’t have enough Linux experience to name a specific thing to install, but command-line utilities that are the equivalent of pbcopy and pbpaste on Mac OS X, which allow me to redirect text into or out of the clipboard from the command line easily)
Of course, this is my first Code Jam and I don’t know how reasonable these requests are. Any nontrivial subset would be appreciated.

Orthogonal Planes

I have a backlog of at least 6,000 words and still too many events to blog about, so these posts will not reflect things currently happening to me for a long, long time, except for the little blurbs on top of posts like this one when they exist.

Blogging is hard.

Also, I don’t have a good title.


It begins with an airplane.

[View of airplane wing and clouds from airplane]

For Zarquon’s sake, you’re entrusting me with my own passport and airline tickets and luggage and all this stuff I can’t even. I still layover people for months on end in Pocket Planes sometimes. (Watch the graceful descent of this reference into personally overused snowclone territory.)

Source: Taiwan, my home for the previous twelve years, which I am now bidding farewell to for the longest time in forever (…which is only (“only”?) five months, assuming I fly back for winter break as already planned). Destination: Seattle, for this year’s Google Code Jam World Finals, which I still don’t know how I managed to qualify for (more on that in later posts); and, before that, an accompanying interview for an internship that I scored as part of the bargain.

I successfully get on the plane, sort some nice things to have on hand into my MIT tote bag (how did I ever survive airplanes without keeping a tote bag on hand?), and put my backpack with the rest of my stuff into the overhead compartment. An old-ish guy who is probably Korean sits next to me. Plane takeoff is a bit delayed due to traffic congestion. Once during the flight, after an attendant passes out forms to everybody entering South Korea and I tell him I’m not, the guy asks me where I’m going and we have a short conversation. But for the most part, it’s typical airplane shenanigans. I listen to Avril Lavigne and Ellie Goulding, do a little homework, and eat the airplane food. Nothing remarkable happens.

Until near the end of the flight: a guy in a suit shows up in the aisle and, looking at some sort of checklist, calls my name.

[IOI 2014 Outtakes]

Miscellaneous observations that didn’t make it into a compelling narrative, sometimes because I have forgotten exactly when they happened, sometimes because I only remembered when they happened after blogging about it, sometimes because it just seemed too tangential, sometimes just because of the circumference of the mooooooooooooooooon! (That made no sense and I’m not going to remember what I’m alluding to in a few months.) During the first day a guy came into the secret computer room that the Taiwan team had concealed themselves in, saw us watching anime (SAO 2 among others), and innocently asked, “Are you the Japanese team?

[IOI 2014 Part 4] Shades of Xanthous

No, I didn’t forget. Not for one minute. I was doing homework. I am very happy because that means I was actually carrying out my priorities as I envisioned them. I’ve probably edited this post too many times, though. Meh. But it’s the first weekend after finishing summer homework, so here we go again!

Fun fact: This is by far my favorite post title in the entire series. Possibly in the entire history of this blog.


In the morning of the last day of official IOI activities, there were a bunch of cultural activities, e.g. writing Chinese characters calligraphically, doing tricks with the diabolo, or picking up beans with chopsticks, and noncultural activities, e.g. getting somebody to pour water into a cup on your head while he or she was blindfolded. Due to the last activity I got wet, but my shirt dried really quickly. And alas, even though I had taken calligraphy summer classes a long time ago, my calligraphy was awful — robotic, lifeless strokes without the right aesthetic proportions to make up for it. Blargh.

Anyway, lunch followed, and then it was time for the closing ceremony, in the same building as the other ceremonies and contests. Our team caught the ending song of in a Chinese musical being rehearsed as we walked into the auditorium. While we waited for everybody, we milled about waving flags that our various teachers had brought, including not only Taiwan’s flag but also flags of my school, thoughtfully brought by teachers who had volunteered. A little later our leader told us that all the leaders had discussed the matter during a meeting and decided that we shouldn’t bring any flags to the stage while receiving our medals, so we were going to have to make do with being patriotic and school-respecting off stage.

There were a few performances, including two aboriginal music performances and the musical we had seen rehearsed ealier, which was a fun rock musical rendition of some Chinese tale that seemed to have been sharply abridged, giving it the plot depth of a Wikipedia stub-article synopsis — a conflict, boy-meets-girl-and-falls-in-love, and a lamenting Aesop song conclusion with thrillingly vague general applicability. But the singing and counterpointing and atmosphere were good. I guess it was proportional to the relative importance of the performance to the closing ceremony. The program interleaved them with the long-awaited medal presentations: one round of bronze medalists, one round of silver, one round of gold.

Dum-dum-dum-dum, medals! The home team advantage was really obvious here; the cheering and the medal-presenter handshakes were both significantly more forceful for Taiwan’s medalists.

I think our leader made this. Thanks.
I think our leader made this. Thanks.

[IOI 2014 Part 2] One Line to Solve Them All

I started trying to sleep at 9 the night before the contest, tossed and turned in bed until 10, then fell asleep and got up at 3:35 in the morning. Blah. At that point, I went to the bathroom and applied some chapstick before trying to go back to sleep until 6. After breakfast, I grabbed a few minutes of sleep on the bus to the convention center where our contest would be, then slept on a sofa outside the actual contest hall alongside most of the rest of our team as we waited for a very long time until it was okay for us to enter. Competitions really mess with one’s sleep schedule.

Then, much too soon, we could enter. Day 1 of the contest was about to start.

The laptops were as yesterday, although they were protected with a white screensaver that indicated my name and ID as well as a countdown to the start of the contest. I was glad to see that my mousepad and all my writing utensils had survived without me. Somebody had the sense of humor to project an online stopwatch with an animated bomb fuse onto the screens to indicate the remaining time, which, once again, there was a lot of.

I conferred briefly with Paul (TZW (alphaveros (?))) about vim settings for a bit, but there were still fifteen minutes left or so. I idly stretched, practiced typing my .vimrc on an imaginary keyboard, and watched as the US dude two tables to my left unplugged his laptop’s mouse and rearranged absolutely everything on his table using the surface under his chair as swap space. (Well, that was how I mentally described it at the time, pending further revelations. (hint hint))

Then it began.

[IOI 2014 Part 1] Everything is More Exciting with Lightsabers

Okay, I guess it was really naïve of me to suppose that I could get any considerable amount of blogging done before the IOI ended. Onward…

We left off at the end of the practice session. As if somebody were taking revenge against us for not having to suffer through any airplane trips, we were served a cold airplane meal for lunch.

Seriously, the box had a sticker that noted its manufacturer as something something Air Kitchen and another translucent sticker that badly covered an inscription saying the same thing in much bigger letters. It contained a cold apple salad, a cold chicken bun, a cold flat plastic cylinder of orange juice, and a package of plastic utensils that was exactly like the utensils that came with every airplane meal ever. I was disappointed, but at least the salad tasted okay, and I ate an extra one because two of my teammates volunteered theirs.

To pass the time, we played an extra-evil ninety-nine variant. Apparently this is a very Taiwanese game because lots of student guides were teaching their teams the game, although our special cards differ from the ones Wikipedia lists in a lot of ways and our evil variant created more opportunity for sabotage and counter-sabotage and bluffing. 7s are used to draw your replacement card from somebody else’s hand, and that person cannot draw again and will have one less card; aces are used to swap your entire hand with somebody else, who also cannot draw a card; small-value cards can be combined to form special values (e.g. play a 2 and 5 for the effect of a 7) but after playing a combination you can only draw one replacement card; and later, to speed up the game, we added a rule where all 9s had to be unconditionally discarded without replacement but would still get shuffled back into the draw pile. Players lose if it’s their turn and they have no playable cards, including no cards at all.

While we were playing and repeatedly reveling in everybody ganging up to beat the winner from the last round, an instrumental version of “You Are My Sunshine” played on repeat in the background for literally the entire time. It wasn’t a very good version either. If you didn’t listen carefully for the fade-out and few seconds of silence at the end of each loop, you’d think that the loop was only one verse long. After the miserable excuse for lunch, we entered the place the opening ceremony, and an orchestra played a few songs that I can finally hope gave the contestants a feeling of Taiwanese culture. I recognized 「望春風」.

[IOI 2014 Part 0] Waiting

Yes, I know day 1 of the contest already ended and is probably a more interesting topic to blog about, but I finished writing this last night just before the internet was cut off to quarantine the contestants from the leaders, who received the problems and began translating them. I didn’t know about this until it was too late, which is why I’ve been waiting since yesterday to post this.

To provide a counterpoint to the last post, one of the many, many advantages of entering an international competition is that you get to meet a lot more people you already know, so there’s less time spent being socially awkward. While waiting for stuff to happen, aside from all the expected time spent with the Taiwan team, I also talked to, played games with, and otherwise entertained a whole lot of people I already knew, including my schoolmates (no less than fourteen of them were volunteers) and some of the college students who had shepherded us around during olympiad training.

Which is a good thing, too, because there was a lot of waiting.

First I waited for my teammates; my parents had decided to take me to the hotel (Fullon Shenkeng) directly, since I had a lot of stuff, and I had arrived early. This took about an hour, after which we had lunch. Then I waited for the hotel to give us our room cards, which took about five hours, after which we had dinner. Finally, at night, I waited for the Codeforces system tests. Very nerve-wracking. But I’m getting ahead of myself.

Rise from the Ashes

After the first stage of selection camp, I was very nervous because I was fifth place in a selection sequence that would finally result in a team of four.

I screwed myself over on the first mock test by committing to a bad implementation method on a problem that was hard to get points on. My method seemed simple, but the memory usage leaked out in a way that was confusing and hard to patch; unfortunately, I tried to patch it in increasingly desperate and convoluted ways rather than scrapping the method, and thus missed out on many of the points elsewhere.

During the second test I failed to read the last problem carefully and spent too much of my time on the second problem, once again missing out on a lot of relatively easy points. I had optimized and optimized and pushed my quadratic runtime down to linearithmic, which would allow me to get the points for the last subtask — or so I thought. But with 10 minutes left I had all but one testcase right, and after desperately rereading my code, I realized that I had a string comparison stuck in an inner loop that could make my runtime degenerate to quadratic if the input string had lots of the same digit. In order to have a solidly linearithmic algorithm, I would have to implement a suffix array. Ten minutes? I gave up. (The problem setters told me afterwards that hashing would have worked too; I didn’t think of that at all. Oops.) I spent the 10 minutes reading the last problem and still failed to read it carefully. So that did not go very well.

But, as the title probably gave away, during the third and fourth mock tests everything went much better than expected. :) There are two good reasons:

Adventures in Cabal Installations

First Google Code Jam!

The format of this competition, allowing us to run programs on our own machines, brought up a very interesting issue for me: what programming language should I be using? (I had had similar considerations for IPSC 2013, but GCJ’s problems are closer to the traditional ACM-ICPC style.)

The obvious choice is C++, the language I use for roughly every other competition, but its safety (or lack thereof) is not very appealing. I need speed, but not that much speed. Unfortunately I still haven’t gotten around to learning any other friendlier mid-level languages (on the list: D, Go, or Rust), so I have no close substitutes for C++ right now.

Python is certainly available for a reliable arbitrary-length integer type, if nothing else.

As for non-candidates, Java has BigInteger and memory safety, but all in all I decided the benefits are too minor and it’s too ugly without operator overloading. Scala is probably way too slow. So I don’t expect to be writing either language.

The only difficult choice I have to make is, of course, Haskell — which can be quite fast, even while it’s ridiculously type-safe and expressive and referentially transparent and easy to reason about, once you’ve:

  • figured out how to do the problem
  • scrapped step 1 and actually figured out how to do the problem functionally
  • gotten the thing to compile

Even if I can handle step 1, step 2 is by no means a simple task, as my struggle to implement a mere Sieve of Eratosthenes efficiently shows. That is fun, but not at all intuitive; I am doubtful I can do this under contest conditions. It is extremely difficult to transfer my skills in learning how to implement, say, a segment tree or treap into this language.

But! Google links to the programming language breakdown for 2010 Qualification Round as an example, and much to my surprise, Haskell ranks somewhere between sixth and tenth place in popularity (depending on what you sort by), so there are functional superprogrammers who can presumably do something like this.

As it happens, I ended up implementing all four solutions to the qualification rounds in Haskell, because of the relaxed time limit and lack of any involved algorithms and data structures. I think it was worth it.