Felix Halim .NET: ICPC World Finals 2007 Day 4, Awards ceremony, and Surprise event

Today is the contest day. After the breakfast, Bill Poucher wandered around talking with the teams bringing the ACM ICPC Trophy with him. Many teams got chance to take picture with him and the Trophy as a "fake" champion. The spectators were invited to enter to the contest room at the back stage and then Bill Poucher invited all the team to enter the contest room with him. The background music that surrounds the contest room was very good (I don't know the title of the music, can anyone tell me?)

These pics were taken by our coach (which categorized as spectators)
There were a good music played in the background

Bill Poucher and Shingo Takada then officially start the ACM ICPC World Final 2007

As usual, Kurniady starts by preparing the computers with "batch" files to automate the compiling and testing because he is who understand the linux environment the most. The settings were more or less the same with one in Taiwan, very convenient. Andoko and I start reading the problem statements. There are 10 (A to J) problems presented in this World Final. The complete problem set can be downloaded here.

First accepted Problem B - Containers (24 Minutes)

I don't know why, when I first read this problem I didn't quite get the problem statement meaning. I asked Andoko to explain the problem statement to me according to his understanding. Don't know why, every time he finished his explanation (and I asked some cases to verify my understanding) I almost always want to code it right away.

This is the simplified problem statement: Given a word on a line consist of N (0 < N < 1001) letters (A..Z). One by one, we have to put these letters into M stacks with a constraint: if the stack is not empty, the letter inserted into that stack can only be smaller than or equal to the top of that stack. The question is: What is the minimum value of M?

I came up with a greedy + binary search algorithm for this problem: Binary search the M, and greedily test the solution. The greedy test is like this: if you have M stacks and you have to put a letter into one of these M stacks, choose the stack which its top has the closest value with the letter otherwise you will lose something.

Andoko doubt that this method will work, but I coded and submitted it anyway and got it Accepted, Yayy! I looked at the standings, we got 4th rank! Hmm.. a good start!

The ranklist showed that we were ranked 6. There must be 2 teams got two accepted problem this time, what a fast competition
Our yesterday's picture at the practice session showed up whenever we solved a problem (the same with other teams)

Second accepted Problem G - Network (209 Minutes)

Wow.. 185 Minutes idle?!? (its 185 minutes elapsed since problem B got accepted).

I really was having a bad day here! The problem was tricky because there is a word in a problem statement that easy to miss. The word is "consecutive". This generates a lot of discussion between Kurniady and Andoko.

The problem statement is this: There are N (1<=N<=5) messages numbered 1 to N to be sent over network. The N messages were split into M packets. Each packet is labeled with packet ID (which is the message number itself), the starting byte and the ending byte position for the packet. You are given the total size of each of the N messages, and the arrival order of the M packets. You have to determine the minimum size of the buffer needed in order to reconstruct the message. Any packet can go into the buffer and leave in any order.

Somewhere in the problem statement, there is a tiny word "consecutive" which means if you are currently constructing message number 3, you cannot in the same time constructing other messages! The other messages must go into the buffer. If only the word "consecutive" doesn't exist, it would make the problem much simpler (and we doubt that World Finals problem should be that easy): it become a simulation problem.

Because of the "consecutive" constraint, we need to permutate the order of the messages get constructed (5! possible permutation). Still, the problem was very easy (just brute-force). But since I was having a bad day, I got Runtime Error for the first submission (it was because of totally logic error and therefore wrong code). The second submission on this problem, I got Wrong Answer because of the logic error again (my algorithm didn't follow the "consecutive" constraint). At last, the third time after Andoko made several test cases and verified the answer, it got Accepted.

That's why it take 185 minutes! It appeared not only our team having this kind of problem, many teams didn't see the "consecutive" word (by the time they realize it, they need to re-code everything). See this TopCoder Thread for that discussion.

In the mean time, many teams already got accepted 3 to 4 problems

Third accepted Problem A+ - Consanguine Calculations (229 Minutes)

Wow, only 20 minutes elapsed, we got this problem accepted!?! Nope... Actually this problem has the worst story. We need 4 submissions to get it Accepted. Let me describe the silliness one by one.

The simplified problem statement: Given two parents' "ABO Blood Type" (A, B, AB, O) and Rh factor (+, -), determine their children's possible Blood Type and Rh Factor. Whattt?!? it's just another brute-force problem! Of course with added difficulties: you may be given one parent and his child Blood Type and Rh Factor, determine the other parent's Blood Type and Rh Factor. And also, there is some "nasty" (as misof often said) conversion between the Blood Type and the actual combination (A means AA and AO, B means BB and BO, Rh + means ++ and +-). We have to carefully convert the one to many combinations of the Blood Type when reading the input and convert it again from many to one when outputting the Blood Type and Rh factors.

I coded this problem somewhere between the frustrations of RTE and WA of problem G above, hence made me a little paranoid (I should've delegate this coding to Andoko!). So, my fear come true, we got WA for the first submission for this problem. It takes a long time to figure out the bug, since the code is really long! (I should've coded it in Ruby: no code, no error! and make me smarter than I think I am). Then after sometime, we found the bug: I forgot to convert the many to one for the output! Actually I was not forget, but the remove duplicates must be done twice: remove combinations duplicates and after convert it to Blood Types remove the duplicates again (I miss this second step). However, we still got WA! At this time, all of us became paranoid! We started making delusions! We thought the "sentinel" is wrongly handled: the "E N D" could be "E E E" or "E D N" or any thing... so we fix that and actually resubmit it \LOL. Of course this will get another WA :P but we have to make sure :D (entering "WA gak bayar mode").

Just after we got problem G accepted, Andoko instruct me to generate all possible input and print the output. He intended to check it one by one. Not long after I generate the input and run it, there appears the bug: The children's Blood Type is EMPTY! Hore, found the bug! The bug is there because of the second fix I made (the remove duplicate things). I forgot to update the code for a single Blood Type, what a silly and unnecessary mistake!.

The current standing: Our team got 49th rank with 3 solved problems
And the statistics for each problems also shown

There was about 71 minutes left (the contest were 5 hours). We attempt to solve 2 more problems (Problem F and C) and it seemed to be not a good idea since the time left were too short. If only everything went well on the first 3 problems, maybe I can get problem F accepted. Since it only need complete-search (A*) algorithm to solve it and I've solved many kinds of problem like that before. The "nasty" things about these world finals problem set is that it requires you to do a lot of coding but the algorithm itself is just brute-force, greedy, complete-search. I'm disappointed with the problem set.

Then the contest ends. By the time the contest ends, I really disappointed with the result. We should've done better than this! In the same TopCoder Thread I mentioned before, there were some teams also have disappointments with the "taste" of the problem sets.

Only 3 balloons :(
ardiankp's team approached us for explanation of problem G
Andoko told every scientific process he had with Kurniady to solve problem G
The culprit is the word "consecutive"

After the contest ends, we met sindu (the Indonesian TopCoder) at the outside of the competition room. Thanks sindu for coming :) Also in the afternoon we met Rudy Raymond Harry, Indonesian that works for IBM Research Tokyo. We discussed how life at IBM Research is.

Around 5PM, the contest results were up and we assembled in the competition room again for the Awards Ceremony.

The Judges decides the cut-off line for the ranks based on the number of solved problems and time. See my previous blog post for the contest results. The Top 12 teams were called on to the podium to receive awards. The photos of each 12 teams can be found in baylor site

Warsaw University got the World Champion! Congratulations!

After the Award Ceremony we had dinner.
Ainun Najib participate in singing during dinner (Left).
Crowds sang Y.M.C.A (Right)

Bill Poucher also sang and then invited us all to the Surprise event. The surprise event was Chinese Acrobatic performances, Pickpocket Entertainer Lecturer, Bob Arno, Piano Playing Jugglers, Wally Eastwood, and another Chinese Acrobatic performance.

The IBM's Celebration, the surprise event, opened with drum performance

The first performance is Chinese World Class Acrobatics

The second is Pickpocket Entertainer Lecturer Bob Arno
See the part of his action below

Whose "Cheap" watches are these belong to?!? You go to IBM using these watches!?!

I'm just warming up here!

Are you missing your wallet? (after went off the stage, he didn't realize that his tie was stolen)

Ok, whose underwear should I steal?

Bob Arno: "Relax, I won't TOUCH anything."
This is funny because John Clevenger said this repeatedly in practice session: "Do not TOUCH anything!".
Hearing Bob Arno saying "I won't TOUCH anything" made the audience laughing hard. It's just clicks!