Monday, July 7, 2008

Day 5 (April 9th) - ACM ICPC World Finals, Awards, and Celebration

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)

Kenny coded for this problem since the first two hours using some kind of BFS approach. He submitted and got Wrong Answer. At around the fourth hours, we found out that his solution did not forbid the ducts from intersecting with each other. The problem was supposedly solvable by simple DFS (the state is not so many)  and simply trying all the possible combinations. Memoization cannot be used (and not needed anyway) since the duct configuration in terms of used cells is quite big and cannot be memoized efficiently.

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).

(Contest finished with Balloons everywhere)

(A team photo with Mr. C.J. Hwang)

(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).

(The frozen river)

(A romantic riverside walk)

(Somebody riding a horse passed by)

(Another visit to downtown Banff)

(A nice afternoon sunlight on the river)

(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

-Andrian Kurniady

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


Andrian Kurniady’s Blog » ACM ICPC World Finals 2008 - Banff, Canada said...

[...] Day 5 (April 9th) - ACM ICPC World Finals, Awards, and Celebration [...]

Andrian Kurniady’s Blog » Day 4 (April 8th) - Opening Ceremony, Practice Session, Gondola Ride, and Downtown Banff said...

[...] Continue to Day 5 [...]

flanflygirl said...

... "I want to read that DB2 book..."
anw, too bad we didn't improve much... but congratz for reaching world final twice.. (uda kayak gitu, pulang gak bawa oleh2 lagi. ckckck.. mengecewakan)

Andrés Mejía said...

Hello Andrian, can you tell me what's the dynamic programing state to solve problem F - Glenbow Museum?

I tried dp[i][j][k] = number of strings of length i having exactly j R's and finishing in O if K == 1, or finishing in R if K == 0.

This state gives me Wrong Answer, because it counts strings that start and end both with O, for example: ORRRRO.

Thanks for the help, and take care.

Kurniady said...

For the Glenbow Museum... I think the observations is that you would want

Total number of R - total number of O = 4, and there are no two Os in a consecutive position (let's call this diff)

I think I used dpmat[length][diff][last], where last is either R or O. I found the same problem with you, but that can be solved with a bit of trick, which is to run the DP a few times :
- Assume the first character is O, then we do init with dpmat[1][-1][O] = 1, and we collect the answer in dpmat[length][4][R] (you cannot have two Os both in the beginning and the end right :D but OR is okay)
- Assume the first character is R, then we do init with dpmat[1][1][R] = 1, and we collect the answer in dpmat[length][4][R] AND dpmat[length][4][O] (RO and RR is fine, right? :D )

Well while looping for the DP you should consider NOT adding cases for OO, otherwise it would be fine. (I think you get this one already).


Andrés Mejía said...

Hello Andrian,

Thanks for your answer. I noticed there's an even easier way to find the final answer without running the DP twice.

Notice that for each valid string starting in R and ending in O, there's also a valid string starting in O and ending in R (For example, by reversing it).

If we use the state dpmat[length][diff][last] what I do is initialize dpmat[1][1][R] = 1 (Assume ALL strings start with R) and the final answer will be dpmat[length][4][R] + 2*dpmat[length][4][O]. That is, first count the strings that start and end in R. Then count the string that start in R and end in 0 and for each one of these strings count its paired "brother" string that starts in O and ends in R.

-Andrés Mejía

Kurniady said...

That's a good observation, I haven't noticed that back then. Well actually I was solving a harder problem like a few weeks before the world final, in which there's more types of characters (e.g. A B C D... up till n kinds) with my trick (multiple runs)... your way will reduce the number of runs into a half, which is quite nice.

Therefore on the world final I instantly remembered that trick and solved it without considering any optimizations (just copy pasted the code hehe...)


Bookmarks about Acm said...

[...] - bookmarked by 5 members originally found by sakkigi on 2008-09-12 Day 5 (April 9th) - ACM ICPC World Finals, Awards, and Celebration - [...]

Lorencohof said...

I need to contact site admin urgently. Can you understand me?
Thank you

Simone said...

Problem F - Glenbow Museum (AC)
Hi Adrian, i don't understand exactly the solution of problem F, i understand that there are are 4 more Rs than Os but i don't understand if you have used permutations or combinations.
Sorry for my bad english
Simone Santarelli