Newsletter No. 6


June 2006


Editorial

The times, they are a-changin' ... Seldom did this famous line better suit the situation of IOI. At IOI 2005 in Poland, Zide Du from China was elected first President of IOI, after this position had been successfully installed following a movement by the General Assembly. Last fall, IOI community was shocked by the news of the death of Lionel Hartmann, IOI's first and long time Executive Director. In January, IOI and other experts came together in Germany for a workshop on Computer Science contests and developed proposals, most of which are closely related and relevant to IOI. At both IC and ISC meetings in March, many of these proposals were discussed, and several new steps on those lines were taken. Almost by the way, IOI 2006 is being well prepared by its Mexican hosts and will become reality quite soon.

In this newsletter, all those issues are covered. In his address, the President gives a word in honor of Lionel Hartmann and on the actions he took when dealing with this sad incident, and informs about the most important movements made by the IC. There is a report about the workshop, there is an extensive article from the ISC about new approaches to scoring at IOI 2006, and from ITWG comes both a statement about the use of Java, and notes about the progress of several ITWG projects. However, the news part will begin with the most important information about IOI 2006.

In addition to that, there is a call for translation volunteers. Again, IOI documents are to be made available in other languages than English only. Thus, more GA members will be able to more closely follow debates and discussions about the development of IOI which we are looking forward to have at IOI 2006. Discussions about IOI-related topics will probably also be held at the ISSEP conference in Lithuania in November, chaired by long-time team leader Valentina Dagiene, who is also editor of the journal "Informatics in Education" where selected contributions to the workshop were published.

See you in Mérida!

Yours truly,
Wolfgang Pohl, IOI ED


Table of Contents

  1. Presidential Address
  2. News About IOI 2006
  3. Competition Workshop
  4. ISC Report: Grading and Feedback at IOI 2006
  5. Java in the IOI
  6. ITWG Highlights
  7. Call for Translation Volunteers

Presidential Address and IC Report

This year, IOI will have its 18th competition, and it seems that IOI is becoming an adult. But actually, it is far not! It is still growing up.
 
The core activity of IOI is the competition, but competition is not its main and final objective. As it is written in the regulations, the IOI should stimulate more students in high schools to be involved in and to learn computer science. However, only a very low percentage of students are participating in this activity. Obviously, IOI should strengthen its impact in the world and enhance its reputation. With these goals in mind, the IOI will have a long way to go.
 
Just after IOI 2005, the Executive Director Mr. Lionel Hartmann unexpectedly brought forward his resignment to the president and the IC because of his disease. The president nominated a new ED candidate, who got approved by IC, so that we have a new ED Wolfgang Pohl, a very experienced person, since October 2005.
 
Lionel is the first Executive Director of the IOI, he took the position in 2000. Unfortunately, he left us in March. This sudden news shocked all colleagues of the IOI community. Many countries and many members in our community expressed their deep condolences to Lionel’s death and sent sympathy to his widow. Due to Lionel’s outstanding contributions to the IOI, IOI will award him and will also have a memory celebration during IOI 2006.
 
Nevertheless, IOI keeps moving forward. The IC meeting in Mérida in March was busy discussing many new developments, in part inspired by preceding discussions at the competition workshop in Germany (see below). One example is the restructuring of the IC. IOI IC’s structure has to be adjusted so as to reflect more democratic rights of IOI members: the IC members from the host countries will be cut off to 5 at most, and the members elected by GA will be increased to at least 6. And more power will be given to the GA in the future.
 
Another issue: IOI is a very organized community, all participants (individuals and teams) have to meet requirements, and every new member has to be qualified. The IC will make a form for all teams to fill out, the IOI will know who is who. The acquired data about national activities will be very useful for measuring and demonstrating the overall relevance of IOI in the secondary school world.
 
IOI is an international community. In addition to giving recognition to the excellent students, all volunteers who work for IOI and make outstanding contributions should be recognized as well. The president will award some of those people on IOI 2006.
 
Nowadays, almost everyone in the IOI knows what responsibilities he or she should take. We surely believe the IOI will develop in the future, for we have worked out the goals and responsibilities.
 
Zide Du
President of IOI

back to table of contents


IC meeting

IOI International Committee during their March 2006 meeting in Mérida, México (Photo: Don Piele)


News on IOI 2006

The most important source of news about IOI 2006 is, of course, its completely redesigned web site. There, you will see the following:

Registration is open. However, at first, country contact persons need to register themselves as well as preregister their country's delegation. For that process, the new IOI registration system is used. Contact persons are those persons in a country that have long-term responsibility for their country's participation in IOI. Contact persons may or may not be delegation leaders, they may or may not go to IOI themselves; this is handled very differently in IOI member countries. There has already been some discussion on the procedure of retrieving country contact information from IOI countries. However, so far, this procedure has worked almost without flaw, and it will help IOI in its effort to build up a valid and lasting data base of country information.

