journal of science education

Back Issues

Information and Announcements

International Olympiad in Informatics

The International Olympiad in Informatics (IOI) is one of the six science olympiads held annually.  The subjects in which the other five science olympiads are held are mathematics, physics, chemistry, biology and astronomy.  IOI was first conducted in 1989, in Bulgaria.  This year's edition, IOI2001, was held from July 14-21, 2001 in Tampere, Finland, about 200 kms north of the country's capital city, Helsinki.

As with the other Olympiads, the host country provides local hospitality for the participants in the competition.  In this case, the local arrangements included free transportation to and from Helsinki because a number of participants found it more convenient (and significantly less expensive) to arrive in Helsinki, rather than Tampere.

A typical team at IOI consists of the student competitors (up to four) accompanied by a leader and a deputy leader.  This year, 72 countries sent teams, though not all teams had the full complement of four students.  North America, Europe and Asia are all well represented at IOI.  Quite a few countries from South America and Africa do not yet participate.  Other than India, prominent absentees include Belgium, Japan and New Zealand.

India has not been sending a team to IOI, but plans to do so in 2002.  In keeping with the traditional procedure at the science olympiads, India had to officially nominate an observer to attend IOI this year in order to qualify to send a full team next year.  India was the only

country that sent an observer to IOI2001.  I was the official Observer from India at Tampere.

The Local Organization

IOI2001 was organized by the University of Tampere.  The main competition, along with the opening and closing ceremonies, was held in the city's conference centre, Tampere Hall.  This impressive building is just across the road from the main campus of the University of Tampere.  The students and accompanying adults were housed in (separate) hotels within a few hundred metres of Tampere Hall.  Meals were organized in a dining hall within the University. The proximity of the conference venue to the accommodation for the guests made it possible to travel back and forth on foot with minimum delays, resulting in a considerable saving in time and effort (in terms of avoiding coordinating the movement of large groups of people by bus).

One feature of organizing IOI -- in contrast to, say the Mathematics Olympiad -- is that the venue for the competition has to be equipped with vast computer infrastructure.  In the case of IOI2001, a huge room within Tampere Hall was equipped with about 300 new computers, networked together, for the students to use for the competition.  In addition, about 75 computers, one per country, were made available in another hall for the team leaders and deputy leaders to use for translation, checking the evaluation etc.  (At the end of IOI2001, these computers were donated to the public school system in Tampere.)

 The Academic Programme

The format of IOI has been evolving and is now quite similar to, say, the International Mathematics Olympiad.  The host country invites competition questions from all over the world.  These questions are then shortlisted by a local committee.  There are two days of competition and the problems for each day are chosen from the shortlist by the host country and presented for approval the night before each competition day to the General Assembly, consisting of all team leaders.  Once the questions are approved, the team leaders from non-English speaking countries are allowed to translate the questions into their native language.

In fact, IOI2001 was the first IOI where questions for the competition were contributed from outside the host country.  In addition, the organizers have recently formed an International Scientific Committee (ISC) consisting of 3-4 elected members together with some de facto members from past, present and future IOI local organizing committees to assist in the problem shortlisting process.  This year, for the first time, the ISC reviewed the questions shortlisted by the host country and checked them for ambiguity, level of difficulty, etc. This screening resulted, I believe, in significantly shorter General Assembly meetings for approving the final competition questions because many of the rough edges had already been taken off the questions by the ISC.

