International Olympiad in Informatics

Meena Mahajan

IMSc, Chennai

E-mail: meena@imsc.ernet.in

It came as a considerable surprise to me to discover that there is, and has been since 1989, an International Olympiad in Informatik (IOI). I read about it in the October'97 EATCS Bulletin (Number 63). I mentioned the IOI to various colleagues in theoretical computer science, and found that none of them had heard about it either.

Subsequently I visited the IOI web site . I checked that there is no record of participiation from India. I downloaded some of the problems from the earlier Olympiads too.

The article in the EATCS Bulletin is written by Tom Verhoeff, who was involved in the IOI since 1994. Verhoeff, who is at the Eindohoven University of Technology in the Netherlands, sounds a strong cautionary note in the observation that the flourishing sciences all have flourishing school-level competitions. To quote from his article,

... One measure of acceptance and integration of a discipline into the curriculum is the situation regarding competitions in that discipline. A healthy, diverse set of competition events indicates that the discipline is well accpeted. A lack of (good) competitions is a sign of poor acceptance. ...

He then describes the nature of the IOI and other programming contests, points out the poor emphasis on theoretical aspects and some of the difficulties in setting theoretical questions, and concludes as follows:

... The lack of a good, interesting, and thriving TCS competition is an ominous signal that cannot be ignored. Either we do something about it and prove that it can be done (and thus do the field a badly needed service), or we must conclude that TCS is not suitable for this, and thereby also admity that there may be a ground for the students' general dislike of TCS. Fortunately, there are still those students that after a programming contest hate machine details enough to prefer a more abstract field. ...

Whether or not we agree with these sentiments (for myelf, I am not entirely convinced, mainly because of my own experience. I like to solve interesting problems and puzzles, but ask me to participate in a contest and my mind proceeds on casual leave. Non-competetiveness is fine as a way of life!), it is certainly intriguing to follow the course of the IOI and chart the shifting emphases laid on different kinds of problems over the years. A major point Verhoeff makes is that while the problems are programming-based (partly to make them easier to judge impartially; more importantly, to minimize disadvantaging some teams due to language barriers), there is no reason why they cannot be based on strong theoretical foundations. In the last couple of years, he has helped introduce problems of this nature, and he feels that the response from the participating teams was a bit mixed. By and large, the contest is still centered around programming, with the occasional emphasis on algorithmic aspects.

Here is an instance of a programming problem which requires the participants to address theoretical issues as well. This question was asked in IOI'96 (Veszpr\'em, Hungary).

Sorting a Three-Valued Sequence

Sorting is one of the most frequently done computational tasks. Consider the special sorting problem, where the records to be sorted have at most {\em three\/} different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver , and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. Sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers $p$ and $q$, exchanges the elements in positions $p$ and $q$.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted. (Subtask A). Moreover, construct a sequence of exchange operations for the respective sorting (Subtask B).

Input Data

The first line of file INPUT.TXT contains the number of records $N$ ($1 \le N \le 1000$). Each of the following $N$ lines contains a key value.

Output Data

Write on the first line of file {\sf OUTPUT.TXT} the minimal number $L$ of exchange operations needed to make the sequence sorted (Subtask A). The following $L$ lines give {\em the respective sequence of the exchange operations in the order performed}. Each line contains one exchange operation described by two numbers $p$ and $q$, the positions of the two elements to be exchanged (Subtask B). Positions are denoted by the numbers from 1 to $N$.

Example Input and Output

A sample input file and the corresponding output file is shown below.

INPUT.TXT          OUTPUT.TXT     

9                  4              
2                  1 3            
2                  4 7            
1                  9 2            
3                  5 9           
3                                 
3                                 
2                                 
3                                 
1

Figure 1

With a little reflection we can come up with a method that seems optimal. Technically, the IOI requires the students to come up with a program for an optimal method. If the obvious-after-some-reflection method is optimal, then the task is not too much for talented high-school kids. But isn't it fun for us to come up with a formal proof that this is optimal?