Thursday 4 October 2012

Late but not never

Well, late is better than never right?... <silence> well, let's get on with it then.

On day 1 we had (pebbling) odometer, (parachute) rings and (crayfish) scrivener.

Odometer was really weird. The most amazing thing is... Gennady didn't solve it!... that's right! Gennady didn't solve pebbling odometer!! Don't believe me? Well here's the IOI results. Still don't believe me? I don't believe it either. But on to the actual problem.

In odometer you were given a whole new programming language to control a robot in a grid. The grid consisted of a bunch of squares each with a number of pebbles in it. You had to do a number of tasks on the grid such as putting the robot in the middle square of two pebbles or putting the robot in the square with the minimum number of pebbles. The crazy thing is that since this is a whole knew programming language, you don't have memory! You don't have variables! All you know is where you are in your program. It's pretty crazy which is the only reason (I think) Gennady didn't solve it. Me, junkbot and goldy got the first two subtasks giving us 21 points while nic got subtasks 1 and 3 giving him 28 points.

The second problem was rings. You are given a bunch of rings which can be connected. We define a chain as one or more rings that forms a single non-cyclic path. We also define a critical ring to a be a ring which you can remove such that the remaining rings are chains, not necessarily all in one chain but a set of chains. You want to support two operations, connecting two rings and finding the number of critical rings. Basically, it was a whole bunch of icky and tripsy data structure foobar... that's all the detail I can go into in a blog. :/
Me and goldy got the first subtask giving us 20 while junkbot got 55.

The final problem was scrivener. You had to implement a machine which could type a character or undo the last x operations. The trick was that an undo counts as an operation in itself and undoing an undo would redo  all the undone operations... yeah, tricky. [SPOILER] After a few observations, you realised that you could turn the operations into a tree and use logarithmic parent lookup, similar to that in lowest common ancestor algorithms. [/SPOILER] Me, nic and junkbot got 100 on this and goldy got 60.

Tuesday 2 October 2012

Home!

Sun 30 Sep - Mon 1 Oct
Following a rushed packing and breakfast, we jumped onto the bus at 0730 for a 2 hour ride to Malpensa Airport (Milan). Most people slept, others talked (I caught up on NCIS). We boarded our flight to Abu Dhabi. Upon arrival, we were told that our following flight was delayed by an hour. This was not a problem, however, as we had free WiFi. After another 14 hours, we were back home in Sydney and met with family.

It was a fun IOI. On the whole, it was a great experience. For Goldy, Nic and I, it feels as if we've been training for 3 years to get to this stage, so it is a happy/sad feeling of it all being over. We've made some great friends at the IOI some that we may keep for a very long time.

I'd like to thank everyone who has supported us (friends, family and tutors), especially Jarrah and Chris, our team leaders, for a sensational experience over the last 2 weeks, both training and competing. It certainly has taken up much of their time (and their sleep) and for this I am ever-grateful.

We now look forward to the year ahead. The AIO is over, and results are yet to be released (pinging bgbn). It will be a long and hard process once again, but for many of us in Australian Informatics programme, we will aspire to qualify to represent Australia at the next IOI in Brisbane.