As in other Olympiads, each competitor participates as an individual. Each day of competition consists of three `tasks' to be completed over a period of five hours.  The tasks are algorithmic in nature and involve some non-trivial use of techniques from the design and analysis of algorithms and data structures.  This year's questions were universally acknowledged to be harder than in any previous IOI, and in my opinion they were difficult even for computer science undergraduates, let alone high-school students.

Two of the problems from this year's competition, are given at the end of this article: the problems have been edited to make them more concise.  Interested students are invited to send in their solutions to the author.

The competitors have to generate working programs for each of the tasks in the competition in order to get credit.  The programs are evaluated automatically using carefully chosen test data -- it is important to note that the source code is not evaluated at all for style, conciseness etc.  Moreover, if the program does not work, the solution gets zero credit -- there is no way of assigning partial credit for non-working code.  Thus, not only do the competitors have to be trained in the underlying theory of algorithms, they must also be capable of generating working code under severe time constraints.

Each task is accompanied by limits on the amount of memory and the time available to the competitor's solution.  The test data is designed in such a way that it distinguishes optimal solutions from non-optimal ones.  By choosing suitable values for the test data, the organizers ensure that inefficient solutions will overrun either the space or the time limit.  Typically, each problem is evaluated using 20 or 25 test inputs.  Each test passed by the program thus gives it 4-5 points out of a maximum possible 100.

One negative feature of this evaluation system is that a correct program that fails to meet the time/space requirements is given the same marks (zero) as a program that is incorrect.  There is a suggestion to give `degraded' but non-zero marks for correct solutions that fail to meet the time/space bounds.  One constraint is that the entire evaluation system is automated and in order to process and tabulate the results in a reasonable amount of time, some cutoffs have to be imposed on the running time of submitted solutions.

The programming languages available to the competitors are Pascal, C and C++.  This year, students had a choice of working either under Microsoft Windows or Linux.  The actual testing and evaluation were done under Linux.  Students submitted their programs as source code via a web interface to the evaluation server, which compiled the  programs and ran them on the test inputs.

 Till last year, the operating system used for the competition was Microsoft DOS, which has severe limitations on the memory usage of programs (among other shortcomings).  By switching to a more modern operating environment, the organizers were able to set questions that were more challenging in terms of the time and space requirements that had to be satisfied to get a fully correct solution.

However, as I noted earlier, there was a feeling that this year's questions were, perhaps, too hard.  This was reflected in the scores -- while there were 2 or 3 perfect scores at IOI2000 in Beijing, this year, the highest score was 585 on 600, and the second and third

positions were around 525 and 485 with a further sharp fall in scores through the gold medal list.  Interestingly, but not surprisingly, the top  scorer Reid Barton of USA, had just won a Gold medal scoring 42/42 at the IMO held a week earlier.

Another important factor is that most of the team leaders at IOI2001 were not well-versed in algorithms and data structures.  As far as I could tell, the basic interest of almost all the team leaders was computer pedagogy (`how to introduce computers and programming in a school curriculum').  Given that the questions at IOI2001 went well beyond the abilities of the team leaders, it is not surprising that the students performed rather badly!

 IOI in 2002

The next IOI will be held in South Korea, in August, 2002.  It will mark the first time that India competes in IOI.  A national level steering committee has been constituted and a first-round nationwide screening test to select the team is planned for February, 2002. Selecting and training the team is a major challenge, but I am confident that India will field a competitive team in Korea next year.

 Madhavan Mukund
Chennai Mathematical Institute, Chennai, India.
E-mail: madhavan@cmi.ac.in

Read full article (88 Kb)

VIDYANANTHA

(A registered society for the promotion of education)

The following publications are available on donation

1. Molecule to man: A narration of cosmic-chemical-biological organization. 
2. Life under the Sun: Solar energy-ATP.
3. Energy transduction: proton gradient _ energy gradient.
4. Woodward_Hoffmann rules _ a simple description _ aromatic transition states.
5. The magic in chemistry _ ninety minutes of tested demonstrations.
6. The rules for making and breaking bonds to carbon: An hour on basic organic chemistry.
7. Introduction to carbon chemistry
8. Models with an envelope 1. Modular assembly of buckminster fullerene (bucky ball).
9. Models with an envelope II: Modular assemblies of platonic solids (tetrahedron, octahedron, cube, dodecahedron and eicosahedron).
10. Models with an enveloped III. Modular assembly of DNA double helix.
11. Modular assembly I. Ten napthalenes to one fullerene.
12. Modular assembly: Nut bolt approach to dodecahedron.

Please send crossed demand draft in unregistered covers to:

S Ranganathan

Secretary, Vidyanantha,
Padmavati Paradise Apartments #2
12-13-261 Street No.8, Tarnaka
Hyderabad 500 007

Donation per copy: Undergraduates: Rs. 20; Post-graduates/Teachers: Rs.50; Others: Rs.100.

Indian Academy of Sciences
C.V.Raman Avenue, Post Box No. 8005,
Sadashivanagar Post, Bangalore 560 080