Competition rules have been made available. In most sections, you will not find surprises, but there are important changes in the section on grading. Those changes will be explained extensively in the ISC article below. For the first time, the competition will be Linux-only. This move was supported by IC; a Linux-only competition environment will make organizers' lives much easier. All modifications compared to last IOI's rules are clearly listed on the web site. It is not yet mentioned, however, whether the host SC will use the medal allocation algorithm suggested at the IOI workshop for computing their proposal on medal allocation to the GA.

For your travel to IOI 2006, it is highly recommended to take a flight to Merida. The alternative airport in Cancun is pretty far away from Merida, and a long bus drive is required to go to Merida.

back to table of contents


Competition Workshop

After initial discussions at IOI 2003, a first presentation to GA at IOI 2004, and an announcement at IOI 2005, it finally took place in January 2006: A workshop on computer science competitions, closely related to IOI but open to other interested people. In the end, Dagstuhl castle with its International Conference and Research Centre for Computer Science, saw 22 participants, including guests like the President of IOI, Zide Du, ACM-ICPC International Steering Committee Member and Problem Archivist, Miguel Revilla Ramos, the chairman of IOI 2005 and IC member, Krzysztof Diks, and the in-spe chairman of the IOI 2007 scientific committee, Igor Urbiha. Many other members of the IOI family were present, like ISC chairman Tom Verhoeff, ISC member Gordon Cormack, and IC member and workshop chair Wolfgang Pohl. The programme committee had accepted 14 papers for presentation, coming from all over the world (several papers from Europe, but also Canada, China, and New Zealand were represented).

The workshop was organized into two parts. The first two days saw paper presentations with a lot of discussion already going on. During the other two days, participants worked in three groups, dealing with the impact of IOI to the rest of the world, with scientific and task-related aspects, and with IOI policies and structures. In the end, each group documented the results of their discussion in a Wiki which can be read by everyone. Persons interested in actively contributing to this documentation may contact any workshop participant. Papers and presentations are documented at the workshop web site.

In a closing session, participants expressed their satisfaction with the workshop and its results. Discussions were considered very inspiring, and several ideas will be first implemented at IOI 2006. But results will not only become visible within the IOI community. Selected papers were elaborated and published in a special issue of the international journal "Informatics in Education" (Vol.5, No.1). Thus, the workshop may have given birth to a new scientific community with computer science contests as central topic.

back to table of contents


ISC Report: Grading and Feedback at IOI 2006

by Tom Verhoeff and Gordon Cormack for the ISC

Summary: For IOI 2006, new scoring criteria replace the "50% rule" introduced in 2004. Each test case is a set of runs designed to test some explicitly defined correctness or efficiency criterion. Points will be awarded for each case, not for the individual runs. Because this scoring scheme is more rigorous, the change is offset by graduation of the difficulty of the test case criteria, and by the provision of real-time feedback so that contestants may detect and correct trivial mistakes. The new rules are intended to make the tasks approachable yet challenging, while providing more transparent and deterministic evaluation.

The IOI 2006 Competition Rules include some details on how the IOI 2006 competition will be conducted and how the submitted work of the contestants will be graded. In particular, the section on "Grading" replaces the principles (commonly known as 50%-rule) established for IOI 2004. The goals have not changed, but the mechanism for achieving those goals has been refined.

For IOI 2004 and IOI 2005, we applied the following principles; see http://olympiads.win.tue.nl/ioi/sc/documents/principles-2004.txt.

  1. The competition tasks will be selected to cover a range of difficulty levels.
  2. For each task, half of the test inputs used for grading the submitted programs will focus on "testing for correctness". These inputs will be based on "small" cases only. What is considered "small" will be stated explicitly in the task description. These constraints will be referred to as 50%-constraints in this document, to distinguish them from the regular constraints (or 100%-constraints) on inputs.
  3. The other half of the test inputs will focus on "testing for efficiency". The "size" of these cases is chosen to distinguish the efficiency for a range of algorithm classes specific to that task.

Principle 1 still stands, but principles 2 and 3 have been refined. Note that the choice of 50% rather than some other percentage was a compromise to ensure

At the IOI-initiated workshop "Perspectives on Computer Science Competitions for (High School) Students" last January in Dagstuhl, Germany, the topic of evaluation was high on the agenda (see the published papers). In particular, test data design and the so-called 50%-rule were discussed. Similar discussions took place at the ISC Review Meeting last March in Mexico.

In summary, the main conclusions are:

The ISC decided to address the issues to some extent as follows.

  1. Adopt a more rigorous approach to testing, where larger sets of test runs are combined into a test case, whose result is the minimum score of the constituent test runs.
  2. Design each test case to assess a well-defined characteristic of the submitted program. This characteristic can be related to correctness and/or efficiency, and it will be published afterwards. Some (zero or more), but not necessarily all, of these characteristics will be defined explicitly in the task description.
  3. Provide more feedback to contestants on their submissions during the competition.

