Saturday, October 29, 2005

ACM ICPC Regional Manila 2005

IMHO, overall, this year ACM ICPC Regional Manila 2005 (held in Ateneo de Manila University) wasn't as good as the previous years (held in University of Asia and the Pacific). This year, they gave bags and t-shirt as souvenirs. The t-shirt quality seems to be improved from the last year but the scheduling and the contest preparations seems worse than last year.

Practice Session. The waiting time between events were too long, the practice session were delayed and shortened (it became too short!) and was not pleasing since they didn't finish judging the runs in the queue when the practice session was over! Also the problem input name was renamed without notification! We kept getting wrong answer. Although it's a practice, it was still very dissapointing!

Contest Proper. Several inconveniences arise during the contest proper:

  1. Java Compile Error, they promised that whatever compiled on our machine, will also be successfully compiled on the judge machine, but the fact says otherwise: many teams got penalties for compile error during the contest proper! and they didn't give clarification of why it happens. My team rewrites our Java solution (which get's compile error on Judge machine) to C/C++ solution because of that. The other teams also have the same experience. It's very disappointing.
  2. Printing problems, some teams have to use flashdisk to print!
  3. The standings, the big projector which displays the teams' rank and their solved problem was MIS-LEADING! The problem name was out of order! For example, problem D is actually problem C on the standings! I think they really need to learn how to configure the PC2! (the online judge system for ICPC).. or.. were they jumble the problem name intentionaly? Anyway, whichever it is, it's unfair.
  4. Controversial Problem, there is this Problem C in the problem set, which is controversial! A lot of clarifications were asked for that particular problem, seizing a lot of team's time!
  5. Permission to the restroom, We got a hard time to get to the restroom!
  6. Seating arrangements, they wanted to make it similar to the world final seating arrangements where all teams compete in a single room. It's nice, but it makes the teams very uncomfortable since we didn't get enough space! They try to fit 98 teams in a not-so-big-theatre. We barely move and we barely put our paper on the table, we put some paper on the floor :o

