June 22, 2009 at 20:48Programming Olympiads, a look from NSU. Article 1 - Drafting Tasks
Next year will be my fifth and last season at the ACM Olympiads. Over the years, many different memories and knowledge about the Olympiads have accumulated, since my university participates in them very actively. Talking only from the side of the participant will not be entirely correct, since many can participate in the Olympiads, but I also happened to be on the jury (though, school olympiads). I’ll tell you a few interesting things from the inside, I will slightly open our backstage a little. The story will be closely connected with the Open All-Siberian Olympiad, because I have the closest communication with her (and it is conducted by our university).
The second article is about testing systems.
The third article is about the work of the organizing committee.
The fourth article is about the tour itself.
In the first article I want to talk about the compilation of tasks for these olympiads. The case is fascinating, creative, but sometimes very dreary.
About 2-3 years I write tasks for school olympiads of different levels. I still haven’t reached the student ones, because I myself still play quite well and I want to participate myself (although, as I recall, one of my tasks was taken to the NSU personal olympiad; I rarely participate in PMs).
About 3 weeks before any school olympiad, our coaches collect the "old people" - the first 4 teams of NSU - indoors and are puzzled. The task is to pick 10-12 tasks, of which 8 are recruited to the tour.
At first raw ideas are thrown. Firstly, there should not be a bias in any area of Olympiad programming, it’s good to train - either train all day on geometry, or work out dynamics. In ready-made olympiads, everything should be more or less even. One or two problems on graphs, almost necessarily - one geometry, something combinatorics. Sometimes a simple terver (after all, schoolchildren need to be sorry). A couple of tasks for dynamic programming, one for processing strings, and most importantly, one “console”. Secondly, you need to maintain the overall level of the Olympiad. If the goal is selection for the next level olympiad, then one should not get carried away with complex tasks; if the tournament finals pass, then you can also show a small piece of sadism by releasing 1-2 frank coffins in order to separate just good coders from real tops.
So, the think tank always has a couple of ideas in each of them. Speak, record, distribute. As a result, we get those very 10-12 tasks, some of which are eliminated during the play (due to complexity / failure / repetition).
Each task goes to a couple of people, preferably from different teams. Further, each of them gets 2-3 tasks from the list:
The condition is usually written by the author of the idea of the problem. Usually, but not always. If the author of a disagreement with the written work / language is not suspended, then the technical skeleton is prepared during the preparation of the course, and it is literate for the Olympiad itself. The most important thing is that both the coaches and the partner in the task are able to realize what is required in the decision and how to do it. There are, of course, incidents. The condition can be specially wound, confusing and indigestible, and the solution is simple and quick. Therefore, our team is using the method of reading the task from the bottom up. First, the format of the input / output data looks, then the restrictions on the execution time and free memory. If after this the hair does not stand on end, then you can take on the decision. But about the tours a little later, now we have only preparation.
The conditions are different. There are strictly mathematical ones (like, for example, Shilov’s tasks on Vsesibakh - there’s almost always a task from him to the parser of some language defined formally). There are strictly humorous ones (for example, our team, which consisted of ardent football fans, was put out of action for about 5 minutes by a task about the football player Vladislav Bulanov and the owner of the team Harold Ivanovich Nerr). The main thing is not to go too far with either one or the other. The quintessence of conditions, in my opinion, is the idea of Misha Kalugin to entrust the writing of the addition of two numbers to a professional psychoanalyst, with the urgent development of the reader who fears closed spaces, open spaces, the Java language and the number 13.
Okay, enough for the conditions. Now about the solutions. The solution is mandatory written by both the author of the task and his assistant. Desirable - in different languages (in the case of school competitions: c ++ / pascal, for students: c ++ / java). Tests are usually not written by the author of the task. Why is this done? The fact is that when drawing up the task as a whole, one person may not be affected by any subtleties, extreme cases are missed, and indeed - the non-optimal solution method is chosen. When a decision is written independently by two more or less knowledgeable people, it is much more likely to be correct.
In the process of writing decisions, the conditions of the problem often change. Limitations - so those change a thousand times, with the goal of either passing or not passing certain decisions. If Java is enabled, then time / memory limits can increase. Sometimes a hole is suddenly found in a condition or a counterexample lying around one of the solutions. As a result, in the process of interactions 2 decisions arise, they are the notorious “jury decisions”, infallible and invincible =).
Everything is more or less clear here. A checker is written if the task has more than one solution and only one arbitrary possible is to be deduced. In this case, a program is written that checks input and output data for optimality. Otherwise, if there is only one correct solution, the test is completely left to the testing system. From the authors - only sets of input and output tests.
Now about the tests. It is divided into two categories. If the competition is held according to the rules of ACM, then the soul comes off. In this case, the test passes only that task that passes absolutely all the tests and is written with the optimal asymptotics assumed by the authors of the size of the input data. With a correction constant in the region of 2-3, because the author has written 2-3 weeks to write the decision of the jury, and Olympic athletes are invited to write 10 decisions in 5 hours in the wild. Tests for boundary values are written (to check what happens with the minimum values of the input data - often many overlook cases with zero input data). Macstests are written - they often pour non-optimal solutions or solutions where the writers inaccurately handled arrays (oh yes, I always add a dozen extra elements). In the case of geometry, tests are written, on which the guys who are in enmity with precision and epsilons are cut. Random tests are written, if you need a lot, then a test generator. And if laziness - a show is written.
A little offtopic:
When we were sophomores, my constant workmate and good friend Misha Gorodilov and I made tests for a simple task. The input is one number up to 10 ^ 18, the output is two numbers. I did not want to write a random number generator. As a result: in the tests of the jury there were also our phone numbers, and barcodes from a coffee can and a bottle of Coca-Cola, and even, in the end, the result of two head hits on the keyboard. For us, it was faster then writing a generator.
So, with school olympiads the situation is somewhat different. As mentioned in the comments on the recent topic, there is a different rating system. Points are awarded for the number of tests passed. Everything passed - 100, only the input or none - 0. And between them - all our riot of fantasy. First, the restrictions on a full collapsible solution are considered. 3-4 tests are sent there for points 15-20. To not be offended. Further non-ideal options and asymptotics are considered. The algorithm works for O (N ^ 3) - here is a death pill for him. For O (N ^ 2) - that's him. O (NlogN) is good. Here is the maxtest for him, and if the asymptotic constant is good, then there will be 100 points. With geometries, again, cut-offs take place on complex tests where increased accuracy is needed. Well, in this case, a couple of the input / output data set is scoring.
Look like that's it. The conditions are written, there are solutions, it remains to load everything into the testing system and wave the checkered flag. But more about that in the following articles.
The second article is about testing systems.
The third article is about the work of the organizing committee.
The fourth article is about the tour itself.
In the first article I want to talk about the compilation of tasks for these olympiads. The case is fascinating, creative, but sometimes very dreary.
About 2-3 years I write tasks for school olympiads of different levels. I still haven’t reached the student ones, because I myself still play quite well and I want to participate myself (although, as I recall, one of my tasks was taken to the NSU personal olympiad; I rarely participate in PMs).
Where does it all begin
About 3 weeks before any school olympiad, our coaches collect the "old people" - the first 4 teams of NSU - indoors and are puzzled. The task is to pick 10-12 tasks, of which 8 are recruited to the tour.
At first raw ideas are thrown. Firstly, there should not be a bias in any area of Olympiad programming, it’s good to train - either train all day on geometry, or work out dynamics. In ready-made olympiads, everything should be more or less even. One or two problems on graphs, almost necessarily - one geometry, something combinatorics. Sometimes a simple terver (after all, schoolchildren need to be sorry). A couple of tasks for dynamic programming, one for processing strings, and most importantly, one “console”. Secondly, you need to maintain the overall level of the Olympiad. If the goal is selection for the next level olympiad, then one should not get carried away with complex tasks; if the tournament finals pass, then you can also show a small piece of sadism by releasing 1-2 frank coffins in order to separate just good coders from real tops.
So, the think tank always has a couple of ideas in each of them. Speak, record, distribute. As a result, we get those very 10-12 tasks, some of which are eliminated during the play (due to complexity / failure / repetition).
What next do with ideas?
Each task goes to a couple of people, preferably from different teams. Further, each of them gets 2-3 tasks from the list:
- the task;
- the solution of the problem;
- tests for the task;
- checker (optional on the type of task)
Conditions
The condition is usually written by the author of the idea of the problem. Usually, but not always. If the author of a disagreement with the written work / language is not suspended, then the technical skeleton is prepared during the preparation of the course, and it is literate for the Olympiad itself. The most important thing is that both the coaches and the partner in the task are able to realize what is required in the decision and how to do it. There are, of course, incidents. The condition can be specially wound, confusing and indigestible, and the solution is simple and quick. Therefore, our team is using the method of reading the task from the bottom up. First, the format of the input / output data looks, then the restrictions on the execution time and free memory. If after this the hair does not stand on end, then you can take on the decision. But about the tours a little later, now we have only preparation.
The conditions are different. There are strictly mathematical ones (like, for example, Shilov’s tasks on Vsesibakh - there’s almost always a task from him to the parser of some language defined formally). There are strictly humorous ones (for example, our team, which consisted of ardent football fans, was put out of action for about 5 minutes by a task about the football player Vladislav Bulanov and the owner of the team Harold Ivanovich Nerr). The main thing is not to go too far with either one or the other. The quintessence of conditions, in my opinion, is the idea of Misha Kalugin to entrust the writing of the addition of two numbers to a professional psychoanalyst, with the urgent development of the reader who fears closed spaces, open spaces, the Java language and the number 13.
Solutions
Okay, enough for the conditions. Now about the solutions. The solution is mandatory written by both the author of the task and his assistant. Desirable - in different languages (in the case of school competitions: c ++ / pascal, for students: c ++ / java). Tests are usually not written by the author of the task. Why is this done? The fact is that when drawing up the task as a whole, one person may not be affected by any subtleties, extreme cases are missed, and indeed - the non-optimal solution method is chosen. When a decision is written independently by two more or less knowledgeable people, it is much more likely to be correct.
In the process of writing decisions, the conditions of the problem often change. Limitations - so those change a thousand times, with the goal of either passing or not passing certain decisions. If Java is enabled, then time / memory limits can increase. Sometimes a hole is suddenly found in a condition or a counterexample lying around one of the solutions. As a result, in the process of interactions 2 decisions arise, they are the notorious “jury decisions”, infallible and invincible =).
Tests and Checkers
Everything is more or less clear here. A checker is written if the task has more than one solution and only one arbitrary possible is to be deduced. In this case, a program is written that checks input and output data for optimality. Otherwise, if there is only one correct solution, the test is completely left to the testing system. From the authors - only sets of input and output tests.
Now about the tests. It is divided into two categories. If the competition is held according to the rules of ACM, then the soul comes off. In this case, the test passes only that task that passes absolutely all the tests and is written with the optimal asymptotics assumed by the authors of the size of the input data. With a correction constant in the region of 2-3, because the author has written 2-3 weeks to write the decision of the jury, and Olympic athletes are invited to write 10 decisions in 5 hours in the wild. Tests for boundary values are written (to check what happens with the minimum values of the input data - often many overlook cases with zero input data). Macstests are written - they often pour non-optimal solutions or solutions where the writers inaccurately handled arrays (oh yes, I always add a dozen extra elements). In the case of geometry, tests are written, on which the guys who are in enmity with precision and epsilons are cut. Random tests are written, if you need a lot, then a test generator. And if laziness - a show is written.
A little offtopic:
When we were sophomores, my constant workmate and good friend Misha Gorodilov and I made tests for a simple task. The input is one number up to 10 ^ 18, the output is two numbers. I did not want to write a random number generator. As a result: in the tests of the jury there were also our phone numbers, and barcodes from a coffee can and a bottle of Coca-Cola, and even, in the end, the result of two head hits on the keyboard. For us, it was faster then writing a generator.
So, with school olympiads the situation is somewhat different. As mentioned in the comments on the recent topic, there is a different rating system. Points are awarded for the number of tests passed. Everything passed - 100, only the input or none - 0. And between them - all our riot of fantasy. First, the restrictions on a full collapsible solution are considered. 3-4 tests are sent there for points 15-20. To not be offended. Further non-ideal options and asymptotics are considered. The algorithm works for O (N ^ 3) - here is a death pill for him. For O (N ^ 2) - that's him. O (NlogN) is good. Here is the maxtest for him, and if the asymptotic constant is good, then there will be 100 points. With geometries, again, cut-offs take place on complex tests where increased accuracy is needed. Well, in this case, a couple of the input / output data set is scoring.
Look like that's it. The conditions are written, there are solutions, it remains to load everything into the testing system and wave the checkered flag. But more about that in the following articles.