Programming Olympiad, view from NSU. Article 1 - drawing up tasks
Next year will be my fifth and last season in ACM Olympiads. Over the years, many different memories and knowledge about the Olympiads have been accumulated, since my university participates in them very actively. Telling only from the participant will not be entirely correct, since many people can participate in competitions, I also happened to be on the jury (albeit at school olympiads). I'll tell you some interesting things from the inside, let us slightly open our backstage. The story will be closely connected with the Open All-Siberian Olympiad, since I have the closest communication with it (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 preparation of tasks for these competitions. The case is fascinating, creative, but sometimes very dreary.
2-3 years, I write tasks for school competitions at various levels. I haven’t gotten to the student ones yet, because I’m still quite playing myself and want to participate (although, as I remember, I took one of my tasks for the NSU personal olympiad; I rarely participate in personalities).
')
Weeks 3 weeks before any school competition, our coaches collect the “old men” - the first 4 teams of the NSU - indoors and perplex. The task is to pick 10-12 tasks, of which 8 or 8 are recruited for the tour.
First come up with raw ideas. Firstly, there should be no bias in any area of ​​Olympiad programming, it’s good for training - either to train all day long on geometry, or work out the dynamics. In the finished Olympiad should be more or less equally. One or two tasks on graphs, almost necessarily - one geometry, something in combinatorics. Sometimes a simple terver (schoolchildren, you have to regret). A couple of tasks for dynamic programming, one for processing strings, and most importantly, one “comforter”. Secondly, it is necessary to sustain the general level of the Olympiad. If the goal is the selection for the next level Olympiad, then you should not get involved in complex tasks; if the tournament finals take place, then you can show a small slice of sadism by releasing 1-2 candid coffins in order to separate just good coders from real tops.
So, the think tank always has a couple of ideas in each store. Express, write, distribute. In the end, it turns out the very 10-12 tasks, some of which are eliminated in the course of the play (due to the 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 problem idea. Usually, but not always. If the author has trouble with writing / the language is not suspended, then during the preparation in the course of the technical skeleton, the conditions, and his olympiad itself, is olititeratur. The most important thing is that both the trainers and the task mate 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 coiled, confusing and indigestible, and the solution simple and quick. Therefore, our team has a method of reading the problem from the bottom up. First, it looks at the format of the input / output data, then the restrictions on the execution time and free memory. If after that the hair does not stand on end, then you can take up the decision. But about the tours a little later, now we only have training.
Conditions are different. There are strictly mathematical (as, for example, Shilov's problems in Vsesib - almost always there is a task from him on the parser of some language, given formally). There are strictly humorous (for example, our team, consisting of ardent football fans, for about 5 minutes, the task of football player Vladislav Bulanov and team owner Harold Ivanovich Nerr put out of action). The main thing - do not overdo it with neither one nor the other. The quintessence of the conditions, in my opinion, is the idea of ​​Misha Kalugin to entrust the writing of the task of adding two numbers to a professional psychoanalyst, with a permanent development in the reader who read the fear of closed spaces, open spaces, the Java language and the number 13.
Okay, that's enough for the conditions. Now about solutions. The solution is necessarily written by the author of the problem, and his assistant. It is desirable - in different languages ​​(in the case of school competitions: c ++ / pascal, for student: c ++ / java). Tests are not usually written by the author of the problem. Why is this done? The fact is that when a task is drafted entirely by one person, any subtleties can be left out, extreme cases are missed, and in general, a non-optimal solution has been chosen. When a solution is written by two more or less knowledgeable people independently, it is more likely to be correct.
In the process of writing solutions, the conditions of the problem often change. Restrictions - so they change a thousand times, with the goal of either passing or failing to make certain decisions. If Java is enabled, then time / memory limits may increase. Sometimes there is suddenly a hole in the condition or a counterexample, which is one of the solutions. As a result, in the process of interactions, 2 decisions arise, they are the notorious “decisions of the jury”, infallible and incomparable =).
Everything is more or less clear. A checker is written if the problem has more than one solution and only one arbitrary possible is required. In this case, a program is written that checks the optimality for input and output data. Otherwise, if the correct solution is only one, the test is completely at the mercy of the testing system. From the authors - only sets of input and output tests.
Now about the tests. Here is divided into two categories. If the Olympiad is held according to the ACM rules, then the soul breaks away. In this case, the test passes only the task that passes absolutely all the tests and is written with the authors of the optimal asymptotics of the size of the input data. With a correction constant in the region of 2-3, because the author is 2-3 calm weeks writing the jury's decision from the author, and olympionics are invited to write 10 decisions in 5 hours in the wild boom. Tests are written on the boundary values ​​(check what will happen with the minimum values ​​of the input data - often, many people lose sight of cases with zero input data). Maxstas are written - often non-optimal solutions or decisions are written on them, where the writers inaccurately dealt with arrays (oh, yes, always add a dozen extra elements). In the case of geometry, tests are written, on which guys who are at enmity with accuracy and epsilon are cut. Random tests are written, if you need a lot - then test generator. And if laziness - the show is written.
A little offtopic:
When I was second-year students, my constant partner and good friend Misha Gorodilov and I were tests for a simple task. The input is one number up to 10 ^ 18, the output is two numbers. I didn't want to write a random number generator. As a result: in the tests the jury had our phone numbers, barcodes from a can of coffee and a bottle of Coca-Cola, and even, at the end, the result of two beats on the keyboard. For us it was then faster than writing a generator
So, but with school olympiads, the situation is somewhat different. As already mentioned in the comments on a recent topic, there is another evaluation system. Points are awarded for the number of tests passed. Everything went - 100, only input or none - 0. And between them - all our tumult of fantasy. First, the restrictions on the full choice solution are considered. 3-4 tests for points 15-20 go there. That was not insulting. Further possible non-ideal variants and asymptotics are considered. The algorithm works for O (N ^ 3) - here is a death pill. For O (N ^ 2) - that’s him. For O (NlogN) - good. Here is his makstest and if the asymptotic constant is good, then there will be 100 points. With geometries, again, the cut-off is performed on complex tests where increased accuracy is needed. Well, in this case, a pair of input / output data sets is spilling.
Look like that's it. The conditions are written, there are solutions, it remains to load everything into the testing system and make a waving checkered flag. But about this - 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 preparation of tasks for these competitions. The case is fascinating, creative, but sometimes very dreary.
2-3 years, I write tasks for school competitions at various levels. I haven’t gotten to the student ones yet, because I’m still quite playing myself and want to participate (although, as I remember, I took one of my tasks for the NSU personal olympiad; I rarely participate in personalities).
')
Where it all begins
Weeks 3 weeks before any school competition, our coaches collect the “old men” - the first 4 teams of the NSU - indoors and perplex. The task is to pick 10-12 tasks, of which 8 or 8 are recruited for the tour.
First come up with raw ideas. Firstly, there should be no bias in any area of ​​Olympiad programming, it’s good for training - either to train all day long on geometry, or work out the dynamics. In the finished Olympiad should be more or less equally. One or two tasks on graphs, almost necessarily - one geometry, something in combinatorics. Sometimes a simple terver (schoolchildren, you have to regret). A couple of tasks for dynamic programming, one for processing strings, and most importantly, one “comforter”. Secondly, it is necessary to sustain the general level of the Olympiad. If the goal is the selection for the next level Olympiad, then you should not get involved in complex tasks; if the tournament finals take place, then you can show a small slice of sadism by releasing 1-2 candid coffins in order to separate just good coders from real tops.
So, the think tank always has a couple of ideas in each store. Express, write, distribute. In the end, it turns out the very 10-12 tasks, some of which are eliminated in the course of the play (due to the complexity / failure / repetition).
What do next with the 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 problem;
- checker (optional on the type of task)
Conditions
The condition is usually written by the author of the problem idea. Usually, but not always. If the author has trouble with writing / the language is not suspended, then during the preparation in the course of the technical skeleton, the conditions, and his olympiad itself, is olititeratur. The most important thing is that both the trainers and the task mate 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 coiled, confusing and indigestible, and the solution simple and quick. Therefore, our team has a method of reading the problem from the bottom up. First, it looks at the format of the input / output data, then the restrictions on the execution time and free memory. If after that the hair does not stand on end, then you can take up the decision. But about the tours a little later, now we only have training.
Conditions are different. There are strictly mathematical (as, for example, Shilov's problems in Vsesib - almost always there is a task from him on the parser of some language, given formally). There are strictly humorous (for example, our team, consisting of ardent football fans, for about 5 minutes, the task of football player Vladislav Bulanov and team owner Harold Ivanovich Nerr put out of action). The main thing - do not overdo it with neither one nor the other. The quintessence of the conditions, in my opinion, is the idea of ​​Misha Kalugin to entrust the writing of the task of adding two numbers to a professional psychoanalyst, with a permanent development in the reader who read the fear of closed spaces, open spaces, the Java language and the number 13.
Solutions
Okay, that's enough for the conditions. Now about solutions. The solution is necessarily written by the author of the problem, and his assistant. It is desirable - in different languages ​​(in the case of school competitions: c ++ / pascal, for student: c ++ / java). Tests are not usually written by the author of the problem. Why is this done? The fact is that when a task is drafted entirely by one person, any subtleties can be left out, extreme cases are missed, and in general, a non-optimal solution has been chosen. When a solution is written by two more or less knowledgeable people independently, it is more likely to be correct.
In the process of writing solutions, the conditions of the problem often change. Restrictions - so they change a thousand times, with the goal of either passing or failing to make certain decisions. If Java is enabled, then time / memory limits may increase. Sometimes there is suddenly a hole in the condition or a counterexample, which is one of the solutions. As a result, in the process of interactions, 2 decisions arise, they are the notorious “decisions of the jury”, infallible and incomparable =).
Tests and checkers
Everything is more or less clear. A checker is written if the problem has more than one solution and only one arbitrary possible is required. In this case, a program is written that checks the optimality for input and output data. Otherwise, if the correct solution is only one, the test is completely at the mercy of the testing system. From the authors - only sets of input and output tests.
Now about the tests. Here is divided into two categories. If the Olympiad is held according to the ACM rules, then the soul breaks away. In this case, the test passes only the task that passes absolutely all the tests and is written with the authors of the optimal asymptotics of the size of the input data. With a correction constant in the region of 2-3, because the author is 2-3 calm weeks writing the jury's decision from the author, and olympionics are invited to write 10 decisions in 5 hours in the wild boom. Tests are written on the boundary values ​​(check what will happen with the minimum values ​​of the input data - often, many people lose sight of cases with zero input data). Maxstas are written - often non-optimal solutions or decisions are written on them, where the writers inaccurately dealt with arrays (oh, yes, always add a dozen extra elements). In the case of geometry, tests are written, on which guys who are at enmity with accuracy and epsilon are cut. Random tests are written, if you need a lot - then test generator. And if laziness - the show is written.
A little offtopic:
When I was second-year students, my constant partner and good friend Misha Gorodilov and I were tests for a simple task. The input is one number up to 10 ^ 18, the output is two numbers. I didn't want to write a random number generator. As a result: in the tests the jury had our phone numbers, barcodes from a can of coffee and a bottle of Coca-Cola, and even, at the end, the result of two beats on the keyboard. For us it was then faster than writing a generator
So, but with school olympiads, the situation is somewhat different. As already mentioned in the comments on a recent topic, there is another evaluation system. Points are awarded for the number of tests passed. Everything went - 100, only input or none - 0. And between them - all our tumult of fantasy. First, the restrictions on the full choice solution are considered. 3-4 tests for points 15-20 go there. That was not insulting. Further possible non-ideal variants and asymptotics are considered. The algorithm works for O (N ^ 3) - here is a death pill. For O (N ^ 2) - that’s him. For O (NlogN) - good. Here is his makstest and if the asymptotic constant is good, then there will be 100 points. With geometries, again, the cut-off is performed on complex tests where increased accuracy is needed. Well, in this case, a pair of input / output data sets is spilling.
Look like that's it. The conditions are written, there are solutions, it remains to load everything into the testing system and make a waving checkered flag. But about this - in the following articles.
Source: https://habr.com/ru/post/62655/
All Articles