End of Awesomeness

Well, IOI 2011 is over... That was pretty epic. This post will probably not be seen by many people. This is just final words. You know, IOI's a big thing. I just thought it deserved a post devoted solely to it's ending.

It's 11:25 pm now. We got on the plane from Thailand to Sydney, some time yesterday. We flew through the night with little sleep so yesterday, last night and today feels like a single day... or maybe it feels like three separate days. I can't really tell. Anyway, I got back from the flight from Sydney to Melbourne and slept from about 11/12 am till arounnd 10 pm. I don't think I can sleep any more so I'm just staying up for a few hours. My sleep cycle is so screwed up.

I feel sorry for Edgeworth. Essentially, 9 hours of his 14 hours of flying are redundant. He has to fly from Thailand to Sydney and then to Perth which forms a triangle. Yeah... I wouldn't like to be in his position.

I have mosquito bites all over my foot which I had to deal with all the way through both flights.

But despite all of this, I have to say, IOI was definitely worth it.

Many people only every have a brief touch of informatics. It's a great thing and I certainly think it has changed many lives for the better. Many people only ever go to a single December camp and I would think many competitors at the IOI only experience it once. Not only from Australia but from other countries as well. Not all countries are as good as China or USA. Many get to the IOI just because they can program and solve problems with some proficiency.

But all of them have a personality and a story and everyone, whether they're a legend or someone who just scraped a few points at the easiest problem, all of them have something to add to the community and some joy to give to others.

I think of AIO now, which I competed in now 10 months ago. I didn't even know what a BFS was and only a tiny amount, if any, about algorithms and complexity. I look back and think of how far I have come since then. I can't imagine what my life would be without informatics. I remember getting that email saying I was invited to December camp and how happy I was. Now I've gotten a medal at the IOI, the pinnacle that many have strived to achieve for years.

Now, having achieved this, I think of the December camp, the one where I began this journey and where I learned so much. Now, having reached this pinnacle, I look back and think of all the things I've learnt. The truth is, I believe I might not learn so much from December camp again but every year, I'm going to be there because every year, there is going to be someone new. Someone to bring something new to the group and every year, there's going to be a new group of people with their own quirks and references and personalities and stories. I want to be a part of that.

Informatics is about much more than the problem solving at the computer. It's about the jokes, the congregations around the computer watching videos, it's about the trolls, it's about playing minecraft in our free time, it's about screwing our fingers up playing table football, it's about staying up playing mafia and bartog. Because every moment is a new one and any moment could be the one that you end up missing. So every night, I stay up with the group as long as I can because I want to be there when it happens and I want to be part of that story.

It's 12:04 am now. I've spent around 40 minutes on this so I hope it shows you something and gives an insight or an inspiration to be part of that group and part of that story.

Everyone has a story, and I'm glad that informatics is part of mine.

Ohh... sparkly...

Yay! We all get medals! If you haven't seen already, the results are here: http://sc1.ioi2011.net/scoreboard/ (No, I don't know how to make links and everything on the browser here is in Thai). You can click on Australia on the right to only show Australian scores. If you look you can see I came last (of the Australians). Now look at Day 1 and Day 2 scores...

