5. Authoring problems

This page is intended as a resource for people who wish to create olympiad problems. It's mostly here because members of South African training squad are required to produce problems for the other members to attempt, so I felt it would be useful to have some advice.

Before even considering the details of problem statements and test data, it is necessary to have a problem. This is not as difficult as it might at first sound, because it is not always necessary to have a brilliant and original problem. There are lots of existing problems, many of which are linked to from the IOI secretariat. While you cannot copy the problem text or test data without the permission of the copyright holder, you can re-use an idea and just re-theme it. It is also not the case that hard problems are better: problems need to be chosen according to their target contests (or vice versa), and most contests aim for a range of difficulties. Easy but novel problems are probably the rarest.

Assuming you have an original idea, or are adapting an idea from another problem, your next step is to think up solutions. Don't stop as soon as youe found a fast but complicated solution; there may be equally fast but simpler solutions. You should also consider what slower solutions people may use, since you may need to separate them from the faster ones, or in some cases you may decide that the faster solutions are too difficult and decide to give full credit to a slower solution. It is generally impractical to try to distinguish O(N) from O(N.log N) or sometimes even O(N2), because the I/O will tend to dominate the running time, and will vary enormously between languages (also keep in mind that, for example, a permutation of the numbers from 1 to N takes O(N.log N) digits in the input file). Often it is possible to tweak the problem slightly, for example by adding an extra loop around the outside, so that the relative impact of I/O shrinks. This will also reduce the size of input files, which makes them more practical to store and distribute and reduces that noise that could be introduced by disk caches and so on.

Once you have a good idea for a problem and know what reward you want to give to various solutions, you are ready to begin writing the problem statement.

  1. The problem statement
  2. Creating test data
  3. Evaluating the problem

[Prev] [Next] [Up]

Last updated Mon Jun 19 17:45:45.0000000000 2006. Copyright Bruce Merry (bmerry '@' gmail dot. com).