The awards. Last year all of the team names were mentioned during the awards session (including the honorable mentions) and Top 10 teams were called to the podium. But this year, they only announced best 3 teams overall and best 3 local teams. It seems that they didn't give enough "appreciation" for all teams even for the top 10. It's ridiculous that team ranked 25 could receive award at the podium (because it's one of the best 3 local team) while the top 10 teams (overall) were not even mentioned!

The contest results (some name is truncated to fit), click here for the official result

Rank    Team's Name         University                          Country/Territory   # Solved
1       Fate                The University of Hong Kong         Hong Kong               8
2       eXtreme GNC-4 ...   University of Tokyo                 Japan                   8
3       The Linden BoyZ     Ateneo de Manila University         Philippines             7
4       SNU team2 Ra!       Seoul National University           South Korea             7
5       P.S.P               The University of Hong Kong         Hong Kong               6
6       SNU team3 Goon!     Seoul National University           South Korea             6
7       For Union           Yonsei University                   South Korea             5
8       TJU BliZZard        Tianjin University                  China                   5
9       Pinyin              Zhejing University                  China                   5
10      Vinix               Bina Nusantara University           Indonesia               5
11      K-CUBE              De La Salle University-Manila       Philippines             5
12      Arirang             Yonsei University                   South Korea             4
13      HCMUNS Victory      University of Natural Sciences      Vietnam                 4
14      Smart Bee           Bina Nusantara University           Indonesia               4
15      CS-Unpar            Parahyangan Catholic University     Indonesia               4
16      HKUST1              Hong Kong University                Hong Kong               4
17      Margonda            University of Indonesia             Indonesia               4
18      Avian               Tarumanagara University             Indonesia               3
19      HKUST3              Hong Kong University                Hong Kong               3
20      HKUST2              Hong Kong University                Hong Kong               3
21      Unlimited           Soongsil University                 South Korea             3
22      TeamALK             The University of Hong Kong         Hong Kong               2
23      CUHK_CSE            The Chinese University of Hong Kong Hong Kong               2
24      Thinker Bee         Bina Nusantara University           Indonesia               2
25      Persistence         Ateneo de Manila University         Philippines             2
26      KANG                Soongsil University                 South Korea             2
27      UP Wet              University of the Philippines       Philippines             2
28      UP BisDak           University of the Philippines       Philippines             2
29      Mapua DOTA Boys     Mapua Institute of Technology       Philippines             2
30      Booroonggoo         University of the Philippines       Philippines             2
31      Nara                University of the Philippines       Philippines             2
32      Team Roger          University of the Philippines       Philippines             2
33      KLUGE               De La Salle University-Manila       Philippines             2
34      UP Team of ...      University of the Philippines       Philippines             2
35      Angels              Ateneo de Manila University         Philippines             1
36      Exepxions Team 1    University of Saint Louis Tugegarao Philippines             1
37      Sarutobi            University of the Philippines       Philippines             1
38      Exepxions Team 2    University of Saint Louis Tugegarao Philippines             1
39      Kennon              University of the Philippines       Philippines             1
40      ONE HUNDRED         University of the Philippines       Philippines             1
41      DLSU 1              De La Salle University-Manila       Philippines             1
42      Decided             University of the Philippines       Philippines             1
43      Identical Code ...  Ateneo de Manila University         Philippines             1
44      <G                Ateneo de Manila University         Philippines             1
45      Vitalis Perfacilis  Ateneo de Manila University         Philippines             1
46      Aburame             University of the Philippines       Philippines             1
47      Magisx              Ateneo de Davao University          Philippines             1
47      STIPque coolLITz    STI College Paranaque               Philippines             1
49      Geekettes           University of the Philippines       Philippines             1
50      Uchiha              University of the Philippines       Philippines             1
51      Tulo Laway          FEU - East Asia College             Philippines             1
52      Lark                University of Asia and the Pacific  Philippines             1

The funny thing was that during the awards session, the local teams seems a lot happier than the "champion" (team name: Fate).

For a complete day to day life click on the days below. Note that only Day 3 and Day 4 are related to the contest, the rest of the day are barely documented for the completeness of the trip.

Day 1, Take off to Kuala Lumpur (Oct 26, 2005)

Late in the afternoon (3 PM), Win Ce Bong (our coach), Yen Lina (Ing2 roommate), Ryan Leonel (Buzz-er), Andrianto, Suhendry, Ing2, and I went to the Soekarno Hatta International Airport while the others: Andoko Chandra, David Santoso, Evan Leonardi, and Stephen Kohar went there separately.

First Row: Felix Halim (me), Andrianto, Andoko Chandra, David Santoso
Second Row: Ryan Leonel (hidden), Win Ce Bong, Evan Leonardi, Ing Ing Ang

Not long till we arrive at KLIA (Kuala Lumpur International Airport). Unfortunately, we've to spent the whole night until the next morning for the next flight to Manila. So, we spent the night at the Airport. I've to say that the Airport was quite high-tech that some of us were amazed of the automatic escalator:

Left to right (compare by head position): Ing2, Buzz-er, Kohar, Susu.
They were looking at Evan, who dare to go down using the escalator and fire the alarm when
he tried to force his way back up using the same one-way-going-down elevator.
Everyone immediately know that: "They must be Indonesian" :)

We ate at Burger King, it seems that Andoko and David enjoyed their Super-Big Double-Buffet :)

Some of us were tired and slept, the others were playing internet or playing with the laptops.

One of us were freezing because he didn't bring his jacket.
But later on, somehow, he got his favorite "super-mantle".

Day 2, Take off to Manila (27 Oct 2005)

Still at the KLIA, we ate breakfast. Some of us drink Starbucks Coffee, the other ate Noodles (some says the sauce is made of medicine?). At 11 AM, we then take off to Manila and went to Richmonde Hotel (the same hotel as last year). The transportation used was a taxi. It's amazing to imagine how 11 + 1 person along with their bags fit in. We met Hong Kong university (the champion) and the others during the hotel registration.

