Olympiad programming tasks: what kind of beast?

We recently announced a competition for sports programming tasks . The contest organizers asked to write a short announcement about the contest to the ABBYY blog, but the strict editor refused to print the announcement without explaining what the olympiad challenge was. From this was born the whole article. Let's start with the example of the olympiad problem.

The first thing that catches your eye is an unusual condition. Such an approach has developed historically: it is not accepted to write a brief mathematical formulation. Usually they try to connect it with real life, well, or not so real . For example, at USACO, the heroes of all the tasks are farmer John and the cows. Before proceeding to the solution after reading the conditions, the participant is required to select the mathematical formulation of the problem.

The solution of the Olympiad problem is a program written in one of the programming languages. The most popular languages ​​are: C ++, C #, Java, Pascal. You might say that Pascal has long been outdated. However, do not underestimate him! Experienced sports programmers are able to write standard algorithms on Pascal that already exist in C ++, faster than an ordinary person will read the condition of the problem :) By the way, because participants choose a programming language on their own, there is a risk that they make a non-optimal choice . Firstly, solutions do not exist in all languages, and secondly, solutions written in some languages ​​may work less efficiently than in others.

Let us return to the discussion of the conditions. Olympiad tasks are very formalized :

• strict input / output format, sometimes even up to spaces and line breaks;
• conditions, as a rule, have a strict unambiguous interpretation. This is where you can learn from customers in writing TK!
• strict limits on runtime and memory used. In real-world development, you are more likely to be told something in the style of “ we want it to work on such and such hardware and on such and such OS ” or “ listen, your program eats too much memory ”. Far less often you can hear phrases like “ your program should work no more than 1.5 seconds ” or “ don’t dare use more than 64 megabytes of memory ”;
• all initial values ​​are strictly limited.

Such strict formalization is justified. All decisions of competitors are checked on a set of tests, which is prepared by the jury of the Olympiad and is usually not known to participants in advance.

The next feature is the analysis of tasks. The author of the olympiad problem thinks about how many percent of the participants will solve such a task, for what time (up to minutes), to which subject this task belongs (for example, a task on graphs or a task on a greedy algorithm).

In general, there are two types of olympiad tasks: “ classical ” and “ heuristic ”. Classical problems require an exact, rigorously proven solution. When solving heuristic problems, participants compete with each other, who can get the best answers. For example, whose solution correctly recognizes more characters. Heuristic problems usually do not have exact solutions. Here they are most close to real development. For example, character recognition is quite a “heuristic” task.

There are many ways to evaluate solutions for "classical" problems:

• The problem is considered solved if the participant's solution worked correctly on all tests. This rating system is used in ACM competitions.
• points are awarded for the decision, depending on the number of tests successfully passed by the program. This approach is often used at school competitions: no one will leave offended from the competition and will receive at least 0.5 points.
• Tests are combined into groups, for each of which a certain number of points is awarded. It should be noted that points for a group are awarded only if the solution worked correctly on all tests from the group. This is a reasonable compromise between justice and the satisfaction of the participants. The ABBYY Cup professes exactly this form of decision evaluation;
• sometimes the number of points received by the participant depends on the time spent on solving the problem. For example, such a system is used on Codeforces and Topcoder.

Estimates of the solutions of "heuristic" problems in each case are developed individually. In the heuristic problem , which was proposed to be solved by the finalists of ABBYY Cup 2.0, it was necessary to develop a program for classifying documents by subject. The solution was tested on a group of tests, each of which contained a certain set of texts on different topics. In total there were three subjects, and each of them was represented in each group in a different quantity. Won the one whose decision passed the greatest number of groups of tests. When installing a “heuristic” task on a testing platform, it is sometimes necessary to refine it, since most of the testing platforms are “sharpened” for evaluating classical problems.

Of course, one can talk endlessly about the features of Olympiad tasks. We covered only the most important moments. If you have questions or comments - welcome to comments. And if you can and love to write the tasks described in the article, we can talk about it here .

Vladimir Minyaylov, Department of Technology NLC,
Ruzan Miniakhmetova, a group of educational projects.