Sunday, January 27, 2008

Day 3 (December 14th) - Contest Proper and Awards Ceremony

Based on the experience from the previous day, we managed to depart early from the hotel and went directly to NUS. As the previous day, our team arrived earlier than the other team from Fort Canning. Some breakfast was served by the committee in the venue. Not long after that, all of us moved to the contest venue, which require some queuing to ride the elevator upstairs. I handed over my camera to Suhendry, to take some pictures during our contest.

All set and ready, our seats are not in the same place as the practice session's arrangements. As soon as the contest begin, I got surprised because there are only 7 problems in the set. Usually we would expect some 8 to 10 problems for this kind of contest. More or less, the 6 available problems was quite easy as well (compared to other regionals we have attended).

By the order we got it accepted, here are our solutions to the problems (problemset available here) :

  • Problem A - Modex

    • This problem is solved by Kenny, who needed only some 5 minutes of coding. The problem itself is actually the classic x^y mod n problem, which can be solved in O(log y) divide-and-conquer approach. An exactly same problem is available in ACM UVA. We got it Accepted on the first try.

  • Problem C - Acorn

    • I knew instantly since the first time I read about this problem, that it is to be solved with Dynamic Programming. My approach is actually O(N^2) but optimizable to O(N) by adding a temporary variable. It took some 10 minutes to code for this problem and we got it Accepted on the first try. Some other teams used the same O(N^2) approach and got Time Limit Exceeded, therefore I think we were very lucky.

  • Problem G - Racing

    • On the first glance, I thought it is something like Minimum-Cost Maximum-Flow problem. However, Timo mentioned about Minimum Spanning Tree and I suddenly realized that the solution require some Maximum Spanning Tree (reversed Kruskal). I coded some part of the solution before handing it over to Timo who completed it and we got Accepted on the first try.

  • Problem F - Usher

    • On the first glance, this problem is to be solved with A* heuristic search. However, the first solutions we submitted using A* got TimeLimitExceeded. While fixing (trying to optimize), I suddenly realized that it is actually only about finding the shortest cycle in the graph, which I solved using Dijkstra's algorithm (changing only a little bit from the already completed A* algorithm). That gives us our fourth balloon.

  • Problem D - Tusks

    • This is a computational geometry problem. I somehow got the idea to simplify it into finding nodes on the left and right of an imaginary line between all pairs of nodes. The naive approach is O(N^3) and will surely exceed the time limit. I managed to simplify it into O(N^2 log N) with the use of angles and sorting. The first try got Wrong Answer because of some bugs in the implementation. I fixed it, and the result for the example cases were two times the correct answer. I added a "division by two" to have the correct answer for the sample cases, and submitted. It turns out that my dirty hack was lucky, it got Accepted. Several days after the contest, I finally understood why my solution is correct.

  • Problem B - Jones (Accepted after rejudge)

    • This problem is actually quite straightforward, a simple Dynamic Programming problem that can also be solved with BFS. I coded it, made sure that it worked correctly according to the problem statement, submitted, and got Wrong Answer. I tried to fix it, and found a bug in my solution (a simple typo). After fixing it, we still got Wrong Answer. Requested clarification once, and found out that our understanding about the problem is perfectly correct. But still, Wrong Answer after several tries. Kenny coded a new solution (BFS, mine is DP) and still got Wrong Answer. I was convinced that the judge's solution got problems, as several strong teams did not solve it as well (except Felix Halim :P and Sofasquad plus some very few other teams, who submitted several times until it got Accepted).

    • Later on, after a rejudge (several days after the contest, when we have already returned to Indonesia), we found out that my second solution was actually already correct. Unfortunately, it did not affect our rankings as other teams got it Accepted as well.

  • Problem E - Skyline

    • Timo read about this problem, and explained it to me. I got the impression that this problem is quite similar to problem Mountain of IOI 2005 (Poland). The solution is using some tree data structure. Timo found another solution, coded it and got Time Limit Exceeded. I was struggling to get problem B accepted, therefore got not enough time to code this problem. I mentioned something like Misof-tree to Timo but we got not enough time to look it up in the notebook and code it. Therefore, until the end of the contest, it was not solved. Timo asked the team from Shanghai Jiaotong University and was told that it was to be solved with Segment-tree (my guess about using tree was correct, and Segment-tree is some generalization of Misof-tree).

After the end of the contest, we asked Felix Halim on how he got problem B accepted, and he got no clue why other teams did not solve it (turns out that his solution is wrong, for the case when John hop on the first stone on the zeroth minute).

Right after that, the lunch was served. We arrived a bit late and therefore had to eat in a hurry, because the bus for the city tour was about to depart soon.

The bus took us to the Merlion Park, which is one of the most famous landmark of Singapore. Across the river was the Esplanade building. We took a lot of photos there, both in teams and individuals.

There was a Merlion statue in there (the symbol of Singapore), accompanied by a lesser Merlion statue behind it.

We then returned to the NUS by taking some routes through China Town and Little India. Since the awards ceremony was not yet to begin, we were suggested to visit the art Museum in the Cultural Center (venue for awards ceremony) of NUS to kill some time. The exhibit in there were mostly abstract paintings which took some time to actually understand and enjoy. There is also some unique figures such as this one below.

To our surprise, the awards ceremony was merged with other events including the AlgoMania (Algorithm competition for high school students) and First Lego League (looks like Lego Mindstorms with Artificial Intelligence - for students). It is combined as some sort of IT Fair hosted by NUS School of Computing. That makes the closing ceremony bigger but less specialized to ACM ICPC winners.

There was the education minister of Singapore coming as well to give some speech and present some of the prizes.

Without much surprise, the first place (and the three Lenovo Thinkpads) goes to team Prime from Shanghai Jiaotong University.

After the ceremony, the dinner was served. The ex-TOKI members took some time to take some photographs together on a stairs.

The Indonesian participant, coaches, and guides of the contest also took some time to take this photo altogether.

The official result can be seen here. After that, we said goodbye to our guide, Tania, and returned to Fort Canning Lodge to rest for a while. We then go to a nearby hawker center to have some supper before returning to the hotel for a complete rest. It was a long day, and we're glad it was over.

Continue to Day 4

-Andrian Kurniady

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


Andrian Kurniady’s Blog » Day 2 (December 13th) - Opening Ceremony and Practice Session said...

[...] Continue to Day 3 [...]

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

[...] Day 3 (December 14th) - Contest Proper and Awards Ceremony [...]

suhendry said...

mantap mantap :-D eh, jadinya sekarang udah bisa segment tree donk yah :-D

yang F agak overkill... masih bisa di floyd-warshall. tapi gpp lah, yg penting AC dan gak pake lama :-D

btw, gubrak deh itu Tania ngapain yah....? =))

Andrés said...

Hello Andrian, do you still have the source-code of these problems? I just solved problem Acorn on the Live Archive using O(n^2) DP and got accepted. However I would like to see the faster O(n) approach.


sandrar said...

Hi! I was surfing and found your blog post... nice! I love your blog. :) Cheers! Sandra. R.