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 Rules for IOI'94

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 MS-DOS.

Programming languages

The following four programming languages are available: 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 end-of-file 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 <stdio.h> 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 <stdio.h> 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

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.

The Problem Set for IOI'94

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)

The maximum number of points for the first day is 100.

Day 2 (5 hours)

The maximum number of points for the second day is 100.

The Test Data Used for Judging IOI'94

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

Documented Solutions for IOI'94

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

Index

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