A Trip Report

3 - 10 July 1994, Haninge, Sweden

- Introduction
- Arrival Day
- Opening Ceremony
- First Competition Day
- Ericsson Day
- Second Competition Day
- Archipelago Boat Tour (Telia Day)
- Closing Ceremony (KTH Day)
- Conclusion: Departure Day

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'94This picture shows part of the Dutch delegation.

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.

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.

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.

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

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.

**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.

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.

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.

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, ...$).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.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.

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

**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 iThen 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, iGiven 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, 53is 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, 53and 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

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, 5gives 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

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.

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,

- Assignment of medals.
- Host countries for future IOIs up to 2002.
- Plans for a Board of Trustees.
- Regulations.
- Suggestions for improvement.

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?

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.

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.. 62Even 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).

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