Monday, June 18, 2007

The ACM ICPC Indonesia National Contest 2007

This year is the first year for BiNus to host a contest bearing the ACM ICPC logo, in form of Indonesia National Contest (INC) 2007. In previous years, BiNus organized a yearly competition called Bina Nusantara Programming Contest for College Students (BNPC-CS). As a preparation to host an Asian Regional Contest site in 2008, since this year, BNPC-CS is changed into ACM ICPC INC which is now a competition for teams of three peoples. This time, my team consists of myself, Dennis Andika Suryawijaya, and Peter Suryaatmaja, and I chose "kurniady" as the team name because I don't have any other idea for the team name :)

The contest is conducted in two rounds : the online preliminary round (June 10th) and the onsite final round (June 16th). I went to BiNus Syahdan campus for the online preliminary round, to avoid network problems which may happen on my internet connection. There was 5 problems for 3 hours in the preliminary round. All of them are easy problems that needs only some 20-40 lines of code each and 15 minutes of coding. Unfortunately, due to a couple of reasons I did not solve all of the five problems during the round. I misinterpreted the rounding rules for problem B, which gives me Wrong Answer upon submission. The other bug was in problem D, where I declared my variable as type "long" (should've been "long long") and print it using %lld (which is for long long). The program works fine in my computer because I compile using DevC++. The same program, compiled by the judges with DJGPP produces silly erroneous output, because long and long long is different in DJGPP. At the end of the round, I only solve 3 problems and ranked fourth out of the 162 or so participants. All participants solving at least one problem advanced to the final because there are only 42 teams solving at least one problem, thus the original quota (one slot for best of each university solving at least one problem) was not effective. To fill the remaining 8 slots, the committee invites some teams from the participating universities that was not qualified, to give them the chance to experience the contest as well.

The final round, unlike the previous BNPC-CS, was held in BiNus' Joseph Wibowo Center campus (my campus - BiNus International). The reason was that the final round are supposed to be conducted in one whole big room for the participants, and the computer labs in Syahdan and Anggrek is not currently equipped with removable partition between the labs. We were told to come at 8am in the morning to do the re-registration and attend the opening ceremony. My luck of the day started during the drive from home to the campus : every traffic lights I went through turned green every time I'm about to pass, thus despite of the normal traffic, I arrived early on about 7.40am, only 20 minutes after I left home. The drive usually takes at least half an hour and has never been that fast except if I departed really early in the morning before 6am.

The event started with the usual re-registration process, during which we were given a T-shirt, a name tag, a bottle of water, an event guide book, as well as a nice plastic handbag to carry them. The opening ceremony consists of some speech by the Vice Rector and the Head of Computer Studies of Bina Nusantara University. A briefing session was conducted after that, by Mr. Win Ce and Mr. Suhendry Effendy, detailing what to do during the competition. A trial session was held on 10.00am to 11.30am to make sure everything was rightly prepared. Because we were given the problemset for trial session right after we entered the room, and the contest in the PC^2 system was not started, I managed to read the problemset, code a quick solution, and submit it right after the contest is started in PC^2. This yields an accepted submission, the first one, with time 0 minutes and that means we are on the top of the scoreboard for practice session. Having not much else to do, we went outside to have some snacks before the real contest.

Right on 12.00 noon, the contest started. I prepared the environment, and log into the PC^2 system. We decided that the easiest problem was problem A, in which I am not sure about the correctness of my algorithm but I submitted it right away as it is already correct for the sample cases. Luckily, the algorithm was correct and we got it Accepted in 16 minutes. Not fast enough as team phoenix (from BiNus as well) got it in the 14 minutes. Right after that, I coded for problem D, based on the explanation about the problem by Dennis. That makes another Accepted run in 27 minutes. The next thing to code was problem G. At first, I want to try submitting a brute-force solution, but when I'm about to do that, I saw a red mark on NoMoreAC's problem G, meaning that TimeLimitExceeded (TLE) is very likely. At that time, NoMoreAC have already solved problem A and D. I immediately think of a better solution, and found one using the STL set_intersection and a couple of formulas. That makes an accepted run for problem G in 48 minutes.

Having solved three problems, I took a rest, went outside and have some snacks while Dennis coded for problem E. After that brief rest, I directly coded problem H, knowing that it is another variation of Tree-DP problem. The first submission of that problem yields a Wrong Answer (WA). I left the problem and directly coded for problem F, which is another simple A* or Dijkstra problem (just like problem E - Taxi in the preliminary round). At that time, team NoMoreAC have already solved 4 problems and was on the top of our team in the scoreboard. The submission took a very long time to be judged, first replied with WA by the judge. While I rechecked the problem with the code, another message appear telling that we got Accepted for problem F (rejudged). We are now on the top of the scoreboard again, now permanently until the end of the contest. Dennis tried to create a testcase for my problem H's solution and found that my program returned a wrong answer for his test case. I traced the program and found the bug : an unnecessary addition was done during the condition checking, which means the program will skip some of the best solutions. Deleting the problematic code, we got it Accepted in 218 minutes. That gives us our 5th balloon, our last before the scoreboard was freezed and no more balloons were delivered.

During the freezed time, I tried to solve problem B. The first attempt failed with TLE because it is a plain brute-force solution. I went out for a while to have some snacks (again), and suddenly I got an idea. I went inside and upgraded my program with some pre-checking for prime numbers, and this time I got it accepted in 267 minutes. For the rest of the time, Dennis resumed his job on coding problem E. It got TLE and has never got accepted. I found a trick for that problem but it was 3 minutes before the contest ended, so we never got the time to implement it. The contest was then over, I packed all of the codes and send it via email to my mailbox for later viewing.

We went outside the labs and I had some chats with NoMoreAC team. They did not solve any problems after the scoreboard was freezed, so they still solve 4 problems. We don't know whether any other teams have solved any other problems. After some long chats about our algorithms, we went down to the main hall. Over there, Mr. Suhendry explained the algorithms used by the problemsetters to solve each problems. Mr. Win Ce said that there was only 3 teams solving problem B, and one solution each for problem F and H. That was us, and we were relieved.

The award ceremony comes after that, the result was :

  • The 6th place goes to Team hura-hura (Universitas Katolik Parahyangan)

  • The 5th place goes to Team PGK (Bina Nusantara University)

  • The 4th place goes to Team Tweety (Bina Nusantara University)

  • The 3rd place goes to Team nelkichan (Universitas Katolik Parahyangan)

  • The 2nd place goes to Team NoMoreAC (Bina Nusantara University)

and the first place, goes to Team kurniady from Bina Nusantara University International.

That was the day, we got each a medal and one champion plaque for the team, along with 6 million rupiah in cash prize. The competition was over, congratulations to the winners and see you again in the next competitions. We would like to thank everyone for the supports given to our teams that makes this achievement possible.

Felix Halim has posted a very nice problemset analysis which can be found here.
Ms. Yen Lina Prasetio has also posted the pictures in her blog.

Continue to Final Round Solutions.

-Andrian Kurniady


suhendry said...

congratz kur :-D

eh, ayo mulai latihan lagi mon. regional tinggal beberapa bulan lagi. GO WORLD FINAL!! uupps.. salah, itu mah target tahun lalu, basi. target kita kali ini: TOP-20 WORLD FINAL!!!! B-)

Felix Halim said...

Yoi mon, Top-20 World Final!!

Andrian Kurniady’s Blog » Day 4 (November 25th) - Contest and Awards Ceremony said...

[...] 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 [...]

Andrian Kurniady’s Blog » ACM ICPC Indonesia National Contest 2008 said...

[...] 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 [...]