post

ACM-ICPC Asia Jakarta Regional Contest 2010

Mr Win Ce, the chief of judge, had announced the result. Saklar Lhompat team got #7 place in the overall ranklist and got #1 place in the local (Indonesian teams) ranklist! We got Best National 1 award, plus certificates and Android OS mobile phones. This is our first ICPC regional contest, though. We hope we’ll do better in our next regional contest in Kuala Lumpur on the next couple of weeks.

Here the story goes….

Contest Site

This regional contest took place in Anggrek Campus of BINUS University, Jakarta, Indonesia, in my own country. It is not too far from University of Indonesia, so we didn’t book any hotels. All UI teams used our yellow bus to get there and return to UI every day during the contest.

Teams

Previously, there was a qualification round for Indonesian teams called Indonesia National Contest to select the best 50 teams to advance to this regional contest. Saklar Lhompat got the #5 place. The best place from UI was claimed by Eleazar team, #2 place. So, there were 50 local teams and 16 foreign teams, for a total 66 teams participating in this contest, with 9 of them from UI.

There were several TOKI alumni who participated in this contest, so this contest was like a reunion to us. There was also a legendary (?) team consisting of all girl contestants, YummyBomb.

Problemset

There are 10 problems in the problemset. Two of them, D and I, are easy bonus problems which were solved by most teams. Problem H turned out to be the hardest problem, being solved by only one team. The problemset consists of mostly DP and graph problems, and fortunately no geometry ones. There is also a nice problem about game theory (problem C).

Overall, many contestants said that the problems should have been more difficult for a regional contest, because there are too many problems in easy-medium level.

A. Worst Location

It was the last problem we tried. Until the end of the contest, we had submitted 9 solutions but all of them got wrong answer verdict. No wonder because we tried to solve it in a hurry and this was our last hope to solve 9 problems.

B. Counting BST (AC in minute 140)

I had solved this kind of problem before in a training camp. It is a combinatorial DP in tree. Let dp[u] be the the answer of a subtree with u as the root. Then dp[u] = dp[u’s left child] x dp[u’s right child] x (A choose B), where A is the number of u’s children and B is the number of u’s children to the left (or to the right).

C. Playing with Stone (AC in minute 35)

A modified Nim game. To solve most impartial games, we have to determine the Grundy number of each subgame. Let G[n] be the Grundy number of a pile with n stones. After trying to find some patterns by brute force, it turned out that G[n] is n/2 for even n, or G[G[n/2]] for odd n. To solve the problem, take the XOR of the Grundy numbers of initial piles. If it is nonzero then there is a winning move.

D. Arm Wrestling Tournament (AC in minute 17)

It was the bonus problem in this contest. The solution is just simulating the tournament as the problem statement says, with efficient data structure. Our team was the second team to get accepted in this problem.

E. Lightning Energy Report (AC in minute 173)

A problem about LCA. At first I thought it was to be solved using heavy-light decomposition, but it turned out that it would be too overkill. Alham found a solution similar to partial difference data structure. For each query we marked the two end nodes (one positive value and one negative value). Then, a final DFS would aggregate the answer for each node.

F. Transitive Closure (AC in minute 121)

It was an easy problem, just use DFS N times. But somehow I first coded a buggy SCC-based solution, before Alham pointed the DFS solution! This made us waste around one hour, sadly.

G. Just Sum It (AC in minute 259)

Another combinatorial DP problem that is hard to describe in a few paragraph. The idea is fixing each digit individually, and counting how many numbers can be formed when the remaining digits are placed on the left and right of it. Our DP state was, after removing the fixed digit, dp[len][dig], i.e. the number of len-digit numbers that can be formed using digit 1..dig.

H. Serial Numbers

I even didn’t read the problem during the contest. Alham, as the thinker, decided that the problem was too hard and we should focus on the problem A in the end (which we didn’t manage to solve, either).

I. Romantic Date (AC in minute 60)

It should be a bonus greedy problem, but we didn’t know why it failed in the first attempt. So I coded a bipartite matching solution that must give the optimal answer. We knew that it was overkill but coding BPM was pretty quick.

J. Fire Drill (AC in minute 196)

This is a combination of BFS and standard knapsack problem. First, calculate the shortest distance from Joko to the volunteers. Because each volunteer is independent, we can compute the optimal points using knapsack DP, with time as the knapsack capacity and distance as the cost.

Result

Overall:

  1. +1 ironwood branch, National Taiwan University
  2. Halo, Shanghai Jiaotong University
  3. ManiAC, Chinese University of Hong Kong

Local:

  1. Saklar Lhompat, University of Indonesia
  2. Dongskar Pedongi II, Institut Teknologi Bandung
  3. Hope, BINUS University

ACM-ICPC Asia Jakarta Regional Contest 2010 Final Scoreboard

Saklar Lhompat managed to solve 8 out of 10 problems. No teams solved all 10 problems, though. I am pretty satisfied with the result, especially being the best local team, considering that it was our first regional contest.

I am also very happy to receive a Samsung Galaxy 5 with Android OS as the prize of being the best 3 local teams. Now I can begin learning mobile programming on Android platform, aside from competitive programming.

Epilog

YummyBomb, being the only teams with 3 girls as the members and ranked #4 overall, was becoming a star during the dinner party. Many teams wanted to take photos with them, including me :D.

About Ashar Fuadi

Ashar Fuadi is a competitive programmer from University of Indonesia. He loves to code, especially for TopCoder SRM, Codeforces, and ICPC.
Follow Ashar on Google+ and Twitter.

Comments

  1. gua sarankan tuh scoreboard lu copy dah, takutnya (sepertinya) linknya nanti bakal berubah =P

  2. wuih,,,selamat yah,,,dapet #1 best national team…ngalahin dongskar…:D
    2-1 (gemastik, icpc – inc)

  3. @marcadian: berubah jadi apa?

    @brainplusplus: thanks, waah sampai diitungin juga poinnya kayak match aja 😀

Speak Your Mind

*