Friday, April 13, 2007

Day 5 (March 15th) - The World Final and Awards Ceremony

Participants are not allowed to bring any electronic devices during the world final, therefore I did not take any picture during 5 hours of the contest. We woke up as usual, had a nice breakfast, and then gather in the front the Crystal ballroom. Some teams took picture with the trophy. The spectators entered the room first, and as participants we enter the room after all of the spectators have seated.

We went straight to our workstation (which is located at the last alley, next to the left wall), accompanied by the song "Get Ready for This" (instrumental version, if I remembered correctly). The balloon (grouped into colors, one color for each problem) was tied at the left and right walls.

(Photo taken by Mr. Raymondus Kosala)

There was three copies of the problemset prepared for each team, which makes it easier for us and avoided the need to disassemble the booklet (as we usually do even in the regional contest). I first focused on setting up the workstation (a Linux, Fedora Core 4). I created a shell script for compiling (well, actually only as a shortcut).

After working with the environment settings, I took my problemset booklet. I read problem A (well, still don't know why it is marked A+), and instantly decided that it was only an ad-hoc problem, and any bruteforce approach will suffice. Luckily I still remembered the blood-type genetics calculations from high school Biology, so I don't have to struggle to understand the problemset at all.

By the time I read problem A, Felix was having a conversation with Andoko and both of them decided that problem B is just a simple greedy problem. Felix coded immediately and we got our first balloon, and reached our best rank in the world final (4th, and never came anywhere near that anytime later). The balloon for problem B was a black one. Until now, I still don't know anything about problem B (never read the problem statement at all).

(Photo taken by Mr. Raymondus Kosala)

Because I believe in Felix that he will be the best to code such an ad-hoc solution for problem A, I explained the problem to him, which took some time (looks like he did not remember high school Biology as I do), but finally we get it right. He coded, submitted, and got a Wrong Answer. Soon after that, we found out that there was a problem with the code, he did not filter the output to unique bloodtypes only. He fixed it by modifying a function, submitted, and get another WA.

We were out of idea about what's wrong with problem A. By the time Felix coded problem A, I have already read the problem statement for problem G and understood it correctly the first time. Together with Andoko, who also read the problem at that time, we decided that it needs only a brute-force approach as the number of messages was only 5, because 5! is only 120. We just permute the order of messages to be processed and simulate the process, which will give us the maximum buffer usage. Choosing the minimum out of those combinations should give an optimal output.

Well, I debated for some time with Andoko about the way that the packets should be processed. It was about whether we have to finish one message at a time or not. But I found a word in the problem statement "consecutively" which means my first understanding was correct. Together we explained the algorithm to Felix, and he coded it. The first submission gave a Runtime Error. Felix fixed the code, which gives a WA. I checked the code and found that there is something wrong with Felix's code, he fixed it after that and still got another WA. At the end, we found out that Felix was coding an algorithm that is the opposite of what is correct. (Just like the one proposed by Andoko, that the messages may be processed together). Fixed that logic error gave us the second balloon (green).

We were quite frustrated given that problem A was the easiest (on par with B), but we did not solve it. We decided to test all combination of the input to Felix's code, and finally spotted the bug. Felix's modification (the addition of uniqueness filter) does not cover the single-output cases. In those cases, the program printed nothing. Fixing that one gave us our last balloon (blue - aqua).

(Photo taken by Mr. Raymondus Kosala)

It was about one hour left when we have the third problem accepted. We then go on trying to solve problem F and D. Problem D is quite simple but mathematical. I found the possible solution but haven't got the time to code it. It was about only about half an hour left left when I finished coding it and found some bugs, which was not fixed until the end of the contest. Felix, on the other hand, try to code problem F (which we decided to be solvable with simple exhaustive search or A* search but the states are complicated). He did not make it on time, and that was the end of the contest. We solved 3 out of 10 problems.

After the contest, we met with Ardian KP, Ainun, and Bramandia (the team from NTU, Singapore) who are all Indonesian (and all from Surabaya as well). They solved 2 problems and were struggling to solve problem G, F, and C (if I remember correctly). It turns out that they mistakenly understood the problem G. Their understanding was that the messages can be processed simultaneously, thanks to the "ambiguous" problem statement. We also met Sindunata, the winner of Topcoder Open 2006 Development, who is also an Indonesian. He happen to work in Tokyo for UBS.

We had our late lunch after it, since we did not eat much during the competition (and most of the contestants didn't either). After lunch, we met with another Indonesian, Raymond Rudy, Ph.D, who have lived in Japan for more than ten years and now work for IBM Tokyo Research Lab (which co-hosted the World Final). He told a lot of stories about life and work in Japan. After having such a long but interesting conversation with Ray, we returned to our room to have some rest and prepare for the Awards Ceremony.

In the Award Ceremony, we did not have much expectations other than seeing who is going to be the world champion (TsingHua, Warsaw, MIT, or any other). We was far left behind in the number of solved problem, and was announced to be at rank 44. That was about right in the middle, out of 88 competing teams.

The ceremony started with some awards given to peoples with remarkable contributions to the ICPC.

The Japanese Cherry Blossom Queen was present for the Awards Ceremony as well, accompanied by another lady, to help assist in the prize giving.

At last, the team from Warsaw University was announced as the world champion, solving 8 problems (the 8th was solved during the scoreboard freezetime, near the end of the competition). Comes second was the team from TsingHua University.

A very complete dinner was served after the Awards Ceremony. Some times after lunch, there was peoples singing in our room (which has karaoke equipments).

(Photo taken by Mr. Raymondus Kosala)

The celebration program was set up nicely to include several entertaining shows in the Crystal Ballroom. The first was a show of Japanese drums played with dance-like movements. (Unfortunately I don't know the name of the show)

Then comes the (world champion?) Chinese acrobatics team doing incredible acrobatic moves.

The host for the celebration program was also a very good in doing mind-games.

Perhaps the most interesting part was the appearance of the theatrical pickpocket, Bob Arno. He managed to steal a handful of watches from the peoples he talked to during his entrance from the back of the room to the front stage. He also taught something about how pickpockets work and perhaps how to avoid it.

After that, the Chinese acrobatics team performed again with different personnel.

There was also a professional juggler (forgot his name..., the fastest juggler in the world?). He can even play a keyboard with balls, and plays it nicely too...

And the last was another Chinese acrobat.

Some deserts were served after the celebration. It had been a long day, but at least, it ended up nicely with a lot of fun.

Continue to Day 6


(All photos are copyrighted, please ask for permission before reproducing)


mahli said...

ainun, bukan ainu :P ainu itu suku asli orang jepang :P

Kurniady said...

Ups, sorry :) mistype... already corrected now. Thanks.