If you are reading this blog, and have an interest in computing and/or want to get into informatics contact either Jarrah or Chris or our (unofficial) IRC channel (#aioc on irc.freenode.net) and we'll try and get you involved. It's a life changing experience and definitely worthwhile. I will never, ever, ever forget or regret doing informatics. And hopefully, you never will too.

The Close

Sat 28 Sep
Getting to sleep in to the relatively late time of 0730 was great. Following a luxuriously slow breakfast, we headed out in the rain to the buses towards Sirmione. Wondering around the town, we bought souvenirs, got more vouchers, more noms and more gelato. Despite the rain, the walk down to the beach made for some great photos.

Following lunch back at the village, we were told that due to the rain, they could not hold the closing ceremony outside in Sirmione (as originally planned) but instead we crammed into a small local hall. The band that played were amazing. After receiving medals, and the guides' spontaneous singing of the (Italian) national anthem we ran in the rain to queue up for more buses, eventually heading back to the village for the farewell dinner, followed by playing cards late into the night with the Brits and the Kiwis.

Venice: Spectacular Sights and Long Lines

Fri 28 Sep
Waking up before 0500 isn't usually pleasant. But it is if you're heading to Venice for the day! We boarded bus, train and boat before reaching St Mark's Basilica - the most famous sight in Venice. The architecture and ceiling paintings were amazing. We wondered around the town, managing to get food at a cafe and trying to sit down outside it. However, we were met with menus (the Coke was 9.80 euros) and angry waiters telling us we weren't allowed to sit there. After a wait, we were invited into another cathedral where we were given its history. After a (relatively) short walk, we were met with long, long lines to queue up for what we thought was lunch. However, it turned out that a bridge was broken, and we could not walk to our lunch venue (inside the Arsenale - a Navy yard) but instead had to queue up for a 3 minute boat ride.

Upon arrival, we were met with more walking and more queueing before being served lunch, to our relief. Following this, we heard more speeches, before heading back on the boats then the train then the bus back to the Village.

Contest Day2: Bitter and Sweet

Thu 27 Sep
The contest was very hard today. I was stuck on 0 for 2.5 hours, before giving in a deciding to code the partials. Immediately after the exam, I thought I'd done poorly, but rushing out to the TV screens (with the scrolling scoreboards), I was told by Jarrah that I'd actually done great (relatively) and that Australia had bagged a silver and 2 bronzes (with Goldy just over the bronze medal cutoff)! (sweet) We were all sad, however, that Nic narrowly missed a bronze but less than a measly 20 points (bitter). Heading back to the village I got in some exercise with Ping Pong and Tennis, before noms and sleeps. 

Contest Day1: Stress, Excitement, Fun!


Tue 25 Sep
This is the earliest I have woken myself up (0530). Ever. It is insanely dark outside. There are stars outside. We have to be up this early because the buses to Montichiari for the first contest day depart at 0700. Or so we thought. Following breakfast and boarding the buses, the tyres did not move until 0800, and, with a police escort, we arrived there by 0830. Entering the contest hall at 0915, we were told that the contest would only start at 0930, leaving us wondering for 15 minutes why we couldn't have got up later. At 0930, the contest started. Well, for most people. I was hit with a series of 500 Internal Server Error messages for 3 minutes, much to my frustration. Australia ended up doing great as a team, with everyone well above the medal cutoffs so far. We shall see how we go on Day2 (Thursday). Despite the technical difficulties, the contest was made awesome by the large bags of lunch delivered to our desks by the friendly guides, which was an unexpected pleasantry.

Having no appeals, we boarded the buses back to the village. While the rest of my team decided to swim in the lake, I preferred to stay on land and headed out with Jamie (the NZ deputy) to the soccer pitch where we met some other nations' teams. I learned that at the IOI, Eastern European countries only care about two things: Informatics and Football. Teaming up with the Danish team, we managed not to score a goal in all 4 matches that we played, but was still fun. We headed over to the tennis courts, and met up with a Malaysian representative, finding out that this is the first IOI that Malaysia has competed in. Upon arrival at the dining hall, I discovered my team were ever-curious about my whereabouts. They'd been playing bartog with team NZ, which we continued with Logan after dinner.

Meeting Montichiari


Mon 24 Sep
Woke up early this morning for the buses departing at 0730 for Montichiari (the site of the contest). After a reasonably long wait both at the buses, and at the venue, proceedings began at the Opening Ceremony. The opening bell was tolled and "the games" (that's what the guides are calling it) began (may the odds ever be in your favour). Following this, lunch was served in the foyer. The welcome video was played on the big screen no less than 50 times during that day and the next (so much that we memorised every word and the theme song which we have now deemed worse than Etihad's).

After lunch, we entered the contest hall for the first time for the practise contest. We tried to "break" the judging machine in every way (whilst still abiding by the rules) in order to prepare and accustom ourselves to the system (and its quirks) on which we will compete tomorrow. Heading back and eating dinner, we headed off straight to bed, sleeping no later than 2100 - the start of the quarantine (they took our phones).