Sunday, December 30, 2007

Day 4 (November 25th) - Contest and Awards Ceremony

The "big" day started with a humble breakfast provided in the Teacher's Hostel. It was a traditional Taiwanese breakfast. We were then transported to the university and prepare for the actual contest.

To our surprise, there was a camcorder (used for live webcast of the competition) right in the front of our seats. The contest started without much problem, and soon we are working on the problem set.

I started preparing the environment right after the contest begins. I then started to look on the problems, and soon marked the problems with the solution type. I found one problem which looks like min-cost-max-flow, another one using DP, and another one using geometry+graph.

Timotius started with coding for problem B "Simulation of Life" which is just a plain simulation of the game Life (famous in studies about cellular automata). He got a runtime error for the first submission, but then he fixed it and got a WA (actually, I re-read the problem statement and mentioned about how his solution slightly differs from it before the WA solution). He fixed it again and got another WA. At last, by "misinterpreting" the problem statement, he finally managed to get Accepted. This is weird, since the fix he made was supposedly equivalent to the previous codes. But, it's the first balloon anyway, so we moved on.

When Timo was coding, I spotted that many teams got Accepted for problem A "Miss Kitty and Her Little Ice Cream Shop", and I then guessed that it is just another ad-hoc problem. I coded and got a Wrong Answer (well, actually my code does not even passed the sample case, but I submitted anyway). Several minutes of debugging found that the problem come from using the same variable name twice for different purposes. Fixed that, we got another Accepted run.

I proceed to code for problem H "Maze for Robots" afterwards, which is basically just a Deterministic Finite Automaton simulation, coupled with Dynamic Programming. Got it right on the first try.

I actually hoped that this problem to be a bit harder, for example by setting the limit of N up to 2 billion where simple Dynamic Programming won't suffice, if not coupled with matrix multiplication speed-up trick. Therefore, less teams will solve it :P .

While I was struggling with problem H, Timo scratched his solution on problem I "Eventown problem". However, the solution did not run on time even for the test he made, therefore he added some trick to have the solution "approximated" which is Accepted when he submitted.

Problem C "Undetectable Tour" is actually quite the same with a problem in Topcoder SRM, 500 points in Division 1 sometimes back that I have solved. It is basically a geometry+graph problem. The first two submissions was judged WA. I suspected that it is a TLE and add some optimization, and it proves to be correct, as it got Accepted on the third try.

For problem D, "Uggla Mission", I originally coded with angles (using atan2). The first solution got a Wrong Answer, and thus I modified it into using vectors instead (probably some precision errors) and still got a Wrong Answer. Finally I suspected it to be a TLE as well, and added a keyword "inline" to a function to speed things up, and that proves to be correct as it got Accepted (our last balloon for the day). Right after that, we reached the 2nd position on the ranklist, which moves to the 5th position right before it is being freezed (and looks like it did not change after that).

We attempted two more problems (G and J) after that. Problem J is actually an expression-evaluation + optimal path finding, which is quite complicated and my naive top-down DP solution does not run in time. Problem G is about graph, which is quite similar to problem D (Domino) of the ACM Indonesian National Contest 2007 (finding the longest Euler path by first modifying the graph). A team in our room got Accepted for a problem and got their 7th balloon, but not much else happened. Altogether, we made exactly 40 submissions (23 of it is on problem J with all kind of permutation of optimizations).

I don't know why, but I am sure that the Judges got mixed up between TLE and WA, since some TLE solutions like infinite loops is being replied with Wrong Answer, which is very misleading and makes the debugging process difficult. We have noticed this problem on the practice session, and when we asked, the reply was "depends on the judge" which is not satisfactory. The RCD also stated on the opening ceremony that other than a Yes (Accepted) or No (Not accepted), we should not depend on the Judge's reply, which is quite weird for this kind of competition.

As we did not eat much at all (I only ate a small piece of brownies during the contest), we ate right after the contest is over. Took some time to take some photographs before we moved to another building for the closing and awards ceremony, which started with a speech by a representative from IBM about the career for programming talents.

To our surprise, the prizes for this contest is being distributed in random for the top-12 teams. Since two teams from the same university cannot place twice in the ranklist, we are officially at the 4th position (actually we could've been better if we did not waste too many points on the WA solutions). The first place goes to the team puyo from National Taiwan University.

The party is being organized after that, in a restaurant in Miramar Mall (famous for a giant ferris wheel attached to it). It was a nice dinner with several mini-games with prizes.


The Mall itself is a very well-designed one, with a beautiful alley right in the middle of it. Finished with all of the scheduled events, we were transported back to the Teacher's Hostel and rested.

Continue to Day 5

-Andrian Kurniady

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


Andrian Kurniady’s Blog » ACM ICPC Regional Contest - Taipei Site 2007 said...

[...] Day 4 (November 25th) - Contest and Closing Ceremony [...]

Andrian Kurniady’s Blog » Day 3 (November 24th) - Practice Session and Opening Ceremony said...

[...] Continue to Day 4 [...]

Andrés said...

Hello Andrian,

Can you explain me what is the matrix multiplication speed up trick you wanted to need in problem H - Maze for robots?


Kurniady said...

The maze for robot (H) can be simplified into
A' = MA
for each step, where A and A' is a vector (or simply a column-matrix) and M is a square matrix. Multiplying M with A gives you A' (i.e. the number of accepted strings ending with each nodes). In the onsite, by running A'=MA as many as a specified time (the string length) does not exceed the time limit, giving the complexity of O(N^3 L). However, there is a way to reduce it into O(N^3 log L) by playing with the M matrix. M^2 = M*M, M^4=M^2*M^2, therefore you need roughly only log L matrix multiplication (instead of L). A'=M M M M A => A'=M^4A.