Friday, 22 August 2014

International Olympiad in Informatics 2014 - Medal Time

This year marked my third and final trip to IOI, and after a hairy finish in our national training camp, the AIPO, I was off to Taipei, Taiwan, to compete in the 26th International Olympiad in Informatics.

This year, our team was back to four, myself, Daniel Mulcahy, Áron Hoffman and Conor Griffin along with our leaders, Gary Conway and Ximo Planells, and after much training at the national camp held in DCU, we felt ready. Leaving Dublin in the afternoon, we arrived in Taipei after a stop in Dubai. Pretty tired and ready to get going, we waited for a while in the immigration queue, an over-eager immigration officer just dying to spend nearly half an hour trawling over each of our pretty European passports with a magnifying glass. On the bright side, he stamped them really neatly.

The first thing to hit us as we arrived in Taiwan at dusk was the humidity and heat. I've never experienced it before, although I was rightly warned beforehand that there was near 100% humidity and it was around 30 degrees Celsius. After some interesting interactions with a bus coordinator, and taxi drivers, along with getting stared at by everyone (a pattern which was soon to repeat itself, all the time, everywhere we went), we arrived at our hotel. After a delicious expedition to a local noodle bar, a night's sleep and an oddly western-fusion breakfast at the hotel, we were picked up by the IOI bus, meeting old friends already on the bus.

They had these signs everywhere in the zoo,
featuring such lines like: "zoo poo poo"
We arrived and met our guide, the ever-informative and lovely Serphina, and our equally-nice second (sort of) guide Rosie (we're important enough to have two). After this, we took a trip to Taipei Zoo for the day, which was conveniently just down the road. Even in the face of intense heat and humidity, backed up by our complete inexperience of dealing with such things, the zoo turned out to be quite enjoyable. That night was an games night/talent show, which was incredibly fun.

On Monday, we got up early enough and headed off to the Taipei International Convention Center, the TICC, this is where the competition was to take place. We had a laid back practice session, followed by lunch, and as per usual, an impressive opening ceremony. Of course that night took us to quarantine before the competition, unable to communicate with our leaders as they translated the task statements for the next day (or rather "translated" the statements in our case).

Us, aptly freaking out in an electronics mall
The first competition day began on Tuesday. We had to get up at an ungodly hour, which we'd have to do again and again later on in the week, and as with most IOIs, there was waiting around, but fortunately at this IOI, there were absolutely no delays! Getting into the competition hall, we got ready, split up and I sat there taunt with the tension, staring at the envelope containing the task statements, waiting to open them once the countdown hit zero. After that magnificent moment with the sound of hundreds of contestants opening their task statements for the first time, I was in.
Rail proved to be difficult to master, but I managed to net 30 points by the first hour with a naïve solution. After that, I set into the Wall problem, knowing a possible solution was based on segment trees, something I had practised for this year.

Sunset from the top of the Taipei 101
Everything was looking pretty grim hours later, with only half an hour left an absolutely no more points on the board. A buggy implementation left me only having a submission at the 4:30 mark. All my hopes riding on this, it came up squat, or well 8 points. Not so good. Having spent nearly three and a half hours solely on wall, I feared I had messed up big time, but I could give, abandon my progress on Wall and start on the third problem, Game, which I had no idea how to start. Soldiering on with Wall, in fifteen minutes I had added three lines (yes three lines!) which catapulted me up to a perfect score, a full 100 points. I was shaking.

I actually got an action shot this year! Success!
Now with fifteen minutes left, in a state of nervous, adrenaline-filled euphoria, I read the Game task statement, for the second time. Like some miracle, the solution clicked instantly. It was a disjoint set and connectivity of a graph question. I thought I had an idea for a full score solution, but with only five minutes left to go, I had no time, and opted to code a clever brute force solution, using recursive flood fill to check the connectivity of the graph. Having coded nearly this exact same code hundreds of times before, with just minutes seconds left in the competition, I tested with the sample test data, nearly audibly celebrated when then came up correct on the first test run, and submitted. The competition ended before getting the submission result.

Coming out the hall, I was met by our leaders, delighted at my score, and even more so when I asked them to check it again. My last minute solution garnered 42 points, unbelievable. With this, I was in low silver position, far above the bronze I had hoped for this year. That evening we had a banquet with the mayor of Taipei, the whole time I was delighted and ever so thankful that I had done exactly what I had done in those last 30 minutes, not become disheartened.

The next day, Wednesday, we had another early morning start to travel to the National Center for Traditional Arts (left), followed by the LanYang Museum, a trip which took us through the Hsuehshan Tunnel, at 13km, Taiwan's longest tunnel. Both of our stops were very fun, and also incredibly scenic, the National Center for Traditional Arts styled like an old-fashioned village, with many shops and crafts that we could take part in. It was by now our team had established itself as the "Sticker Team", throwing stickers onto unsuspecting countries' signs during the day, most notably our valiant but ultimately doomed effort to cinch the American sign (or rather many efforts, continuing throughout the week).

Competition day two was not half as exciting for me as day one had been. After deciding to start into the Holiday task, as I had seen similar before, I only had 7 points by the first hour. Abandoning this for the the much more approachable-looking and interesting Gondola task, I had netted 55 more points in another hour. Not immediately seeing a clear way to get more points in Gondola, and feeling like I had squeezed a fair few points out of it already, I started into Friends, which I was sure I could get a number of subtasks done with a graph-based solution. Alas, after fiddling around with a buggy solution for over an hour, I gave up. With an nearly two hours left to go, I set into Holiday once more and managed to push my score in that from 7 up to 30 points. The last minutes of the competition were spent submitting Friends, which unsurprisingly didn't work, and trying to understand why a subtask worth 17 points in Holiday was not grading correctly, when in theory it should have. The answer became clear in analysis mode later on: A cout debugging statement left in the solution. Facepalm.

Not that it particularly mattered anyway, those extra points would not have pushed me back up to silver, and I was overjoyed when my leaders came in after the competition with the scoreboard, now knowing I had a definite bronze medal. That evening we went to the Taipei 101, one of the tallest skyscrapers in the world, and got to head the top observatory, in the fastest elevators in the world. The view was breathtaking and the food in the 101 food court was delicious to boot.

Now that the competition was over, everyone happily enjoyed the rest of the week, and were sad at the thought of leaving. We spent the next day at the Lihpaoland Amusement Park, mostly in the water park, due to the heat, and even through the odd rain shower, we had a great time. The day finished in a huge banquet at the hotel beside the park. I ate a lot of food, like, a lot.

And then, as quick as that, our week was practically over, with the closing ceremony and farewell party on Saturday. The party was fun, held at a local university. As always at IOI, the final day of departure, Sunday, was a tad gloomy. Everyone was sad to leave. I was sad that this would be my last IOI, thinking back over these last three years, I was extremely lucky to go to any, let alone three separate IOIs. The experiences were great, the guides, constants and now friends were the best, and Taiwan was no exception. I wish I could have gotten to see more of Taiwan, it is a great country and if their IOI is representative of anything, extremely fun.

Thanks to everyone who made the IOI what it was this year, and good luck to the Irish team next year in Kazakhstan!


Post a Comment