Well, this is my third participation in an ICPC regional. This time we as Saklar Lhompat team participated in Philippines, in Manila site. This is also my second time to participate in a foreign site, as (unfortunately) Jakarta didn’t host a regional this year. University of Indonesia had also sent two other teams (Vidina and Algorythmists) to Kuala Lumpur site this year.
Honestly, we expected to become a world finalist this year :D. We had participated in nearly all college national programming contests before, and got pretty nice results. Each of us also practiced regularly in online judges, me especially in TopCoder (SRMs). So, we hoped that we got some luck and succeeded this year.
We were assigned a new coach, Denny. He participated in an ICPC regional in around 2000’s. My teammates were also the same as the previous year, i.e., Alham Fikri Aji and Berty Tobing.
The teams were selected by choosing the top 3 teams from my university in Indonesia National Contest. Then, our team was selected to participate in Manila, while the two other teams were selected to compete in Kuala Lumpur.
I told Ilham Kurnia, my programming contest trainer, that we were going to take the Manila regional. He immediately warned me that from his previous experience in competing in Manila twice, this site was always badly organized. The problem statements were ambiguous, the clarification was not so helpful, etc. So, he advised us to anticipate for every bad things that might happen during the contest.
We flew to Manila by Philippine Airlines. It took us about 4 hours to arrive in Ninoy Aquino Airport. Then, we took a taxi to get to our hotel, The Oracle Hotel in Quezon City. We could communicate with people easily as English is one of the national languages in Philippines, besides Tagalog. We didn’t feel like being abroad so much because the weather, the people faces, the traffic, are very similar to those of Jakarta.
We arrived in Manila one day before the contest days, so we were supposed to take enough rest for the next day. While I was lying in bed, surfing the internet, I accidentally ran into a blog of Raffy Saldana, the Manila Regional Contest Director. In his blog, Raffy posted the rules of a team notebook, which are rather hard to prepare (25-page letter-sized notebook, packed in a two-hole binder with 4 dividers, etc.). The annoying thing was, why he didn’t post it in the official Manila regional website.
The official website was way very simple and less informative. Before we departed, it didn’t say anything about the notebook, so we assumed that any simple 25-page notebook will do. After reading the blog post, bought all necessary materials in a bookstore.
The contest was held in University of Philippines Diliman. We had the opening ceremony in a large hall inside one of the university building. The opening ceremony was quite usual. We were in the same table with a Chinese team. They provided snacks, ice creams, and even a performance of two jugglers. The jugglers were very entertaining. But later, I found that this performance was the only nice thing of the contest!
There were many unusual things that I noticed. The first weird thing was… there were no runners/escorts for foreign teams!
Secondly, the MC for the opening ceremony often talked and joked in Tagalog, so foreign teams had no idea what he was talking about. His voice wasn’t loud enough to hear from the back.
Thirdly, the organizers requested us to fill a (very simple) form asking for our emails and T-shirt sizes. This is weird since this information should have been available in our profiles in ICPC website. I couldn’t understand. They had the team names, but they didn’t have the emails and T-shirt sizes.
After the opening ceremony, they picked us up to another building used for the practice session and of course the contest proper. We moved there by Jeepney, a local public transportation in Manila.
We entered our assigned room. The practice session and also the contest was not held in a large hall; just in ordinary classrooms installed with workstations. The bad thing was that each workstation table was too small for three persons and the gap between teams was too narrow. We were afraid that we might accidentally touch or break another team’s workstation.
So, the practice session began. We were given only a single task. The task was simple: You are given several test cases, each containing two nonnegative integers and an arithmetic operator (+, -, /, or *). For each test case, output the result of the expression. If the operation cannot be carried out, output “INVALID”.
The first bad impression was that the problem statement didn’t specify any constraint for the input! When one of the team asked for clarification, the judge said something like “assume a typical range for the constraints”. What? How could we know what the judge meant for “typical range”?
Finally, the judge broadcast additional clarification that the operands will be between -2,000,000,000 and 2,000,000,000. Even the clarified constraint was inconsistent because the statement said “nonnegative integers”. So, the judge corrected his previous clarification and then sent out another clarification that the operands will be between 0 and 2,000,000,000.
The statement also didn’t specify how to do the divide operation: integer division or real division? They had to sent many clarifications to finally make this problem unambiguous.
After we completely understood the problem, we coded the solution. Another unusual thing was that the input must be read from file, not from stdin. We submitted several times to the PC^2 interface. We waited and waited, but none of our submissions was judged until the end of the practice session! When we looked at the other teams’ monitors, it seemed that there were very few of our submissions that got judged. So what’s the point of this practice session? We couldn’t test the time limit, grader’s stack size, etc.
After the practice session was over, we handed in our team notebook. Apparently, they also accept plain team notebooks, i.e., without binder and tab dividers. Okay. They also gave the T-shirts. The T-shirt looked bad; it was only a plain white T-shirt with “ACM-ICPC” printed in it, without naming “Manila”, “2011”, or “University of Philippines”. Some contestants even received T-shirts with wrong sizes because they ran out certain sizes. Some coaches also received T-shirts with different colors. It was ridiculous.
Ah, there was also no excursion.
All teams gathered in front of the contest building on 9:00 AM. Although the contest program (printed in a plain yellow photocopy paper) stated that there should be an assembly meeting on 9:00 AM, no instruction was given to the teams. There were no escorts, so the teams ended up in confusion. So, all teams took initiative to enter their assigned room without instruction.
We sat down in our desk. The contest was planned to begin at 9:30 AM, but they were so slow in distributing the team notebooks so the contest was delayed. The real contest finally began at around 11:00 AM. In our room, the assigned contest proper runners were upset when we told them that the contest had begun (we simply noticed that the timer in PC^2 had started). After we told so, they started distributing the tasks to all teams in rush. In effect, the contest started late in our room for about five minutes.
Another strange thing: no available scoreboard for the contestants! This was my first international programming contest without scoreboard.
There were ten problems in the contest. Almost all problems required very difficult input parsing.
You can download the “underground” version of the problemset here, thanks to a local team who posted it on TopCoder Forum.
A. Student Life
A very easy problem, just a simple sorting problem based on several keys. The real challenge lies in parsing the input. The input format is very difficult. Another big challenge is to guess what output format the judge wants (!), because the output format section only says, “For each test case, output the arranged appointments accordingly”. Examining the sample output is not very helpful, as there are still some ambiguities, like whether we should output a blank line between test cases or after each test case, and in which appointments the “(Conflict)” mark should appear.
To resolve those ambiguities, we just gambled! We submitted, and got “Yes” response after like 20 – 30 minutes. The judge was so slow.
B. Ant Maze
This is also an easy BFS problem. This problem asks to find a path in a maze from the entry point to the exit point. The problem is that the problem statement doesn’t specify the constraints on R and C, the size of the maze. When a team asked for clarification on this, the judge replied, “assume that R and C fit in 32-bit signed integer representation.” This should be an impossible upper bound; how to store an array of 2 billion x 2 billion characters?
Later, the judge corrected the clarification and said that 1 <= R, C <= 200, a reasonable constraint.
We also got a “Yes” response on this problem.
C. Gaussian Integers
A math problem about complex number theory. None of us had learned complex number thoroughly, so we just skipped this problem.
This problem asks for GCD(s) of two complex numbers. Weirdly, the problem doesn’t define explicitly what “greatest common divisor(s)” in complex field is.
D. Top Rank in Rectangular Array
This should be a usual simulation problem using priority queue. For each number a in the list, we add to the priority queue a, a/2, a/3, …, until it is less than the requested integer.
We also got a “Yes” response on this problem.
E. The Chipmunks’ Christmas
This is a controversial problem. The problem seems to be easy. In a nutshell the problem simply wants us to convert a number into a special number system: 1, 2, 5, 6, 7, 8, 9, 11, 12, 15, …, 21, 22, 25, …, 111, 112, and so on. Since the input N is at most 500,000, we can simulate the number system and store the precomputation in an array. So, for each test case we can simply output the precomputed answer.
We got “No” responses many times in this problem though we were like 99% sure about the correctness of our solution. Later, it turned out that the judge’s solution was wrong!
F. An Arrangement of Sorts
The very small constraints of this problem (at most 8 x 8 grid) should be a hint that the problem is to be solved using pruned backtracking. It was indeed the case. We solved this problem using a simple backtracking without any fancy pruning, and it ran fast on several random large input.
We got a “Yes” response on this problem.
G. What will I Ride?
We didn’t have enough time to attack this problem, because we spent much time for problem E. Although the problem statement is rather ambiguous (lacks many required definitions), it should be a modified Dijkstra/Floyd Warshall with convex hull. We think we should have solved it if we abandoned problem E.
H. Balanced String
Aji solved this problem using dynamic programming. His state was (current string length, current difference of 0s and 1s, minimum difference of 0s and 1s so far, maximum difference of 0s and 1s so far). His solution worked perfectly for sample cases but not for large cases (it overflowed), so I convert his source code to Java to allow using BigInteger class.
We got “Yes” response for this problem.
The most ambiguous problem in the contest. No constraints at all. The input and output format section do not match with the sample input and output. Indeed all sample outputs were wrong! These were caught by some teams during the contest.
J. Hollow, Non-Hollow
This problem is also ambiguous. The statement doesn’t define precisely what “empty spaces inside” means, and what “disjoint figures” means. We tried no to assume to much and coded a simple DFS solution, and it got accepted.
We got “Yes” response for this problem.
In total, we solved 6 problems in the contest. We thought we could have solved 7 (+ Problem G) if Problem E were fine 🙁
The closing ceremony was held outside the campus canteen. It was really a very simple closing! No stages, no performances, no MCs. That was a shame for an international contest. They provided late lunch dishes, but some teams (us too) sat down in the floor because they ran out of tables.
So, the winners of the contest are:
#1. STAFF (University of Tokyo, Japan) (rng_58‘s team)
#2. Quiwarriors3 (University of the Philippines Diliman)
#3. ~~(Q_Q)~~ (National Taiwan University, Taiwan)
After the closing, we discussed with other teams about the controversial Problem E. It seemed that the problem indeed suspicious. Even the winner couldn’t solve it in-contest.
Our coach and several other teams sent an appeal email to the Marsha Poucher and Raffy Saldana regarding Problem E. We asked for rejudge for the problem.
Several days later, the official Manila Regional website posted the updated ranking. We Saklar Lhompat finally ranked 4th, solving 7 problems! But we lost to a local team, so the chance of advancing would be too small.
Despite getting increase in ranking, we thought that the rejudge is unfair, because they rejudged all submissions, including the submissions that got accepted during the contest. So, some teams got decrease in number of solved problems.
One day after the contest, University of Philippines Diliman teams invited Indonesian and Japanese teams to a small private “excursion” around the Manila city. Eric Tambasacan, the coach assistant, said that the excursion was as an apologize to foreign teams for the badly organized contest. We went to Rizal national park, national cathedral, and ended up with a nice dinner in a nice cafe.
Ilham was right; the contest was very badly organized. Nevertheless, we got some improvement this year. This (4th) is our highest rank in ICPC regionals 🙂