Tuesday, July 15, 2008

ACM ICPC Indonesia National Contest 2008

June is the time for the ACM ICPC Indonesia National Contest, just like last year. This year I participated with the 'kurniady' as the team name again (it's becoming a habit :lol: ), with Fiona Liausvia and Purnama, as a Binus International team. There was another team from Binus International as well but sadly they did not make it past preliminary.

For this year, the online preliminary round was held in the 1st day of June. On the day, our team participated from the Binus Syahdan campus, in a lab reserved for INC participants (although it is okay to do it from home too, since it's an online contest). It was a set of 5 problems to be solved in 3 hours. The problems by the order we got it accepted are :

Problem D - Maze Walker (My Solution)

This problem can be solved by doing some "flood fill" to find out the "islands". Every connected island of N nodes will have N * (N-1)  / 2 pairs of node in it. Identifying all islands and summing up their number of pairs of nodes gives us the solution to the problem.

Problem E - Lemonade One (My Solution)

At the first glance, this problem looks like a dynamic programming problem. But finding out that we should pick only two out of the five days suggests that a brute-force solution will run fast enough. Picking all possible combination of two days, our solution also bruteforced the number of lemonade sold on the first day, calculate the second day returns, and find the maximum value out of all the combinations.

Problem B - Converting Numbers (My Solution)

This problem is quite tricky. A lot of teams got Wrong Answer a few times before got accepted. The most common mistake was in the number conversion. When all of the numbers are the same, calculating the standard deviation will result in a zero, which may screw up the following calculations. We got a few Wrong Answer before we made it right.

Problem A - Who Got the Medals? (My Solution)

This problem is quite an ad-hoc problem. You can see from the solution that a lot of "if"s is involved, which means a lot of opportunity for error. Following the rules, we made a few mistakes before getting it right.

We almost solved :

Problem C - Panda Land 3: Text Wrapper (My Solution)

This problem is also an ad-hoc problem. Basically it tests your skills on string handling. The idea is quite simple where you tokenize the input into words and then print it out following the page width rules. My solution used a lot of Standard Library features such as string, vector, and such, therefore did not passed due to the time limit. Our solution runs in 8 seconds, which the time limit is only 5 seconds. If just the solution was coded in plain C-string (instead of string), it would've got accepted.

Solving 4 out of 5 problems, we advanced to the onsite finals. There are surprisingly many teams solving 4 problems as well, so I'm a bit concerned about the finals, although the biggest concern was about Timotius Sakti (team TSP).

On the actual finals day, which is on the 15th of June, I arrived in the Syahdan campus at around 8am. By that time, there was so many participants queuing to register, so I decided to wait for a moment while having some chats with Timo and Stephen Kohar, his team member. Most of the conversations were about the Topcoder SRM 405 the night before. In the SRM, I was a room winner in division 1 in a money-match (room winners got awarded with cash), which was my first time ever. I found out only at the morning, as I left the Topcoder competition arena early to be able to get enough rest for the INC finals.

The events are like usual : several opening speeches, a briefing by Mr. Suhendry and Mr. Win Ce, plus a practice session (around one hour) and a lunch (provided).  After all that, the real competition began at around 12:45 pm to finish five hours later. The problemset for the final round can be downloaded here : Final Problemset (PDF).

The finals problems by the order we solved them are :

Problem D - Eat or be Eaten (My Solution)

The problem is actually quite straightforward. Our solution sorts the two lists (actually you only need to sort one of them), and then for each member of the first list, find the number of elements in the second list that is less than the first. With STL, this is easily achievable without much effort with sort() and lower_bound() function. Got accepted in the first try.

Problem E - Indomie (My Solution)

This problem can be solved by simple dynamic programming by observing the probabilistic rule. Our solution runs in O(N.S) without recursion or factorial whatsoever. Our first submission was judged Wrong Answer at first, but then rejudged into Accepted a few minutes later.

Problem G - Hotel (My Solution)

This problem is quite an ad-hoc problem. I used STL pair which can be sorted with STL sort() function by default, and just follow the rules stated in the problem statement (admittedly the rules are quite obfuscated :P ). We also got accepted on the first try with this one.

Problem A - Superstitious Skylab Tower (My Solution)

This problem is quite classical. It is quite similar to last year's Panda problem (which was much more complicated, in my opinion) which was solved by only one team (not mine). There was also a couple of problems in Topcoder and Informatics Olympiads (IOI/CEOI/BOI/ *OI which I forgot which) that is quite similar to this one. The solution was to do Dynamic Programming in respect to the digits. Our solution is in O(N 10^2) where N is the number of digits for the precomputation, and O(N) for the query, which is quite efficient. The first couple of tries has some bugs within the code, but matching the result with the bruteforced-by-hand result (up to 200) has let us find the bug quite quickly.

Problem C - Almost Clear (My Solution)

This problem, as like many other computational geometric problems did not attract a lot of interests from the participant, because geometric problems tends to be quite complicated with formulas and prone to many kinds of errors (precission error, division by 0, you name it...). Thanks to our well-prepared team notebook (which was adapted from our ACM World Finals 2008 team notebook), which included a line intersection function, I tried to solve this problem.

The idea was to convert the points in both polygons into angles agains the camera, which are then sorted, to find the angle coverage of both polygons. If the angles of both polygons don't intersect, that means a clear visibility. If the angles did intersect, then we have to find out which polygon is closer to the camera. My first solutions runs in O(NM) where N is the number points in the first polygon and M is the number of points in the second polygon. Given that there are up to 1000 points each and many testcases, plus it needs a lot of floating point operations, the solution got rejected because if exceeded the timelimit.

The final solution for this problem was to convert one of the polygon into one line spanning from the lefternmost point to the rightenmost one (in respect to the camera angle), and intersect that line to all of the lines from the camera to the points in the second polygon. This resulted in the runtime of O(M) which is quite acceptable even with the sorting procedure that makes the overall complexity becomes O(M + N log N + M log N). It was just like 14 minutes before the ending that we got an accepted submission for this problem.

And we almost solved :

Problem F - In Queries (My Solution)

This problem was actually quite simple (it's even easier than problem A or C). Our solution exceeded the time limit due to *again* being overly relied to the Standard Library (STL Set). Coding a tree doesn't solve the problem because it made the precomputation time becomes O(N log N), even though it solved the queries in O(log N). The judge's solution runs in O(N) precomputation and O(10.000) per query, exploiting the limited range of possible numbers. Because the number of queries was low, our solution runs way slower compared to the judge's solution on the contest test data.

For most of the time before the scoreboard was frozen (1 hours before the ending of the round), our team and team TSP were in the top two spots of the scoreboard. After four hours, both of our teams solved 4 problems (we solved D,E,G,A while TSP solved D,E,G,F). During the last hour, we solved another problem, problem C which was the trickiest problem we attempted in the contest, after several submissions.

(Team EMI on the left, team acmon on the right)

(Team pinkpanda)

Before the awards ceremony began, we found out that team TSP did not solve any more problems during the last hour. When announced, the winners are :

The 2nd Runner Up was from Universitas Kristen Satya Wacana - EMI (Erisman Kriswandhani Lim / Michael Ade Soewondo / Indra Suryatama), solving 3 problems.

The 1st Runner Up was from Binus University - acmon (Eko Wibowo, Lie Gunawan, Cun Cun Lim) solving 3 problems.

The 3rd place goes to Binus University - pinkpanda (Winardi Kurniawan, Eko Mirhard, Panji Kharisma), solving 3 problems.

The 2nd place goes to Binus University - TSP (Timotius Sakti, Stephen Kohar, Pascal Gerardus Angriawan), solving 4 problems.

The 1st place goes to Binus University - team kurniady (Andrian Kurniady, Fiona Liausvia, Purnama), solving 5 problems.

(Suhendry Effendy and Team TSP)

(Mr. Fredy and team kurniady)

The final scoreboard can be seen here : Final Scoreboard (PDF)

Some members of the problemsetters and judges, namely Felix Halim and Suhendry Effendy had also posted their stories and solutions to the problemset in their sites :

(All winners)

(The problemsetters and judges with Mr. Fredy)

There were other remarkable achievements as well, including team from Petra Christian University (vista) made it to the top 10, as well as team EMI who are first timers in the INC made it to top 5. Congratulations to the winners, as well as the finalists. Many thanks to Binus University and HIMTI for their commitment in organizing such a wonderful event regularly.

-Andrian Kurniady


akhmad said...

congratulation yach....
woowwww....2 tahun berturut-turut..
i will improve my coding skill to be like you.. ^_^

Andrés Mejía said...

Very nice write-up. ¿Do you know where can I read the problem statements from the qualification round?

Kurniady said...

Suhendry Effendy (the chief judge) has the practice and qualification problems linked from his blog post http://www.suhendry.net/blog/?p=92 (practice) and
http://www.suhendry.net/blog/?p=93 (qualification). It's on the second page (and next pages for problem B,C,D,etc. ), the link near the top of the page links to the problem description.

In a very short future (about a week or so), I'll be launching my own online judge and the problems will definitely be there as well.


Andrés Mejía said...

Very cool! I will participate in your online judge.

adam123 said...

So cool,you can get so much(3,000,000) from the contest...:D

Indra Suryatama said...

i 'am from EMI (UKSW univ)
hmmm i hope someday i could have a skill like you ^^
hmm interesting i will participate in your online judge too
hmmm iam totally mess on regional this week
by the way, could i add you on ym or msn ...
so if i have a trouble i could ask help for you



Indra suryatama

brian said...

wah keren2 mang anak binus