In the last night before the real contest of the IOI, we simply didn’t know what to do. No internet connection because the leaders were translating the tasks. And because people say that it’s not good to practice one night before a competition, so remove ‘algorithms’ from our mind and tried to play some games. Our (me and Aji) favorite game was O2Jam Offline, because with it we can train our fingers, something that are crucial in competitive programming.
The real IOI had come.
IOI 2010 Rule Changes
This year’s IOI had so many significant changes in the rules, compared to that of IOI 2009. Even the rules were announced in just 6 weeks before IOI, so we had some difficulties to adapt with the new system.
Some of the changes:
- No input/output from keyboard and to monitor. We are required to implement functions that solves the problem. It is very similar to TopCoder SRM, but the functions are not declared inside a class. In addition, a solution may consists of more than one files.
- For each task, the time limit is 10 seconds and the memory limit is 256 MB.
- Each task has several subtasks which have independent points. The maximum points for a task is 100 or even 110 for output-only tasks. To earn score for a subtask we have to get accepted in all testcases of the subtask. So, wrong or weak solutions cannot earn any score.
- Two tokens will be given for each task that can be used to view the final score of a submission (that is, full feedback). Each token will regenerate once in 30 minutes.
- A special tool called RunC is available to automate the process of compiling the source code and testing with all sample testcases, and even submitting the solution to the server.
- A live scoreboard (no freeze time) is available to all people (except the contestants). So spectators in a country can watch how their teams compete in the IOI.
Fortunately, we had practiced with the new system in the training camps before, so the changes should be no problem.
Now, I want to share my solutions of this IOI 2010’s tasks. My score for a task is between the parentheses beside the task’s name.
Contest Day 1
1. Cluedo (100)
This was the bonus task for day 1. My solution was very simple. Begin with calling Theory(1, 1, 1). If the return value is 1 the increase the first parameter (murderer), if 2 then increase the second parameter (location), and if 3 then increase the third parameter (weapon). Because there are 6 murderers, 10 locations, and 6 weapons, the maximum number of calls will be 5 + 9 + 5 plus 1 for the final answer = 20, sufficient for solving subtask 1 and subtask 2.
2. Hotter Colder (50)
I used some kinds of binary search algorithm. I needed 2 Guess() calls to halve the search space. So, in total I needed 2 x log(500) = 18 calls, which were sufficient up to subtask 2. I didn’t have any idea to decrease the number of calls during the contest.
3. Quality of Living (60)
I had solved this kind of task (online median finding) on SPOJ. The way is to create 2 priority queues, one max-priority and another min-priority. Their number of elements must differ by at most 1. The median is then simply the maximum element of the first priority queue.
In this task, I obtained an O(N^3 lg N) algorithm, where N = max(R, C). My solution was sufficient to solve up to subtask 3.
4. Languages (99)
The problem statement is very vague. Simpler statement: Given a sequence of excerpts from Wikipedia, guess the language. We will also be given the correct answer after guessing. The higher the solution’s accuracy, the higher the points.
This problem is about implementing good heuristics of guessing function, very similar with TopCoder Marathon Matches. I had participated in some marathon matches before, so I didn’t get shocked with this type of problem. I implemented many heuristics: character-by-character matching, bigram and trigram with the ‘weight’ of each, etc. After tweaking the solution many times, I earned 99 points, which was very satisfying.
Contest Day 2
1. Memory (100)
A bonus task. Call faceup() 50 times to get the letters of all cards, then call faceup() 50 times again for each pair of cards that have the same letter.
2. Traffic Congestion (100)
Maybe this was supposed to be an easy-level task in this IOI, but many contestants considered that this task was too easy for IOI. My solution was only a modified DFS in tree.
In less than one hour, I got this first two tasks accepted.
3. Maze (64)
An output-only tasks. It is about creating a maze in a map such that the shortest path to the farthest square is maximum. For subtasks with small maps I implemented a plain brute force solution which earned full points. For large maps, I took some random sample entrance points, and ran a highly pruned brute force from those points.
4. Saveit (50)
This is the most interesting task, I think. We have to encode the all-pair shortest path information in a graph as efficient as possible because we have only limited number of bits. It was very easy to score 50 points; just send the information as is because each edge needs only 10 bits.
Because I thought I wouldn’t be able to get full points in this task, so I allocated the remaining time trying to solve Maze.
Right after the end of each contest we went online in notebooks or mobile phones to examine our ranks in the scoreboard. On the first day, I and Aji almost got silver medal positions, while Chris in a good bronze medal position. Unfortunately, Harta had some bugs in Hotter Colder task, so he only earned 25 points for the task.
On the second day, Aji and I again got silver medal position, Chris in a bronze medal position, and Harta in the boundary of bronze and non-medalists.
Of course I hoped that all Indonesian contestants got medals. Although the score had been published, there was still an appeal phase, so the result was not decided yet.