Yeah, I failed pretty hard on the first day. The three problems were known shorthand as Rice, Race and Garden (although for maximum confusion, it would have been way better to call Garden, Rose (Disclaimer: I didn't come up with that)).

The easiest one was Rice which I should have scored 100 on but only scored 68 on. I saw the easy 68 solution and thought, "Okay, I've gotten 68, that's pretty good... and the 100 solution is going to be really hard right? Because all IOI problems are really hard right?" So, yeah... 30 points lost there.

Garden was a graph problem which I may or may not have gotten the solution for. I spent 2 hours making observations about state explosion and cycles. Then I coded up half of it and started doubting myself because I really wasn't actually sure about the solution I'd thought up. So basically I wasted half an hour coding half of a possible solution. Then I decided to code the partial mark solution which was 49 points... but it didn't work! 49 points lost there.

The last one, Race was another graph problem involving a tree and finding the smallest number of edges summing to a certain distance. After the competition I heard Jarrah and Evgeny talking about the solution and realised it was similar to something I'd thought of in the competition. The thing was, I hadn't been thinking clearly at the time (because I was really annoyed at Garden) and hadn't given it much thought. In the end, I only coded the 9 point solution. Not that much of a loss since I doubt I could've gotten the solution anyway but some of the others got 21 points so... 12 points "lost" there I guess.

So, basically I failed the first day, missing out on what could have been another 90 points. I missed out on more points than I gained! So by the end of that I was feeling pretty... bad.

Luckily, I totally pwned on the second day.

The three problems were Parrots, Elephants and Crocodile.

Parrots was a task somewhat similar to a compression or encryption problem in that you had some data, had to "encrypt" it, and "decrypt" it. The thing is, the encrypted data, (a series of integers) could be sent to the decryptor in any order. I managed to get 81 points, Evgeny got the same and Eliot got 95.

Crocodile was another graph problem which required a few observations to reduce it to a kind of "reverse dijkstra". I got 100 along with Evgeny and Robert but (from what I heard) Eliot didn't realise he needed a priority queue so he only got the 46 partial marks.

We still can't figure out the solution to Elephants which we assume is a crazy data structure problem. This was an amusing problem in a few ways. Firstly, the problem had 5 subtasks but on the problem statement they were labelled, 1, 2, 2, 3, 3. Yay, duplicate subtasks. Also, the last two subtasks were worth, respectively, 47 points and 3 points. There was also a note in the problem statement saying something along the lines of "The c++ STL may be too slow to solve subtask 5". As Chris said, subtask 5 is there to separate Gennady and the Russians :). The other three got the 26 point subtask. Eliot told me he used the set solution which did a whole bunch of binary searches to "skip" stuff and make it faster. That was the theory anyway. It turned out to make the algorithm O(N^2 lg N) instead of the simple brute force which was O(N^2). I submitted the bruteforce expecting just 26 points but instead, I got 50!

The second day went much better than the first allowing me to scrape enough points for a medal. Well, I'm not sure if they've finalised the medal cutoffs yet but I certainly hope so.

Post-competition. Success?

(dissriguard spel czech, ackwire spel misteak)

Alright, so
I haven't had any time to post anything in a while due to a few things:
1. Dodgy internet.
2. The competition.
3. Dodgy internet.

Fortunately, it seems to be working now. Anyway, the competition itself:

Day 1.
One free mark/easy question: Ricehub -- A sliding window while keeping track of the median sort of thing. Tony Sun forgot the input was already sorted for you, so he implemented what he calls a "sliding heap" ಠ_ಠ.

Race: (for me) an ostensibly easy problem. Yeah. No. :\

And finally, Garden: Looked kind of complicated. Unfortunately I spent most of my time on Race instead of it.

I scored 158 on day 1, Evgeny scored 170, and Michael scored sub-100 (but he owned the second day really hard).

Day 2:
First the easy question (for me): Parrots. You have to encode a message such that you can decode it no matter the order of which your encoded message is delivered.

More importantly, question 1: Crocodile. This one was rather annoying for me. I coded up some random DP which got "fatal signal 11" on all subtasks. So I put my hand up and ask "wtf is fatal signal 11?" 10 minutes later: "Lol no we aren't going to tell you. Trololol." Feh.

And question 2: Elephants. I made a silly mistake which cost me about 20 marks. Sadface.

Notably, Michael Chen scored ~230 on this day (out of 300), while I scored 168, Evgeny scored 207 and Robert scored 178. Leaving us all with bronze medals, excepting Evgeny, who should get a silver.

The final scores were: Evgeny: 377, Robert: 316, Michael: 308, and me: 326.

After the competition we went to Pattaya city, where, (and this is the most important part) I bought a fan (not steven) (I actually have 4 now)! Incidentally there were also a couple of strip clubs. That is all.

Overdue post by the honorary IOI fanboy

Maybe I should post something... Here is a recount of the few last days of training and the arrivals day of the IOI.

Monday the 18th: Training Day 3

Nothing extraordinary happened at breakfast, again. The morning's exam was an interesting combination of a Dynamic Programming problem, a Combinatorics problem that wasn't actually combinatorics once you looked at it closely, and a really really interesting problem that turned out to have some extraordinarily elegant solution.

Informatics is somewhat of an art in ignoring common sense and making something trivial sound really, really weird:

"While you didn't have enough, keep substituting ceilings for floors until satisfied"

That, more or less, is a quote from the solution to the last problem.

I spent the rest of the night trying to salvage Robert's hard drive, but we had no luck in opening his laptop's cover. It is held in place by screws that will not budge under the pressure of skilful ruler-as-a-screwdriver application.

Tuesday the 19th: Training Day 4

Today we had a B-Session, a strange kind of an exam that is not really a true informatics exam.

On Sunday night, we were given a problem "Tree Mirroring" that we knew we would have to solve today. We spent a day or so thinking about it prior to walking into the tutorial room in the morning, ready to attack the question and hopefully solve it.

The process of solving it consisted of a few hours of discussion, after which we got enough observations and insights into the problem to solve it completely. We then went into the labs to code it up, and it took a far while for everyone to realise that we forgot a crucial part of the algorithm - something that will break things in quite a few ways. It is the same problem that I ran across during day 2 of the IOI - scroll down for the information on that.

I don't really remember what happened after that, so I'll skip immediately to the flight.

Thursday the 21st: The flight

After waking up really early in the morning to get our breakfast over and done with, and catch a cab to the airport, we once again found the breakfast place closed. We ended up packing our food in a paper bag and eating it on the way to the airport, inconspicuously, so that the cab driver won't see us at it :D

Before take-off, we flicked through the in-flight entertainment system's channels and found a camera that is attached to the bottom of the plane and effectively shows the runway in front of us. It was awesome.

I spent most of the flight watching movies (Sucker Punch, The Eagle, and something else that I can't remember - some family comedy), and sleeping in the last hour or so. Others did pretty much the same, with an addition of Tetris tournaments against each other.

After 9.5 hours of flight, we landed in Bangkok and caught a train to the hotel. My room was quite spacious with a surprisingly nice view on the front of the airport. Unlike last year, I did not run across any members of the Russian team in the hotel.

Night-time Thailand is exciting!

Friday the 22nd: Bus ride and arrivals

We caught a bus to Pattaya; the total ride was about 2 hours long. During that, there were 2 vaguely amusing things:

1. The nonogram puzzle on the IOI newsletter was invalid - we did it twice, getting the same result, and then Bernard told us that it is horribly broken. Oh well.
2. Thai KFC charge extra for "no ice" in your drink. Want to know why? Click here.

When we arrived to the Royal Cliff Beach Hotel, the place where we are staying, a glass of really nice cranberry juice was forced into my hands by really friendly and yet determined waiters. We soon left for our rooms, and then went down to meet other teams. There were quite a few people that I recognised from last 2 years, but there also were many new competitors who didn't have any idea of what was going on.

-- I will type up the rest of the IOI days later, I've been at this for an hour or so now.

Wake up!

Getting up today wasn’t all that easy, and the wake up call 10 minutes before the bus was leaving for the Nong Nooch gardens was quite a shock to the system. Fortunately Evgeny and I still had time to grab some bread for breakfast, so that was a triumph of perfect timing for sleeping in.

The Nong Nooch gardens were alright, the highlight was the elephant show where there were elephants trained to play soccer, basketball, paint, dance, and ride a tricycle.

I know jumping photos are kind of clichéd, but they’re still cool! This is our guide for the week, Wan. She’s the one responsible for all our 6:30am wakeup calls, and as bad as that sounds, they’re really appreciated and stop us sleeping in, so please keep them up!

Syndicated on my blog

Something approximating fun

Today was the first exam, and I’m reasonably happy with how I went. 138 out of a possible 300, which puts me a solid 18 points above the bronze medal cut off as it stands. So hopefully I can keep my ranking up and come away with a bronze medal on Tuesday.

I got off to a really slow start, 0 points after 2 and a quarter hours was rather disconcerting. After that I started scoring some points, which let me calm down a little.

Anyway I’m off, this laptop is annoying me and is liable to shut down randomly.

Syndicated on my blog

A singular confusing event

I go into quarantine rather soon and haven’t had much time to write this sorry. Quarantine is rather strict this year, we’re all confined to our rooms nd have our phones confiscated.

Also, I have no idea how this piece of paper came into my possession, I was just minding my own business in the practice competion and someone brought it to me. It’s a hard life.

Syndicated on my blog