In the afternoon we went to the Mega-mall at 9 PM for dinner. The shops over there were almost closed at 10 PM.

Not much happened today, let's proceed to day 3

Day 3, Registration & Practice Session (Oct 28, 2005)

Today we went to Ateneo de Manila University to register for the match and did some practice.

Team name : "Thinker Bee"
(Left->Right) Ryan Leonel Somali, Andrianto Effendy, and Stephen Kohar.

Team name : "Smart Bee"
(Left->Right) Ing Ing Ang, Suhendry Effendy, and Evan Leonardi Ruslijanto.

Team name : "Vinix" (+hannah :)
(Left->Right) Hannah, David Santoso Anggakusuma, Andoko Chandra, and Felix Halim.
When we requested Hannah to take picture with our team, David brilliantly slipped by Hannah side.
We can see that David intention was clear, that "he likes her" (don't deny it, Vid).

Binus Coaches
(Left->Right) Win Ce Bong, and Yen Lina.

During the registration, we got a nice bag labelled ACM ICPC and Ateneo de Manila Logo.

The other teams from Indonesia also take pictures in this place.

Team name : "Avian" (Tarumanegara University)
(Left->Right) Yohannes Aditya, Edward Citrahadi, William Handoko Anggakusuma, and Sani Mohamad Isa (Coach).

Team name : "CS-Unpar" (Parahyangan University)
(Left->Right) Pascal Alfadian, Rosa de Lima(Coach), Ignatius Reza, and Ronny Gunawan ???.

Team name : "Margonda" (University of Indonesia)
(Left->Right) Fajran Iman Rusadi, Ilham Winata Kurnia, and Sutanto Sugii Joji.
The coach is Suryana Setiawan (not in the pic)

We were assembled to the Ateneo de Manila theatre for some introduction.
We were required to bring our university flag and then showed it to the audience.

On the left is (our) Bina Nusantara University flag (flag bearer: Stephen Kohar and Felix Halim).
On the right is Tarumanegara University flag (flag bearer: William Handoko and Yohannes Aditya).

On the left is Parahyangan Catholic University flag (flag bearer: Ignatius Reza and Rosa de Lima).
On the right is University of Indonesia flag (flag bearer: Fajran and Ilham).

After the briefing, there is a presentation from Microsoft (sponsor).
Which talked about the new Visual Studio team system.
Andoko and I then talked about things related to .NET and Java.

We take picture in the back entrance of the Ateneo de Manila University.
Note that there is a thing in this picture is called super-mantle.

The practice session was delayed for almost one hour. We got bored and start making some joke (see below).

The picture above is ko Wince standing, heated, and then melted into a stone :D

At last, we got to the practice room. Alas, the table was so small.
From left picture to right: Smart Bee, Thinker Bee, and Vinix

The practice session was too short and the ICPC committee was not prepare it well. The problem's input filename is different with the judge's input filename and that was not notified by the judges. Also the power went out once. The funny thing is, they do it again intentionaly. So the power went out twice. All computers restarted. Not long after that, the head of judge said: "The practice session ends in 2 minutes". Oh, what a useful practice. After he said that, we submit our solutions but they didn't judge it. The status of the submission is still "new" until the 2 minutes were over and we all leaved the practice room. Well... it's better than not having the practice session at all. At least we got to know that it's sufficient to use JCreator (we are not using Eclipse because it didn't work compatibly with JDK 1.5 and we didn't know how to set it up) and for the Dev C++ it went well.

Then we go to the basket ball court where they held the opening party.
The Anggakusumas' (David and William) seemed very lucky that night. They got prizes over and over.
We then head back to Richmonde Hotel and order fast food delivery, Jollibee!

Day 4, Contest Proper (Oct 29, 2005)

Early morning at 8 AM, using Bus, we head to the Ateneo de Manila University but it seems to early. Since there was no schedule until 12 AM (the contest itself).

We hanging around the entrance (left), and went to the canteen and stay there until 12 AM (right).

Kohar has a trick question before contest:
There are 10 person lining up. Each of them are wore a hat with color either black or white (randomly assigned by someone).
The person at the back of the line can see the person in front of him and the hat color they wear but not his own hat.
An algojo came and start asking the each of the 10 person one by one starting from the back of the line: "What is the color of your hat?"
Each person can only answer once: either "black" or "white". If the answer is correct the person can go free otherwise slaughtered to death.
Can you come up with a strategy that can save the most number of person in the line?
With your strategy, determine the maximum number of person that can go free, definitely.
The answer is 9 people can survive. What is the strategy?

The Contest Begins

Smart Bee and Thinker Bee were adjacent, front and back.
But Vinix was hidden at the back stage, no photos can reach that place

The head of judge then start counting (like a child) from 10 to 1, then the contest begins. There are 8 problems given:

Problem Name Problem Title Problem Category Difficulties
Problem A From Rational to Factorial Greedy Avoid Double data type! (only use double if you know how to handle precision error)
Problem B Right-Heavy Tree Graph Traversal The input is multiple input, but the sample input is not like that!
Problem C Portable Password Purse Ad Hoc Unclear problem statement, the protocol is not listed also the constraints of getting the domain name.
Problem D Any Relation? Set Operations Hard to parse input, thereafter is easy.
Problem E Mayday! Mayday! Recurrence Hard to read input: in Hexadesimal for the position, and unknown error, keep getting WA.
Problem F Check to Check Ad Hoc, Brute Force Relax, Andoko was there :D
Problem G Gotcha! Ad Hoc Relax, David was there :D
Problem H Counting Symbols Dynamic Programming Relax, David was there :D

Below is the story of my team, Vinix. For the other teams, please give me some info so that I can include it here.

During the contest, a lot of things happened but there nothing much I can remember. The first two hours went too quickly and I suddenly wanted to go to the restroom but I wasn't allowed, a committee told us to queue and jot down our team name. It take some time to get popped from the queue. Fortunately, I can hold on :D

We look around us, in front of us was University of Tokyo and at the back was Yonsei University - Arirang. They seemed to have a number of ballons and also Smart Bee and Thinker Bee got balloons too. When I looked at the standings projected on the big wall in the theatre, I saw that our team was ranked 23, the last rank before it became invisible from the top page. We haven't practically solved anything during the first 2 hours! I said to myself: "WOW, this is unbelievable, where should we put our face?"!

Actually, during the first 2 hours or so, we read and determine the easiest problems to solve first. Andoko was opted for Problem B - Right Heavy Tree. The problem is a straightforward graph traversal which like an everyday lunch for teaching-assistants like Andoko. But it turns out Wrong Answer! I then take over the hot seat and start coding for Problem C - Portable Password Purse. Because the problem description was so easy, I didn't even check the sample input and jump right to the coding. When I tested the code with the sample input, then I realize that this problem statement is very unclear! The "www" part is confusing, the "http://" is also doubtfull. The most confusing one is the TLD (top level domain). The problem statement just say ".edu, .com,,, etc." ETC??? what are the ETC? we can't solve the problem if we don't know the complete available TLD! Therefore this problem is unsolvable?!? For example, if you don't know that .com is a TLD, you would include .com as part of the domain, therefore you'll get WA! IMHO, why we didn't solve any problem during the first 2 hours is because of the invalid problem statement (Problem B - Right Heavy Tree) and because of the unclear problem statement (Problem C - Portable Password Purse)!

Our first AC problem (Problem B - Right Heavy Tree)

After 2 hour has passed, there came a "point-light" (titik terang maksudnya). The Judges send clarification that it was a multiple input! Whatta? What a misleading problem statement! This wasting our precious time and unecessary penalty points! that was suck! We resubmit problem B and got AC, thanks to Andoko.

Our second AC problem (Problem F - Check to Check)

In the beginning, as a mathematician, Andoko tried to solve the problem using formula only. But after he realized that a path can be obscured by other piece, he had to do the loop either. He refined the code and got AC.

Our third AC problem (Problem H - Counting Symbols)

David was a Dynamic Programing expert, problem like this was trivial for him. Without much problem except little typo, he got AC.

Our fourth AC problem (Problem G - Gotcha)

This is an Ad Hoc problem and it's supposed to be my job but since I was a little occupied, David take over and got AC once again, thanks to David.

Wow, that was quick. Problem B, F, H, G just got AC rapidly. When I looked at the standing, I saw that our team, Vinix, were just 1 position below Smart Bee with the same number of solved problems. Then I observe the standings for the clue of which problem that has the most number of AC. It turns out that almost none submit Problem C! So, in our mind, that Problem is still very unclear to most of the team and I decided not to continue that problem either. We seek for Problem E - Mayday! Mayday.

Spoiler: after contest, I found out that the problem name that was shown in the standing was not correct! The problem name was out of order! Problem D was shown as Problem C in the standings! That was MIS-LEADING. I got very angry knowing this fact. I could've continue solving problem C and maybe got AC out of it.

Actually, in between the 4 AC problems there were numerous WA for Problem A, submitted by me :D. I immediately became interested in this problem since I saw it from the first time. In my mind, Greedy is sufficient. I started the coding and submit it to the Judges... Jebret... Compile Error? What the... It's Impossible! I rechecked my code, but there was no sign of compile error on my local machine! Why did the judge said "Compile Error?". I did execute the test button on the PC2 and it was a success, and resubmit to the Judge. But again, the reply was still Compile error!?! I resubmit again and got Runtime Error!?! I got depressed. My team mates suggest me to rewrite my Java code to C++ code. I then instruct the fastest typist in my team, Andoko, to do the job. Then resubmit... Runtime Error... This time I really believed that my code had some flaws, I printed it out.

During the last 1 hour, I was still struggling with Problem A, while Andoko and David were struggling with Problem E - Mayday! Mayday! (the problem name matches our situation!). I was quite depressed with Problem A and wanted to change to Problem D but Andoko said that the time would not be sufficient. I think what he said was quite true, so I make up my mind and go to the restroom, preparing myself to re-code the Problem A from scratch! This time with refactoring the double precision functions!

Our fifth AC problem (Problem A - From Rational to Factorial)

At last! Problem A, after delving through many Compile Errors in Java, rewritten into C++, many Runtime Errors in C++, rewritten again from scratch in C++ and refactored some of the code, it got AC! The algorithm was still the same, but this time, the code is a lot more careful on the precision error which caused and endless loop and exceeding the array boundary which triggered the Runtime Error. Huff, fortunately I have some experience on precision error from last year: always add an EPSILON before doing things such as comparision, fmod, etc.. Spoiler: Later on I found out that using only integers is sufficient and it doesn't need to deal with precision error! hix2.. why don't I realize this sooner!

Till the end of the contest time, Problem B was still stucked. We were off with 5 solved problems, 4 balloons (the last was not given).

We managed to solve 5 problems.

We assembled in the basket ball court for closing ceremony.

Universitas Indonesia and Parahyangan University.

The Winners

The first overal winner is team Fate, from University of Hong Kong.

The second overal winner is team Extreme, from University of Tokyo
Actually they sat in front of us during the contest, we should've give them "the bread" :D

These are the best 3 local teams. I don't know which one is what team.
The third best local team was ranked 25 with team name Persistence from Ateneo de Manila University.
I somehow got dissapointed because the head of Judge didn't even mention the Top 10 teams.

While we're waiting for the bus to pick us up, we wandered around the campus and eventually got back to the contest site (the theathre) to get the Certificates.

We were back to the theatre where the contest was held. Susu was shocked... Where were all the computers and chairs?
The left pic is the theatre situation when the contest was going on. The right pic is just 2 hours after the contest has ended!?!?
The theatre got cleaned in 2 hours, that's incredible!

IMHO, they were forcing themself too hard on making the theatre as the contest site! If you look at the left picture, there were 3 teams positioned on the stage! This clearly shows that the theatre was too small to fit 98 teams! During the contest, I have to put my papers on the floor because of no place left on the table (in the left picture, you can see that some other teams do the same thing). Also when I swapped seat with my team mates, sometimes I incidentally hit the monitor behind us! Also, I think some network problems for printing for some teams occurred due to their lack of preparation. During the practice session, the printing feature was not implemented! They set up the printer just before the contest! No wonder some teams got printer problems.

All Indonesian team in the theatre room.

The coaches: Win Ce Bong (Binus), Rosa de Lima (Unpar), Yen Lina (Binus), Suryana Setiawan (UI), Sani Mohamad Isa (Untar)

After getting the Certificates and all the team ranklist, we went to the campus entrance waiting for the bus.
Some of us were dropped at Richmonde Hotel, the rest at the Linden Suites.

As we can see, on the left pic, David intentionaly blocked Hannah from going out of the bus for some reason :D

At night we barely found open restaurants! We traveled a long way down the road seeking for food.
Somehow in the street, we found the Fate team. It seemed that they were also seeking for food.
At the end of our starvation, here comes our saviour, Jollibee! We ate as much as our budget.
And came up with the idea of a robber with recipes... ahahhaha!

Day 5, Stay in Richmonde (Oct 30, 2005)

Today we spent our day in the hotel. Some of us swimming, gymning, playing aquarium.
In the afternoon some of us were wandering around mall in the middle of the rain.

Day 6, Take off to Kuala Lumpur (31 Oct 2005)

Right after breakfast at 10 AM, we have to get packed, check out at 12 AM and went back to Kuala Lumpur 3 PM. We arrived at KLIA around 6 and went to Corona Inn, then seek for dinner. It's different from Manila, the night in Kuala Lumpur was bright as day. Many restaurants were open at night.

The left pic is inside the corona inn. The right pic is us eating at gober if I'm not mistaken.
The delivery for the last 3 noodles were too long for Vinix team!

A guy named Stephen Kohar just got his super-mantle that keeping him from freezing.

Do NOT call yourself "binusian" if you haven't done these :D

At the Corona Inn, we played Alien Shooter, a very good game for releasing stress.

Day 7, Wandering Kuala Lumpur (Nov 1, 2005)

We spent the whole day wandering around Kuala Lumpur.
Here is the Menara Kuala Lumpur

Left pic: at the entrance of the Menara Kuala Lumpur. Right pic: a mosqito bite ko Wince.

Left pic: we went to the nearby "food court" along the way to the Twin Towers. We end up eating Mee Goreng at India's place.
Right pic: we took a break before entering the Suria KLCC, the Twin Towers.

Suria KLCC

Left pic: It's a small pond at the back of the KLCC.
Right pic: The opposite place from the pond, a great place to take picture with Twin Towers as the back ground.

Although it's a good place, but it doesn't necessary means that it's easy to get the picture.

A scene where all of us jumped together.

We went back to the Corona inn after buying some souvenirs along the way and stopped by at "Only Mee" restaurant.

Day 8, Fly back to Jakarta (2 Nov 2005)

The last restaurant that we ate in Kuala Lumpur before we go to the KLIA to went to Jakarta.
This restaurant is just in the front of Corona inn.

Before we went to KLIA, we have some photo transference to my laptop. That gave me more than enough material to write up this story. There are 7 different persons that bring along their cameras (Wilhan, Andoko, David, Susu, Wince, Yen Lina, Ing2), only Ing2 didn't do the transference for some reason. I had difficulties selecting photos from the abundance photos in my laptop to be included in this story... but that was payed off. This story is now completed :D Thanks to those who shared their pictures. Btw, If there's any intrusive words I made in my story, please notify me: felix.halim_at_gmail_dot_com