The Sixth International Olympiad in Informatics:
A Trip Report
3 - 10 July 1994, Haninge, Sweden

Contents

Introduction

The sixth International Olympiad in Informatics (IOI) in Sweden was attended by a large Dutch delegation (see Table 1), for the simple reason that the Netherlands will host the seventh IOI in 1995. This document summarizes my experiences at IOI'94. I pay special attention to those aspects involving the Scientific Committee (SC).

Name                         | Role at IOI'94          | Role at IOI'95
-----------------------------+-------------------------+-------------------
Jaap Beetstra                | Student                 |
Edwin Woudt                  | Student                 |
Marja Vreugdenhil            | Student                 |
Mareille Ypma                | Student                 |
Ries Kock                    | Team Leader             | General Manager
Anne Marie van Schoonderwalt | Deputy Team Leader      | Team Leader
Willem van der Vegt          | International Evaluator | Member SC
Jacco Gnodde                 | Observer                | Member SC
Ard Hartsuijker              | Observer                | Financial Manager
Ron Helwig                   | Observer                | Technical Manager
Franka van Neerven           | Observer                | PR Manager
Ria van Ouwerkerk            | Observer                | General Manager
Kim Schrijvers               | Observer                | Deputy Team Leader
Tom Verhoeff                 | Observer                | Head SC
-----------------------------+-------------------------+-------------------
Table 1: Dutch delegation at IOI'94
This picture shows part of the Dutch delegation.

Arrival Day

Most teams arrive on Sunday July 3 by plane at Arlanda Airport 30 km north of Stockholm. There they are awaited by hosts and guides in white short-sleeved shirts with a colorful IOI back print. Some guides run around with the IOI poster on a long wooden pole. Unfortunately the poster is not very recognizable (we had never seen it before and we were not told what to look for). Each team is assigned a guide for the remainder of the week; ours is a sociable black guy named Axel. Special buses take us from the airport to Haninge, 20 km south of Stockholm.

All students are put up in the luxurious Hotel Najaden. A hilarious situation arises when the elevator ``refuses'' to take some students to the fifth floor. It turns out that the hotel is built on the side of a cliff, the main entrance being at the fifth floor already. Behind the hotel, across the railroad, is a nice lake where one can go for a swim. On the map of the IOI'94 arena you can see the relative location of all the important sites.

The hotel is at a few minutes walking from Riksäpplet, the active center of the olympiad. Here we register and receive information leaflets and badges (besides my name, it showed a conspicuous VISITOR and a cryptic NLD). Riksäpplet is a modern building, white and glassy. It houses a college associated with the Kungliga Tekniska Högskolan, KTH (Royal Institute of Technology). The main part of the building has a square footprint. The offices and classrooms are located on the four sides of this square. The interior contains a central column with elevators and stairs. On each floor four walkways connect the central column to each of the four sides (all entrance doors have a card-and-code lock). Apart from the central column and walkways, the interior is a vast empty space.

The accommodation for team leaders and visitors is in two apartment buildings where normally students live. On each floor there are some six small rooms with toilet and shower, one large kitchen, and one living room (often with TV but no telephone). The organization has bought a number of additional beds so that two people can share a room. The walk to Riksäpplet passes the hotel and takes about 15 minutes.

Lunch and dinner are served in the cafeteria of Riksäpplet; both are warm meals with a choice between vegetarian, meat, or fish. The students have breakfast at the hotel; the others at Folkets Husset, which is located just before the hotel on the way from the apartments (Riksäpplet, Hotel Nayaden, Folkets Husset, and the apartments are collinear; the apartments are further away than shown in the map).

Later that day I briefly meet Håkan Strömberg (48), head of the SC. His advice to me: ``Never do this for the first time; all your nice plans will fail already on the first day.'' For team leaders and visitors there are three rooms (in Riksäpplet) with computers having e-mail facilities (and all the olympiad programming languages). There are also several rooms with practice machines for the students (these are not the competition computers).

The World Cup '94 (soccer) does have a noticeable effect on the olympiad, though many also ignore that event completely.

Opening Ceremony

The opening ceremony is in the (small) entrance hall of Riksäpplet. Many people crowd the walkways on several floors between the central column and two of the four sides of the building. Cameramen have a hard time squeezing in as well. Halfway towards the (high) ceiling a net full of colored balloons waits patiently. Below, Johannes Dominique (15), special IOI composer, sits at his computer (an Apple Macintosh SE/30) and synthesizer. He composed the music, called IOI Fanfare, for the opening and closing ceremonies.

First, there are some (fortunately, short) speeches. The most interesting were by the mayor of Haninge and the director of Riksäpplet. Then, synthesized trumpets loudly play the IOI Fanfare (or did this precede the speeches?). On a second piece of music the flags of all participating countries (except Taiwan, because China objected) are carried in and placed in stands. Later, I am told that the flag-parade music is derived from all the national anthems, but that during the performance, due to some timing mistake, this did not work out as intended (I have not recognized our national anthem the Wilhelmus).