Notes:

Score differences among contestants can be attributed to two sources:

For example, consider a flawed algorithm implemented in two slightly different ways: program A traverses the input list from head to tail, program B from tail to head. The scores for these programs could differ considerably depending on the test data, if the data are not symmetric with respect to list reversal. That score difference is then a consequence of the choice of test data, rather than difference in achievement. We cannot justify such a score difference to contestants; to them it is an arbitrary fluctuation.

Principles 4 and 5 stated above (test cases with minimum scoring devoted to well-defined characteristics) enable us to reduce the influence of chance and arbitrariness on scores, and to reduce the opportunity for gamble-and-bluff programs to grab a significant score.

By properly weighing the test cases, the score can be adjusted proportional to the perceived achievement associated with each characteristic. For instance, one characteristic could concern an easier version of the task (by imposing an additional constraint on the inputs), which could be awarded 30% of the maximum score.

The all-or-nothing nature of test case scoring will also make it harder than in previous years to obtain credit on tasks of similar difficulty level. In particular, small implementation errors will be penalized harder. However, it is the intention that a number of test cases is truly easy, though not trivial. Also principle 6 (more feedback to contestants during the competition) is intended to counteract this. The feedback will help contestants detect implementation errors. Feedback at IOI 2006 is not intended to provide information on the actual score obtained, though we may wish to do so in the future.

Not all consequences of these changes can be foreseen. We will conduct a careful analysis of the IOI 2006 competition to investigate the effect of the new principles.

back to table of contents


Java in the IOI

by Jyrki Nummenmaa and Rob Kolstad, March 19, 2006

The ISC and the ITWG have continued to follow up on developments in Java programming environments to assess the possibilities to incorporate Java into the IOI.

It appears that the Sun's Java 1.5 SDK is the only affordable Java system coming close to meeting IOI's need. The following evaluation is based on this choice and primarily on the statistical data from the USACO contests, including some other smaller-scale testing. USACO has run 5 monthly contests using this compiler, just under 5000 entries, of which 6% is Java.

The following summarizes these findings. Two major barriers prohibit the use of Java in the IOI in the present setup.

Firstly, the execution times are larger by a magnitude and dependent on how the solution is implemented. The overhead of starting a Java solution includes 210 ms overhead of startup overhead and 500 ms memory initialization overhead. The memory allocation seems to be highly CPU-intensive and the impact of Java garbage collection is not known well enough at the moment.

Only one particular style of Java file input runs close to fast enough for IOI-style input files of reasonable size, and even then there seems to be an input time overhead.

In general, assuming that x is the execution time of a conceptually comparable C/C++ program, the execution time of a Java program can be expressed as Ax+B, where A typically is around 2 and B could be nearly 1 second. However, A and B can vary significantly depending of the actions of the program (meaning not just the task but also the implemented solution strategy).

The second problem is memory consumption. It is very diffcult to estimate and thereby reasonably limit the memory consumption in the JVM environment. Also, this depends on the libraries loaded into the JVM, as they also consume the same memory, and there, of course, could be different choices for the libraries used in the program.

There are some proposals for overcoming these difficulties and the ISC and ITWG will continue to explore possibilities to solve these issues in the hope that they will be able to recommended the use of Java in the future.

However, at the moment we do not see Java as a fair choice for a programming language in the IOI. At the March review meeting it was decided not to allow Java at IOI 2006.

back to table of contents


ITWG highlights

ITWG has been working on the IOI Practice CD, the latest version of which was made available recently. The Practice CD has become a useful vehicle for learning about the IOI competition environment. It allows every contestant to practice with a Linux-only environment, so that the IOI competition environment can be based on Linux only without leaving anyone behind. A Linux-only environment on contestant computers, as it will be used at IOI 2006 for the first time, will make life of the technical people at an IOI much easier. Furthermore, the practice CD may even be used to boot contestant computers, in particular in smaller contests. This method has successfully been used at the Baltic Olympiad in Informatics (BOI) 2006 in Finland.

The second main ITWG project is an IOI information system. Part of it is the registration system which is now being used for the first time by the organizers of IOI 2006. Using a centralized system allows IOI organizers to maintain data that is valid over the years. The first example is the contact person registration, which is required for all countries that will send a delegation to IOI 2006.

back to table of contents


Call for Translation Volunteers

IOI documents are provided in English, which, according to IOI regulations, is the official working language of IOI. However, English texts are not similarly accessible to all IOI members. We therefore call for volunteers, who are willing to translate IOI documents like competition rules, GA/IC/ISC agendas and minutes, and other documents provided to GA for discussion and decision. Also this newsletter may itself be translated!

Any volunteers please contact the ED: ioi-ed@bwinf.de

back to table of contents


Responsible: Wolfgang Pohl, IOI, Office of the Executive Director