The IOI'94 Competition
Chair of the Scientific Committee for IOI'94:
Håkan Strömberg
(hakan@haninge.kth.se),
College of Engineering,
Kungl Tekniska Högskolan
(Royal Institute of Technology),
in Haninge, Sweden
First we explain the competition rules.
After that we provide the problem set.
Next we reveal the (secret) test data used for evaluation.
A bundle of documented solutions is also provided.
The programs
written by the Scientific Committee of IOI'94
(and some others) are available as well.
At end there is an index for the problem set.
Competition days
There are two competition days (Tuesday and Thursday),
separated by one day of rest.
Each day the competitors have to solve three problems.
They have five hours for the task (from 12:00h to 17:00h).
The computer
Each competitor has
a personal computer for the entire duration of the competition.
The computer is an AST with a 33 MHz Intel 486 processor running MSDOS.
Programming languages
The following four programming languages are available:
 Turbo C++ 3.0
 Turbo Pascal 7.0
 QuickBasic 4.5
 LCN Logo 3.0
All the languages are fully installed with help files and examples.
Competitors may not bring any aids of their own,
such as program disks, manuals, or books.
Directories
Apart from a directory for each of the four programming languages,
there are two directories: IOI_DAY1 and IOI_DAY2.
In both these directories are five subdirectories called
PROBLEM1,
PROBLEM2,
PROBLEM3,
PROBLEM4 and
PROBLEM5.
Each programming problem will have its number marked on the paper given to the
competitors.
It is important that the solutions are put in the correct directory.
If the title on the problem paper is "Day 1  Problem 3",
the solution has to be put in the directory C:\IOI_DAY1\PROBLEM3.
The solution has to be an EXE file.
The solution to the problem "Day 1  Problem 3" has to be called
PROBLEM3.EXE.
The problems
The competitors get the three problems for each day in two copies,
one written in English and one translated by their team leaders into
their native language.
Input data
For all problems input data will come from an ASCII file
which will always be called INPUT.TXT.
This is the case even if the program will need only a single number.
No tests of the input data are necessary.
For all INPUT.TXT files one can assume that the input data
correspond to the problem statements.
Input data will be either integers or strings.
Since the file always begins with one or more numbers defining
the number of integers or strings that follow, competitors do not have to
check for endoffile conditions.
Two integers in the input file will be separated by either a single
space character or a newline.
The number of integers in a line will be clear from the problem statement.
A string is always terminated by a newline.
Every problem has an example input file which will also be shown
on the problem paper.
Do not read anything from the keyboard, not even a keystroke.
Here are examples of how to open an ASCII file and
read a value for the integer variable N in the four languages:
 Turbo Pascal

var infile: text;
...
Assign(infile, 'INPUT.TXT');
Reset(infile);
Read(infile, N);
 Turbo C++

#include
FILE *infile;
...
infile = fopen("INPUT.TXT", "rt");
fscanf(infile, "%d", &N);
 QuickBasic

OPEN "INPUT.TXT" FOR INPUT AS #1
INPUT #1, N
 Logo

tell disk
filepos "INPUT.TXT
make N
read number
Output data
The results of the program are always to be written to the
ASCII file OUTPUT.TXT.
The file has to be formatted exactly as stated in the problem.
Never add any texts of your own!
Do not write anything to the screen.
The program has to exit when the output has finished.
Here are examples for the four languages of how to create an ASCII file and
write the value of the integer variable N on it:
 Turbo Pascal

var outfile: text;
...
Assign(outfile, 'OUTPUT.TXT');
Rewrite(outfile);
Write(outfile, N, ' ');
...
Close(outfile);
 Turbo C++

#include
FILE *outfile;
...
outfile = fopen("INPUT.TXT", "wt");
fprintf(outfile, "%d", N);
...
fclose(outfile);
 QuickBasic

OPEN "OUTPUT.TXT" FOR OUTPUT AS #1
PRINT #1, N;
...
CLOSE #1
 Logo

