It's been 8 years since Bina Nusantara University got to the ACM ICPC World Finals in 1997, and 1998. After the long waiting and preparation, this year Bina Nusantara University advanced again to the World Final 2007 in Tokyo - Japan.
This year Binus sent 3 teams to compete for ACM ICPC:
- NoMoreAC (Evan Leonardi, Stephen Kohar, and Timotius Sakti) was sent to Manila Regional Contest, got 7th place.
- YoiAC (Andrian Kurniady, Andoko Chandra, and Felix Halim) and ACSlayerS (Cun Cun Lim, Kenny Hartono, Surya Sujarwo) was sent to to Kaohshiung Regional Contest, got first place and 29th place.
Ever since we arrived to Taiwan, bunch of luck coming endlessly:
- There is an Indonesian student in Sun Yat Sen university, William Artan, appointed to be our guide otherwise we would have a serious problem in communications :P
- The compiler and editor used in linux environment really similar with the one I practice for the past 3 months! I didn't found any difficulty at all! Really-really Luck!
Below I wrote the more detailed story for each day of the trip. Note: only Day 2 and Day 3 (MUST SEE) that are related to the ACM ICPC Kaohshiung, the rest of the days are included for the completeness of the whole trip. The pictures was taken from many cameras, so some pictures will look different.
Day 1, Take off to Kaohshiung (Nov 16, 2006)
Early in the morning (9 AM), we assembled in the Soekarno Hatta International Airport.
Left->Right: Felix Halim, Andoko Chandra, Surya Sujarwo, Kenny Hartono, Cun Cun Lim, Andrian Kurniady.
The picture is taken by our coach, Mr. Raymond Kosala.
We flight with Cathay Pacific, transit to Hong Kong for 3 hours before going to Kaohsiung - Taiwan. The food and movies were great, the flight was smooth. When we arrived in Taiwan, we were pick up by the ACM ICPC committees and went to the King Ship hotel with Taxi.
We had some difficulties communicating with the receptionist at the hotel since she spoke too fast and only getting faster, in Chinese!
In overall, the hotel is nice, the only problem is in our bathroom: the water flows very slow and many tiny cockroaches seen :(
The TV is great but I didn't understand a single word coming out from the speaker :P
The best thing I like from this hotel is the unlimited-high-speed internet connection available for free!!
The 7-eleven is just across the hotel, and the "Indomie instan" is so delicious! It has meat (not only seasoning)!
I spent the rest of the night finding files to be downloaded, queue it up, and then went to sleep :D (maklum, orang indo, blum ngerasain internet kenceng).
Day 2, Registration & Practice Session (Nov 17, 2006)
Today is the registration and practice session. We got a souvenir during the registration: a USB Flash Drive 256 Mb.
When Andrian Kurniady took out his camera, the ACM ICPC committees seemed shocked:
"Wow what a marvelous camera he got! Is he a contestant or a photographer?" :P
The first thing I did is open my laptop and check: Is there a Wi-Fi around here? :P
It appeared that this university (Sun Yat Sen Univ) also has free (no blocked sites whatsoever)
unlimited hi-speed internet connection for guests! So, my downloads resumed :D
I think Bina Nusantara should learn from this university about the internet connection! :P
The meeting hall (right picture) is big, it has microphone for every seats.
This is the two teams from Bina Nusantara:
First 3 from Left: The ACSlayerS team, consist of Surya Sujarwo, Kenny Hartono, Cun Cun Lim.
First 3 from Right: The YoiAC team, consist of Felix Halim, Andrian Kurniady, Andoko Chandra
Our team guide was William Artan, he is also from Indonesia (he is our saviour in Taiwan!)
William Artan is in blue at the middle of the picture.
Our Coach, Raymond Kosala, is also in blue at the right.
We went to the competition room for practice session.
We didn't know that Java was not supported until today's practice session but that was not bother us much. Our team, YoiAC, was really fortunate to have Andrian Kurniady that has good experience in linux environment. I was really glad that Kurniady make it easy for compiling and running the program using shell scripts. It was really a coincidence that the compilers and editors was really similar to the one I used during the last 3 month practicing, the G++ and GEdit.
The practice session was not given any problems to practice, but we can still try to submit anything, pick and test the available editors and compilers. We didn't manage to setup Eclipse to compile and run C++ programs :( The replacement is GEdit that has syntax coloring and editing, then compile the source code automated by Andrian Kurniady using shell script ;P
When I went to the rest room I saw the scoreboard at the outside of the competition room. It was intended for the guests, coaches, audiences who want to keep track with the standings. Since this is only for practice, maybe the judge randomly pick the feedback for every submission (either Yes, No, Compile Error, etc...). So Andrian Kurniady "licikin", submit as many source code for every problems, and soon, our team A032 is the champion for the practice session, horray :P
After the practice session was over, William Artan took us to look around the university.
There is a nice beach near the university, and is a really a perfect place for teenagers! (u know what I mean)
William said that the university students really like to see sunsets, it is beautiful.
Here you go, the Baywatch team!
The scene around the beach really fits to a wallpaper.
Sun Yat Sen university also has it's own Soccer field!
I really love this university! Hi-Speed internet, Soccer field, Beach, NICE!
Then we went back to the King Ship hotel, and rest (not forget to resume downloads).
At night, Andrian Kurniady and I made a bet that if we solved problem 302 - John's Trip, then we will be the champion tomorrow. This problem is really bugging me for the last 2 weeks, I cannot get it accepted. When we discuss the problem again, it appeared that I misread the problem statement :P, the starting node is the same with the ending node. If so, then this problem can be solved easily just like problem 10054 - Necklace, it's just an Eulerian Path. And yes, we did get problem 302 accepted! (this is a sign that we'll do well tomorrow).
Another good sign is the seat number. When the seat number was randomized (during the practice session), YoiAC got seat number 32. Andoko Chandra said it means that we are the biggest special numbered team around here. He believes that power of 2 are special numbers (1,2,4,8,..,32,64,..) and since no other team got number bigger than us (no seat number 64) therefore we are the most special :)
Day 3, Contest Proper (Nov 18, 2006)
Today is the competition day. I didn't feel nervous at all, maybe it's because I've been in too many contest or maybe it's because my team members are all cheerful and always make jokes :P
Here is Westlife :P, you all look so cool today guys!
I don't have a coat to wear, but I wear my magical-powered-long-sleeve shirt :D
This gives me Intelligence++, Accuracy++, Awareness++ :P
There seemed to be a mistake in the schedule, we now doing nothing for almost 30 minutes!
Actually the breakfast was too short, I only had the opportuinty to eat cakwe and drink milk (energy booster).
They should give more time to the breakfast time, and lessen the preparation (doing nothing) time :(
The left side is the energy booster for Andrian Kurniady, he will perform well after eating those chocolates!
Then it is the time for the contest proper, we all assembled in the competition room.
Contest Proper
Here it comes, the competition has begun. Kurniady did some settings to the compiler for automating the compilation and run while Andoko and I were searching for the easiest problems. I've to say that this competition went really tight. Let see how we got accepted for the problems and a little description about the problem and how we solved it. The problem statements can be downloaded here. We managed to print out our Accepted source codes and type it again at home, you can download it here. Please keep in mind that the source codes possibly have some mistypes, however it compiles.
The first (Yoi)AC - Problem A - Print Words in Lines - (Minute: 19)
When Kurniady finished the setup, he read problem A, code it immediately, and got it Accepted! I couldn't belive it... That was fast! When we looked at the standings, we were rank 7. It seemed that 6 other teams got the problem Accepted faster than us.
The problem is about how to split the text of N words into multiple lines of maximum M characters. The penalty for each line is the square of the difference between M and the number of characters printed on that line. You've to find the minimum total penalty.
Kurniady solved it using Dynamic Programming (you guessed it! using his special dpmat variable). The DP is similar to LIS but only goes back until up to certain number of words not exceeding M.
Our team morale goes up!
The second (Yoi)AC - Problem E - Route Planning - (Minute: 71)
Let me simplify the problem without making it easier. This problem gives you N(<= 100) cities, its distance among each other as a matrix N x N and M(<= N) selected cities. You have to plan a shortest-distance route that visits all of the M selected cities, print the shortest distance.
When Kurniady was coding problem A, I read problem E and decided to attack this problem using A*. My instinct about top-down Dynamic Programming failed (I cannot come out with a good DP parameters, the DP parameters are so huge!), so I tried using A* and hopes the judges input was not very critical. FYI, A* will either timeout or memory limit exceeded when all of the city distances are equal but will run quite fast when the city distances are randomized! I was gambling then. When I submit it, it got Accepted! What a Luck!
When we look at the standings again, we are rank 3, Yoii... Two teams number 47 and 50 were above us.
The third (Yoi)AC - Problem I - Perfect Service - (Minute: 97, +20 penalty)
Kurniady take over the hot seat, and code this problem. Actually he wasn't supposed to do the coding but it's better than leaving the hot seat empty :P. I then hunting for another easy problem while Andoko assist Kurniady to spot any coding errors Kurniady may type, just like Extreme Programming eh?
This problem gives you a connected graph of N nodes with N-1 vertices (a spanning tree). You have to decide/select K number of nodes as the servers so that any nodes that are not selected is connected directly to one server. Print the minimum possible K.
Kurniady strikes back. He got it Accepted with DP combined with recursion. Here is his explanation for the solution:
The problem I represent a unique class of DP problems, which is about similar to the Rivers task of IOI 2005 (but this one is simpler, of course). The basic characteristic of this problem is that the graph made a tree. We need to traverse the tree deeply while systematically trying every possible combination with a DP approach. Imagining this problem in a linear form will help a lot in finding the DP states and formula. The linear form can be then paired into recursion to achieve a tree-traversing form, which is the solution for this problem. In linear form, imagine each node can have three possible states : it is a server, it is already served by a nearby server, and it is still needing a server. The linear form require a one-way iteration, thus, the tree version require a postorder traversal. Combining the postorder traversal with the DP formula creates an elegant solution to this problem.
The fourth (Yoi)AC - Problem F - Shift Cipher - (Minute: 135)
When Kurniady struggling for Problem I, I found this problem easy. The only concern is the memory, and speed. But that didn't concern me too much, just "hajar bleh" using hash_map :P then look for the outcome :P (actually I did the "WA gak bayar" too early :P, even for Problem E above).
This problem instruct you to read a dictionary (a file located in /usr/share/dict/american-english), and gives you a cipher text. The method of encryption is similar to Rot 13 encryption scheme only that in this problem the rotation can be any number K (< 26). We have to decrypt the cipher text by finding the K. Print the K, and the plain text. The cipher text is said to be decrypted if all resulting text are all in the dictionary. The catch is that if more than one plain text found, we have to choose those having the minimum number of words in the plain text, and if there is a word of length 1 then the next word cannot be of length 1.
I solved it using bruteforce + recursion. I did a bruteforce for all possible K (0 to 25) and for each K, I did a recursion to decipher the cipher text with each characters rotated K times. Each step of the recursion will find a word in the dictionary and checking the length of the previous word. If it found a solution, it will compare the minimum number of words and select the smallest. This kind of recursion will take a long time to implement if I don't know about STL string and STL pair! Thanks to TopCoder community, I learned a lot about STL from each SRM :) You'll never know when your knowledge will come in handy!
We looked at the standings again, and we are rank 1!! This is the first time I see my team name reached rank 1.
The fifth (Yoi)AC - Problem B - The Bug Sensor Problem - (Minute: 162)
This is the only problem that was solved by Team work: Andoko read the problem statement, simplify it to Kurniady. Kurniady "licikin" and decided that it's just a regular MST Kruskal problem. Andoko then told only the necessary thing to me, I then coded it and got it Accepted! I actually didn't have a slightest idea about what is the actual problem about :P. I just code a regular MST Kruskal, it was really easy for me.
If you read the problem again (download the PDF here if you haven't download it above), actually the wording is quite hard. Thanks to Andoko ability to understand hard problem description and simplify it. Basically you are given a set of N points, so it is a graph of N connected components. You have to connect the points until you have M connected components. Print the minimum distance of the last two points you connected.
It can be solved greedyly using MST Kruskal, and keep track of the number of connected components as you merge. You can see the source code, it's really concise and clear.
Before we submit this problem, our team drop to rank 2. The first rank is team number 29 with 5 AC problems. After got this problem Accepted, we regain our position to rank 1. Soon after this many teams also solved 5 problems, however our team has the lowest time and penalty so our rank stand still.
The sixth (Yoi)AC - Problem G - A Scheduling Problem - (Minute: 283)
Wow, look at the minute. It's been idle for 121 minutes before we got this problem Accepted. The audience must be bored to see idle standings for 2 hours :P. In the middle, Lacotix took the first place for solving 6 problems. We know that we need to solve 2 more problems to be rank 1 again. But I were not too stressed because I believe that we can get Problem D accepted since this problems was solved by many teams. Andoko and Kurniady were discussing Problem D while I code for this Problem G.
This problem is a scheduling problem, but was made a lot easier because there is no circular task. In other word, the dependency is a tree-like structure. There are 2 constraints: Conflict Constraint (A task cannot be executed at the same time with a certain task) and Precedence constraint (A task cannot be executed before all its predecesor are executed). The constraints are modelled as (possibly disconnected) a graph with no cycle.
I did a speculation again for this problem. At first, I thought this problem is an A* problem (again, too much coding A* lately). When I jump into coding, I realized that one node can only generate 1 other node, so my A* degenerates become a greedy simulation. It's funny, please look at the source code, the priority_queue is useless :P.
The greedy simulation goes like this: Store all of the tasks that has not been executed and satisfy all precedence constraint in an array. Sort the array based on the "weight" of the task. The weight of a task is the number tasks in the subtree of that task (consider only the directed edges (the precedence constraint) when counting the subtree). Now try to execute one by one the task in the sorted array from the task that has the most weight to the lowest. If the task conflict with the previously executed task, then don't execute the task.
Do the greedy simulation until all task has been executed, and print the number of days needed to execute all tasks.
When we looked at the standings, it wasn't available.
The seventh (Yoi)AC - Problem D - Lucky and Good Months by Gregorian Calendar - (Minute: 284)
When I code problem G above, I was really need to go to the rest room! I was really hungry and thirsty. I held my desire to the restroom until I submit problem G. After I submit problem G, I hurriedly went to the restroom. It is really convenience to go to the toilet, eat anywhere, just like our own home. I love this ACM ICPC contest!
At the toilet, I keep praying that when I get back, I'll heard a good news. Just when I get back to the competition room I can see it from far that Kurniady's and Andoko's were smiling. I was really happy then. Then I hurriedly trashed the problem statements paper that already solved and hurriedly think how to attack problem C. It's just 13 minutes left.
It's only about 1 minute when I got back from the restroom, Problem D got Accepted! Ahhh, I feel really excited! Instead of continuing on problem C, I switched to praying so that Lacotix team doesn't solve another problem :P. Actually I intend to code problem C using super big DP states and see if the Judge's memory is really that big :P
This problem D was coded by Andoko Chandra helped by Andrian Kurniady. This problem already got WA 2 times before it got AC. We intend to do a many "WA gak bayar" to submit every possible combinations of solutions. Try look at the problem description, it's like a novel :(. The first time I see this calendar problem, my morale drops and immediately switch to another problem. Thanks to Andoko, motivated by Ryan Lionel which can calculate the days in his brain, he managed to get it Accepted!
Here is Andoko Chandra coding Problem D - Lucky and Good Months by Gregorian Calendar.
Problem D is an easy-but-long problem description. The problem only asked about how many lucky and good days are there in the specified range of two dates. We have to deal with many nasty rules in Gregorian Calendars :(. Let's end this story before you got bored :P
That's it how we solved 7 of the total 9 available problems.
The contest has ended, the water was drained, the burgers were eaten :P
We got 5 balloons before the standings was freezed.
We go to the rendezvous point again, the meeting hall.
This is when the ACM ICPC Asia Regional Director, Dr. C. J. Hwang approaches our coach, Mr. Raymond Kosala.
Dr. C.J. Hwang talks about his interest in hosting an ACM ICPC Regional in Indonesia! He really liked Bina Nusantara to start preparing the environment to matches the ACM ICPC kind of contest, the PC2, the scoring system, the problem sets, etc... And he believes that many contestants will be willing to travel to Indonesia to compete, the only concern is safety. It's amazing that Dr. C.J. Hwang still remember Mr. Thompson Susabda Ngoen (Bina Nusantara coach in 1997).
Our coach told us about what Dr. C.J. Hwang said earlier.
Now the announcements for the winners begins. Since the number of solve problems differs greatly and there's a large gap for certain rank, the award is slightly changed. Those teams who solved 2..3 problems get Bronze, those who solve 4..6 get Silver, and those who solve 7 problems get Gold Award. It was shocking that 5 teams managed to solve 7 problems! This really is a tight competition, luck factor really plays an important role in such situations :D
The Bronze and Silver awards were given.
There's slight confusion in giving the awards, there's so many teams and
the awarder don't have any idea which certificate goes to which team :P
These are the 5 teams that solved 7 problems: YoiAC, Lacotix, puyo, The Sleeping Beauty, H-E-A-T.
Rank 3 to 5 were mentioned and asked to leave the podium. There's only two teams left:
Lacotix (Shanghai Jiaotong University) and YoiAC (Bina Nusantara University).
And The team who advanced to the ACM ICPC World Finals in Tokyo is...
YoiAC from Bina Nusantara University, Indonesia!!
Going to the ACM ICPC World Finals is one of my dreams.
This is one of the greatest event in my life, I feel really proud :)
Cheers once again guys! The official standings can be found here.
The first place team got these gifts: Mouse Acer (the mouse can shine in different colors, nice!),
DVD -R (25pcs, to burn many movies & pictures), DVD bag (24 slots) and of course..
A ticket to the ACM ICPC World Finals 2007 in Tokyo - Japan.
After the award session, we went to one of the best "seafood" restaurant for dinner.
We need to wait for another bus, and lots of jokes spelled again :)
Any university will look spooky at night (see the right pic).
Itadakimasu...
I don't really like seafoods, but hajar bleh anyway :P
We really enjoyed the dinner.
Who is the girl behind me? So cute, and whose camera shoot this photo? Thanks! :P
I think she is from Shanghai Jiaotong University... :)
Ndok, rugi luh gak kenalan :P, basa basi donk minta minum hahah :P
Soalnya cuma elu yang punya "special ability" untuk ngomong ama dia, trus bawa pulang ke indo (ganas mon) :P
Note: special ability maksudnya bisa ngomong chinese :P
Eventhough I only ate about 40% of the total,
I really appreciate ACM ICPC committee who made this dinner event! :)
Just outside the restaurant there is the Love River.
(This photo was taken by our stylish photographer, see below)
There's so many artists along the street near the Love River.
This is how our stylish photographer, Andrian Kurniady, shoot the picture :P (cool! boleh2!)
The right picture is a statue of a Dragon with fish tail at the back. It is known that after rotating 360 degree,
the dragon will become alive and flying around the sky, sprout fire from its mouth and dive into the water and swim,
then go back to the statue. However that's only in Mr Lim's mind :D
Just before going into the bus to the King Ship hotel, Master Ndok realized that he has lost his passport some where along the Love River. He and I did backtrack to search for the missing passport. After doing DFS several times: check the street, check the policeman at the bridge, check the street again, the passport still couldn't be found. Fortunately, Master Ndok still have a little bit of luck left. William Artan, our savior, talked to the policeman along the street and "pok" the passport is there. Thanks to William Artan!
That's it, now I have to practice again for the World Final.
Preparation we did for this year ACM ICPC
Our team, YoiAC has been practicing regularly twice a week for about 3 months before participating in ACM ICPC Kaohshiung, thanks to Suhendry Effendy and Ing Ing Ang for being our trainer (they were our seniors and also participated in ACM ICPC Regional Manila 2005 with team name "Smart Bee"). This is really helpful for regeneration, passing on the best practices you've learned to your juniors (just like Jedi Masters teach their Padawan).
Aside from the regular training (twice a week), I did a lot more practice by myself. I tried to surpass the limit (just like Super Seiya 1,2,3,4 :P). If you look at my statistics in UVA (open with firefox 1.5 or above or any supported SVG browser), you can see there's an exponential growth of accepted problems (from 600 to 966). It took discipline and sacrifices to achive that kind of growth (I didn't play games, didn't go vacation, didn't watch movies). I bet the other teams who advanced to the World Finals also have the same discipline and sacrifices.
I've been participating in ACM ICPC for 4 consecutive years (see my history menu), so more or less I know the best practices to be successfull in ACM ICPC or any other related programming contest. I believe TopCoders are Born and then Made. When practicing a lot, you will develop your coding style so that your code will be more concise and elegant, easy to fix in case of bug and easy to understand. This kind of practice is really helpful in programming contest where your score will be penalized if buggy (WA bayar). This is one of the factor why YoiAC got so few penalties and beats other teams in penalty points.
Many online contests were held before YoiAC compete in Taiwan, such as (TopCoder (SRMs), UVA, TJU, PKU, etc...). I'm really grateful to those who held online programming contest for I could compare my skills related to others (adu nyali), and discuss the problems. For the upcoming online programming contest schedules can be found in Algorithmist Programming Contest Calendar (thanks to the guys who keep the list up to date).
The End
No comments:
Post a Comment