The big day started with the usual breakfast, after which we have ourselves ready in the front of the contest hall. Spectators (coaches, RcD, and other guests) are to enter the room and be seated first (at the respective spectator seats). Before entering, as usual the teams are offered some pictures with the trophy (and Mr. Poucher too).
(A picture with the trophy - courtesy of DMT)
Last year we haven't got the chance to take the photo, but this year we had. After the spectators are seated, participanting teams enter the room accompanied with a long applause by the audienc (and some interesting music). Displayed readily on the projector screen is the infamous "Do not touch anything" quote by John Clevenger.
There was 11 problems in the world finals, numbered from A to K. Unfortunately we only solved 3 problems, out of the "supposedly solvable by us" of 5 or 6 problems. The problems can be viewed in the ICPC World Finals site or in the ICPC Live Archive.
Problem K - Steam Roller (AC)
This problem is supposedly a plain Dijkstra (or A*) kind of problem that is to be solved in O(N log N). However, my first try on the Dijkstra did not work (Wrong Answer) and I did not find the mistake. Thus, I decided to recode the problem from scratch into a more Dynamic Programming style (using plain multidimentional array as the memo) and got it right. Probably the mistake of the first one was on the memoization part (checking visited nodes).
The state for the Dijkstra is [Node, Direction, Speed] where there are 4 directions and 2 kind of speed (slow or fast).
Problem F - Glenbow Museum (AC)
After a couple of tries, Timotius and I concluded that the result will be the number of all valid permutations of R and O where there are 4 more Rs than Os and there is no Os adjacent to each other. That can be easily solved by the use of Dynamic Programming (had at least two or three mistakes before I got it correct though :( ).
Problem J - The Sky is the Limit (AC)
There was a similar problem to this one on the Bina Nusantara Programming Contest for College Students (if I'm not mistaken) written by Andoko Chandra. The problem by Andoko Chandra asked for the area of the mountain skyline while this problem asked for the length of the skyline itself. The solution is quite similar, we used the line intersection function from the team notebook and get it right on the first try.
Problem A - Air Conditioning Machinery (WA)
Problem H - Painter (WA or TLE)
My solution to this problem is to draw the tree of triangles (which triangle is contained within which triangle). But unfortunately it is too slow O(N^2) in the tree generation, and subsequent attempt to optimize it resulted in Wrong Answer. I did remembered about the scanline algorithm (of computer graphics) but haven't got the chance to implement it efficiently.
Problem B - Always an Integer (WA)
The solution I coded was to parse the polynomial into a vector of constants. Supposedly we can check whether the polynomial division always returned an integer by just plain bruteforce for integers up to the degree of the polynom (as pointed out by someone in Topcoder Forums). Our solution on the day was quite similar, but got Wrong Answer. Most likely the mistake is on the parsing process which is quite tricky (I used some kind of finite state automaton to parse it).
(We solved 3 problems)
By the end of the contest, we only solved 3 problems with several runs pending (all failed later on). After a simple lunch, we decided to go downtown again while waiting for the awards ceremony, to have another chance to buy more souvenirs (and spend the remaining Canadian Dollars). We attempted to visit Bow Falls but the way there was closed (due to the snow, I guess).
(One of my last photos of the exterior of the hotel)
We returned on time for the awards ceremony, during which we don't have much hope to get the top ranks (due to the few number of solved problems - just like last year). I did not take many photos during the awards ceremony and celebration, because I'm handing the videocam to record the whole events. You can see the photos by the Digital Media Team of the ICPC committee in their site. During the ceremony, several speeches were delivered, including by one of the IBM Fellow. A series of service award were given to some excellent coaches who have been coaching their ICPC teams for several years.
This year, they improved the nice scoreboard used since last year's world finals. It basically shows the replayed frozen last hour of the competition (during which the scoreboard was not updated). We can see several teams solved problems and getting lifted upward through the score board. Probably we should create one like this for our ACM ICPC Asian Regional - Jakarta Site contest :D .
This year, the team from St. Petersburg University of IT, Mechanics and Optics took the world champion trophy by solving 8 problems in 1187 minutes.
We solved 3 problems and was ranked 47th along with several other universities. Last year it was 44th out of 88 teams, this year is 47th out of 100 teams, so we only improve by a very insignificant amount :D .
After the awards ceremony, the dinner was served. During the dinner, IBM distributed the book Understanding DB2: Learning Visually with Examples for those who are interested. Mr. Michael Dang from IBM Canada was there to autograph the copies distributed. DB2 is the Relational Database product of IBM, which is said to have a great XML support built into it. DB2 9 Express-C is the free version available for download free of charge.
After the dinner, we are back to the Van Horne Ballroom to attend the celebration. Just like last year, it is an event organized by IBM, presenting several world class artists to provide some entertainment. There was a team of two jugglers who did the interesting stunt by throwing swords back and forth with Mr. John Clevenger in the middle of them (they promised the thrown sword "won't touch anything" :lol: ).
The other show a stage hypnosis show in which a hypnosis expert picks several persons from the audience to be brought on stage and hypnotized into a deep sleep. The expert then "programmed" them to do several funny things such as speaking some alien language and many others.
(Heavy snowfall outside)
As the celebration is over, the whole event is over. There was no more CyberCafe. It snowed heavily that night so I decided to take some last photos in Fairmont Banff Spring Hotel.
Continue to Day 6
(All photos are copyrighted, please ask for permission before reproducing)