tell disk
newfile "OUTPUT.TXT
tell disk
filepos "OUTPUT.TXT
write N
Printouts
During the competition competitors will be able to get printouts of their
programs.
If they want a printout they have to copy their file to one of the two
diskettes and leave it to an official.
See to it that the diskettes only contain files that need to be printed.
Diskettes
When the competition nears the end the competitors have to copy their
solutions to both diskettes.
Give both diskettes to an official.
During testing one of them will be returned to the competitor or their
team leader.
No extra time will be allowed for copying.
It might therefore be good to copy solutions as they are done.
It is the EXE file on the hard disk on the competitor's computer
that will be tested.
Only in case of hardware error during testing will the copy on the diskette
be used.
Grading is done directly after the end of the competition.
The competitors and their team leaders will take part in the grading.
There will be lists with the approximate time for their turn to be graded.
For each problem there is a set of up to 10 test examples that
have been prepared in advance.
Each test will be announced with the maximal allowed execution time
(in seconds) and the number of points a correct answer will give.
The grading will be done by a program that looks
in the various directories for an EXE file with the correct name.
It starts the competitor's program,
measures the execution time and checks the resulting file OUTPUT.TXT.
Note: All test data will have solutions.
Here is the problem set for IOI'94.
For each problem, the number of tests, the number of points per test,
and the maximum execution time is given.
Day 1 (5 hours)
 Problem 1: The Triangle
There are 6 tests.
Each successfully completed test gives 5 points.
Therefore the maximum number of points for this problem is 30.
The maximum execution time is 30 seconds per test.
 Problem 2: The Castle
There are 5 tests.
Each successfully completed test gives 6 points.
Therefore the maximum number of points for this problem is 30.
The maximum execution time is 30 seconds per test.
 Problem 3: The Primes
There are 4 tests.
Each successfully completed test gives 10 points.
Therefore the maximum number of points for this problem is 40.
The maximum execution time is 90 seconds per test.
The maximum number of points for the first day is 100.
Day 2 (5 hours)
 Problem 1: The Clocks
There are 5 tests.
Each successfully completed test gives 6 points.
Therefore the maximum number of points for this problem is 30.
The maximum execution time is 30 seconds per test.
 Problem 2: The Buses
There are 6 tests.
Each successfully completed test gives 5 points.
Therefore the maximum number of points for this problem is 30.
The maximum execution time is 30 seconds per test.
 Problem 3: The Circle
There are 8 tests.
Each successfully completed test gives 5 points.
Therefore the maximum number of points for this problem is 40.
The maximum execution time is 30 seconds per test.
The maximum number of points for the second day is 100.
N.B.The following test data were not available
during the competition.
They were used to judge the programs of the competitors
after the competition.
The provided test output must be interpreted carefully,
because the output is not always uniquely determined by the input.
In Problem 2 of Day 1 (The Castle),
the third item of the output may be presented in different ways.
Each test output file for this problem contains the first two items and
a list of all possible presentations of the third item
(the competitor's program needs to produce only one of these).
In Problem 3 of Day 1 (The Primes) and all the problems of Day 2,
the order in which items,
except the first item in Problem 3 of Day 3 (The Circle),
are presented is free.
The test output files contain the relevant items in one order only;
all permutations, however, are correct too.
Day 1
Day 2
 Problem 1: The Clocks
(per test: 6 points and 30 seconds)
 Input /
Output (3 moves)
 Input /
Output (10 moves)
 Input /
Output (19 moves)
 Input /
Output (24 moves)
 Input /
Output (27 moves)
 Problem 2: The Buses
(per test: 5 points and 30 seconds)
 Input /
Output (12 arrival times; 3 bus routes)
 Input /
Output (44 arrival times; 4 bus routes)
 Input /
Output (43 arrival times; 5 bus routes)
 Input /
Output (31 arrival times; 7 bus routes)
 Input /
Output (40 arrival times; 11 bus routes)
 Input /
Output (70 arrival times; 17 bus routes)
 Problem 3: The Circle
(per test: 5 points and 30 seconds)
 Input /
Output
(3, 1, 1; maximum is 7 with 2 solutions)
 Input /
Output
(4, 2, 2; maximum is 13 with 2 solutions)
 Input /
Output
(5, 3, 1; maximum is 22 with 2 solutions)
 Input /
Output
(4, 16, 1; maximum is 23 with 6 solutions)
 Input /
Output
(5, 16, 12; maximum is 20 with 24 solutions)
 Input /
Output
(6, 1, 1; maximum is 31 with 10 solutions)
 Input /
Output
(6, 2, 2; maximum is 29 with 2 solutions)
 Input /
Output
(6, 4, 4; maximum is 31 with 6 solutions)
Below are the documented solutions for the problem set of IOI'94,
as provided by Tom Verhoeff.
A short introduction explains some
general features of these solutions.
Day 1
Day 2
Here is an index for the problem set of IOI'94.
Clicking on a problem, brings up a page with pointers to
the problem statement, the tests, and the solution.
Day 1
Day 2
IOI Secretariat /
ioisecretariat@win.tue.nl
Internet service provided by