Of the 52 invited countries, four do not show up, and there appears to be one additional participant. Thus, a total of 49 countries are represented at IOI'94. Most countries send four students; the exceptions are Cuba (3), Cyprus (3), Japan (2), Luxumburg (2), and Slovenia (3). Altogether there are 189 students in the competition, nine of whom are girls.

After the flag parade, the balloons are cut loose to descend on the masses, who gladly trample them (what a noise and what a mess). A drink completes the opening ceremony. We then have an early lunch. In the afternoon we go to Stockholm for a boat tour. Stockholm is built on 14 islands, has 1.4 million inhabitants and 250,000 boats.

In the evening, leaders and students can inspect the 204 competition computers (hardware from AST: 33MHz 486 processor, 8MB RAM, 210MB hard disk; software: DOS 6.2, Turbo Pascal V.7, Turbo C++ V.3, Quick Basic V.3, Logo V.3). These computers are located in six classrooms, such that students of one country will be in separate classrooms. I track down the computers for the Dutch students; they are easily found with the help of a list and large stickers on the tables. Apart from a slight problem with Logo everything seems to be in good working order. What I do notice is that the keyboard and DOS are Swedish versions. During the inspection, the organization distributes three pages of advice to the competitors. Unfortunately, troubles with two copiers lead to a shortage of the second page, which is, of course, the most important one.

First Jury Meeting

At 22:00 the first meeting of the International Jury (IJ) takes place in a small lecture hall of Riksäpplet. For each country two adjacent seats with writing space are reserved (the miniature flags are removed when China objects again to the Taiwanese flag). We are immediately confronted with some surprises.

The meeting is opened punctually even though not all members are present (true, the meeting time was clearly announced, but not the location). We are warned that subsequent meetings will also start exactly on the time advertised; this is a good point. Here are some lesser points. It is not sufficiently clear who is chairing this meeting (I expect the chairperson to be ``neutral''). There appears to be no agenda. Microphones are present but not used.

