Probably a lot of coders ever tried to solve tasks from programming contests: in codeforces.com, school olympiads, ACM ICPC, or somewhere else. Most people use C++ to solve tasks.
I used to enjoy solving these tasks and even occasionally prepared tasks for codeforces and for school olympiads. It is called “problemsetting”. I have prepared around 15-20 tasks.
This work is paid quite symbolically. Therefore, this is mainly done by students – former top contest solvers who have not yet graduated from university and have not found a decent job yet. Then they get bored and are replaced by a new generation of students.
I’ll show example of problemsetting on this task: Codeforces Round #704 - E. Almost Fault-Tolerant Database. This is the hardest task of the round despite its simple description.
People prepare tasks mainly on polygon.codeforces.com. This is the most advanced problemsetting service, and has been the only working service for a long time. The other problemsetting services (CodeChef, Yandex.Contest, etc.) have borrowed features from it – like validation, embedded version control system, and so on.
To write small programs (generators, checkers) testlib.h is used.
The task preparation process consists of these steps:
- Invention of the unique problem idea in a short formulation.
- A fancy description of the task is created in LaTeX - example, this is called the legend of the task.
- Test cases generators are written, this can be a handful of simple scripts – example 1, example 2. They are run with different arguments to generate test cases.
- The validator is written. It is needed to check that the test cases have the right format and satisfy the constraints described in the legend - example.
- Test cases are generated using the Freemarker template engine. It is possible to write a script that transforms to generator calls - example from docs. Our task has 100 tests - the list.
- The author’s solution is written. There is the only one reference solution - example, but some deliberately wrong solution (with wrong idea or slow) are also to be written. They are needed to make sure that no wrong solution passes all the tests.
- The checker is written. It is needed to check the participants’ solutions correctness. The polygon service has some default checkers for simple output formats, but usually it is needed to write a unique checker. It is especially needed when the task could have more than one correct answer - example.
This is a quite serious job, so fellow problemsetters should conduct code review of your scripts and solutions as well as proofreading of the legend.
About 5-15 people of different problem solving skills solve the new task without knowing the solution in advance. They can come up with an unexpected simpler solution, or pass all the tests with a wrong solution - all these cases are considered separately.
According to the law of large numbers, epic fails of this kind do occur for one out of dozens of tasks:
- A large fraction of participants came up with a simpler solution, so the complexity of the task is actually smaller.
- The task has weak tests, so many “wrong” or “slow” solutions pass all the tests.
- The author’s solution is incorrect.
The first two kinds of epic fails are somewhat acceptable, but the third one is a complete shitshow, and Codeforces cancels the ongoing contest immediately if this is detected (more precisely, the contest is declared as “unrated”, and it makes little sense to participate in it at all).