The voting machine (claimed to be developed especially for the olympiad) is a story in itself. For each country there is a hand-held control device with three buttons (yes, no, reset) and two feedback lights (yes, no). All devices are attached to a central computer that counts the votes anonymously. An ill-positioned small monitor displays the remaining voting time (you get 30 seconds) and, when that time is over, the total yes/no counts. We vote several times about the voting machine itself (`Are you willing to use it?'). Depressing neither button `yes' nor `no' is the way to withhold your vote. I wonder what happens when you depress both `yes' and `no' (in that case, both lights come on). My watch tells me that the machine's 30 ``seconds'' elapse in about 25 seconds.

Question time. There are plenty of questions. The atmosphere is tense but not hostile.

Why are the competition computers equipped with a Swedish keyboard and DOS? It turns out that the computer supplier pulled out six weeks before the olympiad (the supplier was taken over by another company that did not feel bound by the earlier promises). Therefore, the organization was forced to harvest computers from all over Sweden. These machines had a Swedish keyboards and DOS. Nothing can change that now. It is agreed that the students will get 15 minutes to re-letter their keyboard (with paper and glue) and to reconfigure DOS for a U.S. keyboard layout. They may ask for help when DOS speaks Swedish (mostly error messages).

Grading is done by a program which looks for an executable file with the correct name, but Logo does not produce an executable file. How will Logo programs be graded? Logo programs will be graded in a ``special'' way (only the two Dutch girls appear to be using Logo).

In an earlier meeting, it was agreed that when execution time limits are imposed, these will be scaled depending on the programming language used. These scale factors are not mentioned. How about them? The organization had decided that the languages C, Pascal, and (compiled) Basic are sufficiently equal in speed that no scaling is necessary. They did not give convincing arguments, however. At first, Logo (an interpreted language) was given a scale factor of 2.5, but this was changed to 6 (under protest). Again, it was not clear what kind of experiments they had performed to get these scale factors.

In what directory will the input file INPUT.TXT be put by the grading program? In the same directory as the executable file. The student program need not supply any directory information when opening the file, since it appears in the default directory.

It is stated that programs should not write anything to the screen. Is there a penalty for doing so, or will such output just be ignored? The grading program only looks at output in the file OUTPUT.TXT. Output to screen and other files will be ignored. There is no penalty.

Are students allowed to bring their own scratch paper? I have students who want scratch paper ruled in squares. Scratch paper will be available, also ruled in squares. Students may not bring their own.

Concerning the execution time limit imposed by the grading program, will the student (program) know when to output the (best) solution found so far (before the time-out expires)? There have been endless discussions about this last year in Argentina. For each problem the grading program exercises the student program with a number of test cases (of increasing difficulty). The execution time limit is fixed for each problem and does not depend on the input data. After some talking back and forth it is agreed that this time limit will be made known to the students. It turns out that in Argentina, there was an assignment that asked for optimal solutions. There had been students who interrupted their program just short of the execution time limit, and who output the best solution found so far. Sometimes that turned out to be optimal and would get points, even though the output was, in a sense, just a guess. If this practice is allowed, then it should be known to all students. Right after the meeting, there was a discussion in a smaller group who objected to this practice and tried to put an end to it by adjusting the grading procedure. In essence, they wanted to randomize the execution time limit so that the student program cannot know when to break of prematurely. However, this approach does not help. (We clearly will have to think about this problem for IOI'95. In my opinion, there is a subtle distinction between an execution time limit that is part of the specification and one that comes in as a grading artifact. Furthermore, some aspects cannot be ascertained by testing only.)

Will the number of points for a program that is judged to be correct depend on the actual execution time? That is, will more points be awarded to faster programs? No.

Not all competition computers are configured the same way; for instance, there are machines with 4 MB RAM and 8 MB. This may affect execution speed. Are you aware of that? All programming languages use only 640 KB. Use of the extra memory is impossible, or at least sufficiently hard to be of any use.

What about swapping, some new language implementations allow that? (My records do not show a satisfactory answer to this question.)

Are subdirectories needed on the floppy disks, just as they appear on the hard disks? No, the floppy disks are only a backup medium. They will be used only in case the hard disk on the student's machine breaks down. They are allowed if you prefer to use subdirectories.

Does each input file contain only a single test case? Correct.

Is there a CR at the end of the input file? Yes, the last input line is terminated by a CR.

Can the windows of the classrooms be shaded to avoid screen glare? Yes.

Can the output file be inspected manually during grading, if necessary? Yes.

Can the supervisor in the classroom help a student with Swedish error messages from DOS? Yes, of course, we already said so.

What kind of equations and figures appear in the problem statements? Will we get the English version in electronic format? There are no complicated equations. Figures will be numbered in the English version. You are advised to refer to these, as the students will also get an English version of the problem statements. In principle, you can get electronic versions of the figures, but these are not likely to be of much help, since you have to be able to cope with the format.

Do figures contain (English) text? Possibly. You might use Typex on a photocopy to replace it.

First Competition Day

Some of us have to get up at 5:30 (meeting the Midnight Sun) and grab breakfast at 6:15, in order to attend the 7:00 o'clock meeting of the IJ in Riksäpplet.

Second Jury Meeting

The purpose of this second jury meeting is to determine today's assignments. At previous IOIs, the SC presented an extended problem set and the IJ voted to select that day's problems. Apparently, this was a time consuming process, where all sorts of irrelevant arguments also played a role (such as leaders trying to eliminate problems they expected to be too difficult for their students).

This year, the organizers spring a different approach on us. They present their proposal for today's problem set, consisting of three problems that were carefully selected by the SC (to be of varied style and difficulty). There are two back-up problems, but these will only be revealed in case of a calamity. Instead of a time-consuming discussion on which problems to include and which to drop, most time is spent on discussing the procedure itself. Finally, we vote about each of the problems (using the voting machine, whose monitor is now better visible, though its notion of time hasn't improved). It turns out that there are no major objections and the proposed problem set is accepted.

There is some discussion on the formulation of the problems. The formulation is very concise (no more than one two-column page per problem). Furthermore, it relies on the willingness of the reader to generalize from an example to the general case. In particular, input format, output format, and execution time are recurring topics. Concerning execution time, the SC does not specify a maximum but a range. For instance, for Problem 1 the maximum execution time is in the range from 20 to 30 seconds. They say this is to prevent students from using a timer to end their program prematurely. The IJ objects on the grounds that this was discussed yesterday and that the SC had promised to give a single execution time limit. The SC agrees to adopt the maximum of the range. The SC also confirms that the test data they use for grading always satisfy the input restrictions of the corresponding problem and that there is always at least one solution for that test data. After these relatively minor issues have been settled it is time to start translating (it is now a little past 8 o'clock).

Here is a summary of the number of test cases, points, and execution time limits for each problem:

problem | # tests  points/test  seconds
--------+------------------------------
   1    |    6          5         30
   2    |    5          6         30
   3    |    4         10         90

Translating the Problems

All people attending the jury meeting are confined to that part of the building where the ``translation'' computers are located (the one's with e-mail facilities for leaders and visitors; e-mail is blocked, of course). Apart from a Swedish version of DOS, these machines also have a Swedish version of Word. A helpful technician writes a short Swedish--English Word dictionary on the white board. For several countries the word processor is of no help anyway (Chinese, Thai); the Russians apparently brought their own. Some countries do a joint translation. Even the Americans produce a ``translation'', which they call a clarification.

The Dutch translation is no big deal. One person types in a fairly literal translation directly from the English version. No attempt is made to redo figures. The first draft is printed and then marked up by someone else. In the meantime, we get new printouts of Problems 2 and 3, whose formulation has been adapted slightly. The translations are carefully screened once more for silly mistakes and ambiguities. At about 10:00, we are done. The competition will start at 12:00. We will be stuck here till 13:00, because native-language questions from the students may arrive during the first hour of the competition. There are only a few questions, none for us.

Solving the Problems

After the translations have been handed in, I use the computer to program my solutions to the three problems. At times, Willem looks over my shoulder and provides some feedback.

Problem 1 (The Triangle) I find really easy. Given is a triangle of numbers, line $k$ consisting of $k$ numbers. Consider all paths from line 1 at the top to line $n$ at the bottom, where each step in such a path goes from one line to the next, either diagonally left or right (from position $p$ on line $k$ to either position $p$ or $p+1$ on line $k+1$). Thus each path takes $n-1$ steps and there are $2^{n-1}$ paths. The objective is to find the maximum sum of numbers along any path. In the following five-line triangle, the maximum is 30, and it is obtained along the underlined path:

          7
          =
        3   8
        =
      8   1   0
      =
    2   7   4   4
        =
  4   5   2   6   5
      =
Trying out all paths is a very inefficient way to solve it. No doubt some of the test data will make such an approach exceed the execution time limit ($n$ could be as large as 100, the time limit is 30 seconds).

Problem 2 (The Castle) is slightly harder, but still nothing special. Given is the map of the interior of a rectangular castle. Wall segments partition the castle into a number of rooms. The objective is to determine (i) the number of rooms, (ii) the area of a largest room, and (iii) a wall segment such that its removal creates the largest room possible. For example, here is a castle map:

  +-------+-------+-----------+
  |       |       |           |
  +---+   +---+   |   +---+   |
  |   |       |   |   |   |   |
  |   +----   +---+   +---+   |
  |           |   |   |   |   |
  |   +-------+   +---+   |   |
  |   |                   |   |
  +---+-------------------+---+
This castle has five rooms, the area of the largest room (on the far left) is nine modules (the other areas are 1, 3, 7, and 8), and removal of a wall segment between the 9-module and 7-module room creates the largest possible room.

My first attempt contains a ``nice'' bug. It creates the largest room by joining a room to itself, which then is interpreted as a new room with double the area. I tacitly assumed that a wall segment separates two (distinct) rooms. Fortunately, the example included in the problem formulation attracts my attention to the possibility of a wall segment with the same room on either side. (This could have been better hidden by the problem composers!)

Problem 3 (The Primes) is considerably more complicated. Given two integers $s$ and $d$, find all possible ways to place (decimal) digits in a 5x5-matrix such that (i) the numbers formed by the five rows, the five columns, and the two main diagonals are primes (rows and diagonals read left to right, and columns read top to bottom), (ii) each prime has digit sum $s$, and (iii) the top left-hand corner contains digit $d$. Here is an example for $s=11$ and $d=1$:

  +---+---+---+---+---+
  | 1 | 1 | 3 | 5 | 1 |
  +---+---+---+---+---+
  | 3 | 3 | 2 | 0 | 3 |
  +---+---+---+---+---+
  | 3 | 0 | 3 | 2 | 3 |
  +---+---+---+---+---+
  | 1 | 4 | 0 | 3 | 3 |
  +---+---+---+---+---+
  | 3 | 3 | 3 | 1 | 1 |
  +---+---+---+---+---+
Of course, when $s$ is a multiple of 3, there are no solutions. My first program is too slow for the test case shown above, but further refinements bring it within the required limit. Later, I hear that the judges' programs cannot solve the case $s=23$, $d=3$ within the time limit (there are 757 five-digit primes with digit sum 23, of which 101 begin with digit 3).

Altogether this day is not too difficult, though you have to get all the nitty-gritty details right within those five hours.

Judging the Programs

At 17:00 the students come back. Our boys are rather optimistic (claiming to have solved all three problems), but the girls are not. Judging is done by running the programs for several sets of test data, carefully chosen to be of increasing difficulty (whatever that may be). Each successfully passed test gives a fixed number of points (regardless of ``difficulty''); the number of points depends only on the problem.

Testing is automated. The evaluator inserts a test disk and runs a test program. The test program finds the right executable, copies the first test data to file INPUT.TXT, starts the executable, and keeps an eye on the stopwatch. When the execution time limit is exceeded it terminates the program-under-test. Otherwise, when the program-under-test terminates in time, it checks the output in file OUTPUT.TXT. This is repeated for each set of test data and for each problem. The number of points awarded is shown on the screen and written on a form by the evaluator. In case of partial or erroneous output, the test program provides some more details as to what type of mistake was made. The output file can then be inspected manually for further clarification.

For each test case, the evaluator awards either all points or none; there is nothing in between. Controversial cases are postponed and will be discussed by the SC tomorrow. For instance, what if the program for Problem 2 (The Castle) produces the right number of rooms and largest area, but fails on the third item? Is it fair to award zero points for all test cases or should some, though not all, points be given?

It is a delight to see Jaap's programs being judged. His programs are quick and correct, except for the final test case of Problem 3 (The Primes) which exceeds the execution time limit (of 90 seconds). Possibly his program did find some of the solutions (there were three for that case), or maybe even all solutions but it was still exhausting the remainder of the (empty) search space. It is for problems like this one, that the use of a timer might help, though it then becomes a form of guessing that should not be condoned. Jaap acquires 90 points (out of 100). Not bad at all.

Edwin is less fortunate. For one thing he had not noticed that efficiency is important for Problem 1 (The Triangle), and indeed his program fails for the three larger test cases. Another oversight is that for Problem 3 (The Primes) he had forgotten to switch the output from screen to file. This means no points for that problem. On Problem 2 (The Castle) he must have made some silly error, because his program suggests to remove a wall segment that is not even present. Edwin takes 33 points on Day 1.

The girls explain that they suffered from I/O problems with Logo. Testing for their programs is done in a special way, but they still get zero points.

Judging is fairly rapid. About 20 members of the SC also act as evaluators. They start at about 18:00 and are done by 21:00. This proves that automatic testing can get the results quickly and with few evaluators. At the end of Day 1, it turns out that 11 students have a perfect score, but there are also 25 with the minimum score.

Ericsson Day

Today we get up at a more decent time. In the morning we go to a research facility of Ericsson, an international telecommunications giant. It is located just north of Stockholm, in the Swedish equivalent of Silicon Valley. We are seated in a spacious lecture hall, where the stage is set by a middle-aged man in a suit. His introduction is as dull as can be (possibly on purpose to create a bigger contrast with the other speakers).

The first real speaker is a casually dressed American fellow (a professor it turns out), talking about his Walkstation Project. A walkstation is a walkman-sized workstation that continuously connects to nearby networks while it is moved about. In his lively presentation he emphasizes that this project requires experts from many diverse fields, computing science being one of them. I am afraid that the talk goes unappreciated over the heads of the students. When asked, he admits that a few more years will go by before you can buy a walkstation in your local supermarket (some infrastructure is also needed).

The second speaker arrives late, is young, wears a tie and jeans, and is even more agitated than number one. He will tell us about robots. No, not those poor factory robots with only a few degrees of (motion) freedom. He pulls a six-legged cat-sized orange creature from his backpack and puts it on the table, where it starts to walk about noisily. These robots are not very interesting, he assures us. His love is for amorphous robots. These robots can change shape, split up and reassemble, etc. The story gets wilder and wilder. Colorful transparencies are presented as if they were a movie. Is he a professional entertainer hired by Ericsson, I wonder? He promises to prove to us that his ideas are not mere fantasy. All you need is a properly programmed computer and some attributes. First he shows us a one-page listing of some low-level C code driving the serial output port. Then he dives into his backpack and produces a notebook computer, a battery, a servomotor, and some wires. In a hectic few moments he connects everything and puts the servomotor, to which a little pointer is attached, on the overhead projector. After some tapping on the keyboard the pointer starts to turn. This is a real proof at its best. The crowd cheers. When he puts the ``dull'' orange ``insect'' on the floor, everybody surges forward to take pictures and it seems to get out of hand.

It takes minutes before everyone is seated again. I do not envy the next and last speaker. He tells us about Erlang, a programming language developed by Ericsson to program their newest telephone exchanges. The language is intended to be compact (programs are about ten times smaller than in Pascal or C), easy to learn and use, and suited for real-time distributed applications. We are reminded that a telephone exchange runs 24 hours a day and that it must be possible to update the software while the system is running. Older exchanges accomplish this by special, complicated hardware. Erlang provides a software solution for standard hardware. Universities can get an Erlang implementation at a discount.

Lunch is offered by Ericsson. I have an interesting conversation with the American and South African delegations. The afternoon is filled with a visit to the Vasa Museum, where the partly restored wreck of a large Swedish warship is the main attraction. The Vasa sank just off the coast of Stockholm on its maiden voyage in 1628. Its salvage in 1961 was a very difficult operation. The remainder of the afternoon is spent on a rocky hill with a nice view of Stockholm's Old Town. In the evening there is a one-hour demonstration of Alias, a state-of-the-art software package for modeling, rendering, and animation.

Second Competition Day

The second competition day is set up in the same way as the first. We start with a meeting of the IJ at 7 o'clock sharp.

Third Jury Meeting

Since we are now familiar with the Swedish procedure, we can get to business right away. The proposed problem set consists again of three problems, which are more difficult than the first day's set.

There is a general objection that the problems are too much alike and it is suggested that a look at the back-up problems might help to select a more diverse problem set. I must agree that all six problems (for both days) involve numbers (and no character strings, for instance). But this is partly due to coding tricks to avoid I/O complications (even the locations of the wall segments in Problem 2 of the first set (The Castle) were subtly encoded in numbers). The SC sticks to its proposal and will not reveal back-up problems without a more compelling reason. Problems 1 and 2 are accepted without too much discussion, though their formulation needs to be adjusted slightly.

Problem 3 draws many comments. It is pointed out that the formulation is too vague to decide about inclusion of this problem. For instance, it is not sufficiently clear what is given as input and what is to be computed by the program. Also the output format is unclear. The first part of the original problem statement reads:

A circle is divided into $n$ ($n <= 6$) sectors. Each sector is given a positive integer higher than $k$ ($k <= 20$). You can create a number by using the integer in an individual sector or by adding integers in adjacent sectors. Starting with a given integer $m$ ($m <= 20$), select the integers in the sectors to create an unbroken sequence of numbers ($m, m+1, m+2, ...$).

Write a program that inputs three integers ($n$, $m$ and $k$) and, starting with $m$, calculates the highest number in the longest sequence that can be created.

The SC then explains the intended problem in more detail. The first two sentences of the formulation above are similar in form, but the number of sectors is an input parameter, whereas the program is to pick a suitable number for each sector. After the clarification the voting still comes very close, and for the first time the President of the IJ uses his vote as well. The problem is accepted 15 votes to 13, and will be completely reformulated.

Here is a summary of the number of test cases, points, and execution time limits for each problem:

problem | # tests  points/test  seconds
--------+------------------------------
   1    |    5          6         30
   2    |    6          5         30
   3    |    8          5         30

Translating and Solving the Problems

This time the translation takes longer because the problems are more complicated (and we are more tired). The reformulation of Problem 3 arrives late, delaying the translation process even further. It is decided to start the competition at 12:45. Jacco and I stay and work on the problems.

Problem 1 (The Clocks) resembles the puzzle Rubik's Clocks. There are nine dials in a 3x3-matrix. Each dial can be either pointing up, right, down, or left (giving rise to $4^9$ states). There are nine types of moves (state changes) numbered 1 through 9. Each move turns a number of dials 90 degrees clockwise. Let us label the dials as follows:

  a  b  c
  d  e  f
  g  h  i
Then the moves are specified in the following table (this looks nicer in a picture):
  move | turns dials   move | turns dials     move | turns dials
  -----+------------   -----+--------------   -----+------------
    1  | a, b, d, e      2  | a, b, c           3  | b, c, e, f
    4  | a, d, g         5  | b, d, e, f, h     6  | c, f, i
    7  | d, e, g, h      8  | g, h, i           9  | e, f, h, i
Given a state of the dials, find a shortest sequence of moves to make all dials point up. This is not such a difficult problem. A first important observation is that reordering the moves in a sequence does not affect the result (superposition principle). A second observation transforms it into a linear algebra problem, involving nine linear equations in nine unknowns ($x_i$ indicates how often move $i$ occurs). The inversion of the resulting 9x9-matrix can in fact be done off-line, since it is fixed. This yields an extremely fast and short program. At first my equation solving program fails to produce the desired results, because I did not enter the matrix correctly.

Problem 2 (The Buses) concerns a list of arrival times of buses at a bus stop during one hour. Given is that no more than 17 bus lines use this bus stop. Buses of each line arrive at regular intervals throughout the hour. Each bus line stops at least twice. Arrival times are given in ascending order (duplicates allowed) in whole minutes from 0 to 59. The objective is to reconstruct from the given list of arrival times a schedule with the fewest bus lines that accounts for these arrival times. For each bus line in the schedule you should give the arrival time of the first bus of that line and the interval. For example, the list

  0, 3, 5, 13, 13, 15, 21, 26, 27, 29, 37, 39, 39, 45, 51, 52, 53
is produced by the following schedule with three bus lines
  first arrival   interval | accounts for
  -------------------------+--------------------------
        0            13    | 0, 13, 26, 39, 52
        3            12    | 3, 15, 27, 39, 51
        5             8    | 5, 13, 21, 29, 37, 45, 53
and cannot be produced by fewer bus lines. It took me a while to realize that the first arrival time of a bus line should be less than its interval, for otherwise buses of that line have not arrived throughout the hour (the `throughout' in the formulation above was not present originally).

This is a tough problem, especially getting it to work fast enough. In my approach, I generate a list of candidate bus lines that agree with the given arrival times. Each such bus line is characterized by a pair $(f, i)$ giving first arrival $f$ and interval $i$ such that $0 <= f < i$ and $f+i<60$ (at least two buses arrive; hence $0 <= f<30$ and $f < i < 60-f$), and the set

  { f + k*i  |  0 <= k  and  f+k*i < 60 }
is included in the set of given arrival times. This list is sorted on number of arrivals and a recursive procedure decomposes the given list of arrival times in all possible ways using the candidate bus lines. `Branch and bound' sees to it that the investigation of hopeless subtrees in the search tree is avoided.

Problem 3 (The Circle) already received some attention. I never got to solving it, so I'll be brief about it. First we introduce some terminology, given a circular arrangement of numbers (placed in a circle). Number $p$ is said to be creatable, when there is a subsegment of adjacent numbers in the circular arrangement with sum $p$. The tail of number $m$ is defined as number $t$, $t >= m$, such that all numbers from $m$ to $t$ are creatable and number $t+1$ is not creatable. Given numbers $n$ ($1 >= n >= 6$), $m$ ($1 >= m >= 20$), and $k$ ($1 >= k >= 20$), the objective is to find all circular arrangements of $n$ numbers, each number being at least $k$, such that the tail of $m$ is maximal. It is also required to output that tail.

For example, when $n=5$, $m=2$, and $k=1$, the circular arrangement

  1, 3, 10, 2, 5
gives 2 a tail of 21: the numbers 2 through 21 are creatable and 22 is not creatable (the sum of all numbers is 21). This arrangement gives 2 the maximal tail. It is not unique; another solution is:
  2, 4, 9, 3, 5

Judging the Programs

Judging seems more hectic today, possibly because the final scores will be made up. Since judging is now done in reverse alphabetic order, the Dutch team (whose code is NLD) should be judged early. However, because we require an evaluator knowledgeable about Logo, we still have to wait longer than the first day. The boys appear optimistic as always. They again claim to have solved all three problems. Unfortunately, neither of them noticed the superposition principle in Problem 1 (The Clocks). It looks like their programs will only tackle short move sequences (a move sequence of length 27 is in fact possible). The girls give the impression of having accomplished more.

Jaap is first up. His program for Problem 1 (The Clocks) gets the first test case right, but times out on the other four. He fares a little better on Problem 2 (The Buses), where he passes three test cases and fails the last three by timeout. Surprisingly, he gets the first six test cases on Problem 3 (The Circle) right and produces additional incorrect output for the last two. His score for today is 51, bringing him to a grand total of 141.

Edwin gets two test cases right on Problem 1 (The Clocks) and times out on the others. Problem 2 (The Buses) gives only a pass for the first test and fails the others (by timeout). Again we are surprised at the performance on Problem 3 (The Circle), where Edwin passes six and misses two (incomplete answers). That brings his score for Day 2 at 47, giving an overall score of 80.

The girls remain stuck at zero points each, in spite of Anne Marie's efforts to argue that they did better than the first day. Too soften the blow a bit, there are 15 others with this total score as well. Rumor has it that no one got a perfect score today.

Archipelago Boat Tour (Telia Day)

A short bus trip takes us to Dalarö, a former customs village on the coast south of Stockholm. There we board two boats that tour the Swedish Archipelago while we talk, bask in the sun, and play cards. I join the Taiwanese delegation for a nice lunch on the lower deck. At Utö, one of the larger islands in the Archipelago, we are dropped off to wander around or take a guided tour. On the return trip we switch boats. Now I am on the steamship. The engine room is an engineer's delight. The two crew members in charge of the engine are only too willing to explain all the details about running and maintaining a steam engine. It is hard to imagine how one can stand the heat (produced by three large boilers) down there for so long.

At Dalarö the students go back to Haninge by bus, while the others take a boat to Rosenön, a little island further north. There, the last IJ meeting will take place and afterwards we will have dinner. First we get some notes explaining the SC's decisions on controversial cases. In most cases no points have been awarded. Only rarely has a retest been done under slightly altered conditions; for instance, when the executable was in the wrong directory,

Fourth Jury Meeting

This last jury meeting has a diverse agenda: I will tell a little about the first and last items. The regulations (which I have never seen) state that roughly 1/12 of the participants get a gold medal, 1/6 silver, 1/4 bronze, and 1/2 no medal. For this olympiad there are 189 students, suggesting roughly 16 gold, 32 silver, and 47 bronze medals. It is desirable that students with (almost) the same number of points get the same medal. Therefore, the exact dividing lines will be drawn by the IJ through some voting procedure. It should be kept in mind, however, that team leaders will try to get the best results for their students. The organization attempts to force an ``objective'' decision by presenting no more information than necessary.

This year, I am told by insiders, the approach is again a little different from previous years. First, the organization hands out a histogram of relative scores for students ranked 10 through 22 (centered around rank 16). The absolute scores are not given, making it harder for team leaders to identify their students. It turns out that 16 gold medals is indeed a good choice. This procedure is repeated for the boundary between silver and bronze, and between bronze and no medal. The IJ approves 33 silver medals and a whopping 51 bronze medals, leaving 89 students without a medal.

The next three points on the agenda pass by uneventfully. The last point, however, evokes numerous reactions. Let me summarize them briefly.

The foremost comment concerns the low scores. It is felt to be unsatisfactory that so many students get so few points. Not only is this emotionally hard to accept but it may also hamper fund raising for participation in future IOIs. The organization explains that they have aimed at a problem set that would challenge the best students. IOI'92 in Germany saw 12 students with a perfect score. This they had wanted to avoid, and with success. They also think it would have been worse if only one student had gotten zero points, at least now the zero-scorers are not alone. It must be admitted that the skills of these students range over a wide scope.

Another comment is that there is too much emphasis on optimal solutions and most efficient programs. There is some truth in this. The six problems can be captured by the following phrases: maximal path sum, largest room, all prime squares, shortest move sequence, fewest bus lines, all arrangements with maximal tail. The organization counters that the test cases were chosen such that less efficient programs would get some, though not all, points. And let me add that most problems can be posed as an extremum problem.

Someone else finds that too few (kinds of) programming languages are involved, the competition being too much geared toward Pascal and C. Others would like to see different types of problems (no programming?). And what about a real team competition involving cooperation between team members?

A request is made to settle once and for all that future IOIs make use of standard (i.e., American) keyboards and DOS. I can sense some agreement here, but how long will DOS stay around (and keyboards, for that matter)?

It is also requested that the SC explains in more detail the ideas behind the problems and the tests. This should help to build confidence and should simplify the selection procedure. A disadvantage might be that such information could find its way to the students via the translation.

Finally, it is suggested to set up a forum, possibly electronic, for further discussion of IOI related ideas. No one volunteers to moderate such a group. I can now see why: writing this trip report was already a major effort.

At the very end a heated debate is taken off-line. Do you consider it fair that a student who, in addition to the correct bus schedule, outputs the number of bus lines (which was not requested in Problem 2, Day 2) gets full points, whereas another student who outputs the correct circular arrangements but fails to output the maximal tail (which was also requested in Problem 3, Day 2) gets zero points?

Dinner

After such a meeting a relaxing dinner is a blessing. I share a table with some SC members. They patiently explain to me how the problems were created. Håkan started seven weeks ago by inventing 30 problems and selecting 20 former IOI participants and other bright (ex)students for his SC. The SC read the problems and selected ten for further refinement (no programming so far). Each SC member then was assigned two problems for closer examination, Thus, each problem was covered by four members. They wrote a programmed solution and put together test data. The problems were tuned along the way.

During the return trip by bus, several team leaders take delight in combining their knowledge to find out what medals their students have. We also have a good hunch.

Closing Ceremony (KTH Day)

The closing ceremony takes place in the Blue Hall of Stockholm's City Hall. The Blue Hall is not blue because the architect changed his mind during the actual construction (he liked the red bricks so much). The nearby Golden Hall, having a wall mosaic of 18 million pieces covered with 24 carat gold leaf, is famous for the yearly Nobel Prize banquet. A band, dressed up for carnival (so it seems), provides musical interludes.

Speeches cannot be avoided at such an occasion. Fortunately, they are entertaining and short. We are told, for instance, that ten hours of competition have produced 250,000 lines of code. The ``Queen of Lake Mälaren'', elected every year as spirit and protector of Stockholm, presents the medals. First the bronze medalists are called forth in three batches. Among them is Edwin, hurray. They all move onto the huge flight of stairs leading to the Golden Hall. Then the silver medalists come forward in two batches. Jaap appears near the end (close to gold), hurray, hurray. Finally, the gold medals are presented. The top scorer is a young timid Russian student, Viktor Bargatchev, with an unbelievable 195 points (out of 200). He missed just one test case for Problem 2 of the second day (The Buses); this test case had the maximum of 17 bus lines.

It turns out that overnight the medal counts have been slightly altered to compensate for some errors. For example, one score had not been typed in properly and a bronze medal is turned into silver. The counts are now:

  medal  | count | point range
  -------+-------+------------
  gold   |   16  |  148..195
  silver |   35  |   96..145
  bronze |   50  |   65.. 95
  none   |   88  |    0.. 62
Even the very best students have been challenged to their limits.

The IOI banner is officially handed over to Ries, who thanks the organization for a splendid olympiad. He explains that next year, at IOI'95, each country is invited to bring a fifth student, provided one of them is a girl. Afterwards the Dutch delegation hands out little tulip pins to all present. Before dispersing, we sing ``Auld Lang Syne'' together, holding hands.

The afternoon is for shopping in Stockholm. In the evening there is a ``breaking-up'' party with entertainment. Some go to bed early (next morning).

Conclusion: Departure Day

Most of the teams leave quietly on Sunday July 10, filled with new experiences. I have heard no complaints about the accommodation, the food, the trips, or the (incredibly good) weather. It is not easy to organize an IOI. They did a great job. Many new ideas have crossed my mind, but I will report on them separately.

The illustrations were obtained from the World Wide Web (WWW) via Uniform Resource Locator (URL) http://ioi.haninge.kth.se/ (now http://www.haninge.kth.se/IOI/ioi.html). Besides pictures, this site also carries all the problem statements and test data.


Tom Verhoeff
Faculty of Mathematics and Computing Science
Eindhoven University of Technology
E-mail: Tom.Verhoeff@acm.org