The mystery of creating rounds unveiled by author of the 4 of them!
The guide for preparing the round without horror-fiction and pastorals!
Also, many thanks to RodionGork for the translation of this post to English.
1. Inventing problems
It's hard to advise anything on this point. There's no some standard way of creating problems — and if one have existed we'll have only "complicated algorithmic exercises" instead of "problems". People who participated in Russian Code Cup do know well the tasks of that sort.
To cook good and interesting problem there should be some idea! which came to your mind (and later to minds of participants of the contest). Even the simplest problems of
A level for the
Div2 should have some idea.
So here is the warning: creative way of thinking is trained from the childhood — and since so, not all people are equally good in inventing problems. Alas! For me the experience of creating problems for "Youth Math School" challenges (held annually in St-Pete's, Russia) was of great help. Approximately after the year of offering boring and well-known technical exercises (which always failed to pass the jury filter), I have understand that one can't just "sit down and bring forth a cool problem". But if for significant period of time you roll the thought inside your head, examining different mathematical models from many points of view — then sooner or later you came up with interesting problem.
It is just like searching for mushrooms in the forest. You should not expect to go to some spot and pick the mushroom here. If you already know about some mushroom at some definite place — be sure, many people know it too — and obviously it already was picked. Moreover mushroom is not worth being called mushroom if all people know about it. :)
On contrary you need to wander for some time in unknown places, looking beneath the bushes and fallen leaves. Of course you should not expect to find the mushroom below any leaf. But sometimes you'll succeed. So "seek and you will find"!
It is not necessary to be the top-of-the-tops to be able to create problems
Div1. I myself am kicking around the border between yellow and red — nevertheless I created four full rounds! At one of them no one submit the correct solution for problem
E — while at another only two of contestants succeeded. And some people are slow thinkers and have no great career in competitive programming at all, but this does not hinder them from inventing and solving extremely complex puzzles when they have enough time.
2. The set of problems
Here the goal is clear: you already collected enough problems and you can try to organize them into the problem set for the round. Depending on circumstances it can have
7 problems (or some other amount in rare cases). The difficulty of problems is not strictly fixed — the most important is to order them by increasing difficulty (while contest could be somewhat more or less difficult overall). Because of this the same problem could become either
D level. Also sometimes non-standard "difficulty ladder" is acceptable — but of course not to extreme degree. I doubt anyone will agree to accept contest with 500-500-1000-1500-1500 levels.
When assessing the difficulty of the problem it is important to take into account all circumstances which make the solving more troublesome. Complexity of idea, complexity of implementation and exclusiveness of implementation. For example the blossom-shrinking will create far more troubles to solvers compared with cartesian tree, though complexity of implementation for these two algorithms is approximately equal. Other factors are difficulty of reading the problem statement (yes!) and amount of attention required for implementation (for example amount and inequality of the special cases if they exist).
3. Communicate with Gerald
Gerald is not terrible :) He is really cool! When you collected your set of problems you need just write to him by any suitable way (I myself used PM at this site) — after which you'll be able to choose another channels. I mostly communicated with him in social network while sending larger volumes of text (proofs, descriptions) by e-mail.
Gerald will study your problems and answer you honestly whether some problems are too obvious / well-known or bad for some other reasons. Or if your assessment of difficulty is incorrect. All these flaws are not critical — problemsetting is the complicated art. You will be able to substitute poor problems or change them according to Gerald's advice to reach required difficulty etc. After several "iterations" you will come to agreement. As for me — it usually took 3-4 discussions about 2 hours each.
Well, probably it may happens that you will not come to an agreement. I do not know what is the process in such cases. Probably you will be offered a help of some co-author or some ready problems etc. I do not know.
After the confirmation of your problem set you get to the stage of technical preparations. Each task should be prepared — and here are the steps of this process.
4. Writing problem statements
Problem statement should be maximally clear and should not have any flaws.
Well, that is all. Of course if the statement grows bit too long it is not great — but it would better to have long and crystal clear statement rather than short and vague. Surely if the picture can help for understanding — draw the picture and add it. By the way remember that the length of statement increases the difficulty, so statement of
Div2 should never be extremely long.
Any "features" like belletristic, problem heroes etc — these are encouraged, but not necessarily.
5. Writing an editorial
It is extremely important. Editorial is a half of "educational load" of the contest. But one should not write editorial "as for myself" — even the simplest problem should be explained in very detailed, clear and laconic way. Remember that you know this solution and ones for whom you write an editorial — do not know it. So they could not guess your thoughts.
Since editorial of the problem is usually read by people who did not solve it — it is important to understand they are your target audience. Since so the simpler problem is, the more detailed explanation is needed. My rule is that editorials for all problems should be of roughly equal length.
Once again about pictures. If the picture can help — add it.
Now here are four most deep-hidden things which no contestant will see, but which have great impact on contest preparation.
6. Writing checkers
Programming task supposes that user writes solution and testing system should check it. This process is managed by special programs — we call them checkers — which run the solution on the set of input samples and then checks that the output is correct.
Trivial cases only require to check that the user's answer is the same as author's. This could be done by standard checkers — here are checkers for "yes/no", for a single value, for sequence of values, for strings etc.
In complicated cases (e.g. when multiple arbitrary answers could be correct) checker should judge the correctness of the answer based on input data. Sometimes it could be very complex task — for example for 333C - Lucky Tickets the checker is 10 times harder than the author's solution.
testlib is used for writing checkers. It is simple and handy for creating checkers, validators and generators. If you are not acquainted with it — be sure, Gerald will introduce you :)
I'll add that checkers are usually quite tolerant to extra trailing spaces, line feeds and other insignificant differences.
7. Writing validator
Problem statement tells that input data should be in some specific format. Validator checks the correctness of your input data — that they are exactly such as you described. It is also your task to write validator along with checker.
8. Writing solutions
Yes, you are to write solutions. More than one :)
Of course there should be author's solution — which produces correct answers and suits into time/memory restrictions. It is used for producing author's answers which are used by checkers to compare user's answers with them.
There are many reasons to write another solutions.
At first you need solutions in both
Second — if the solution is complicated, you need to write simple solution which may not be efficient on large tests but will work for small input data. It will help you to prove that your complicated solution is correct.
Third — if your problem allows some "less-efficient" solutions which should fail by memory or time limit — it is important to write them and make sure they really fail (or produce wrong answer etc.)
Fourth — if it the solution assumes some pitfall and you expect to trap some users with it — it is important to write such incorrect version of solution and make sure that it really fails.
Fifth — it is important to write alternative solutions (if they exist). Make sure that your hard problem with cool
O(N*log(N)) solution could not be solved by stupid
O(N^2) approach with bit optimization.
Alternative solutions could affect difficulty of the problem — in both directions. For example if the whimsical trick with
5 lines of code could be substituted with well-known but long algorithm — most of average participants will see it and prefer not to try such problem.
9. Writing test-cases
There are three classes of test-cases.
Tests for problem statement are necessary for better explanation. They are small and structurally simple with purpose to show the idea of the problem. There could be
1-3 of them.
Pretests are to check that participant is not trying to submit some spam and that he/she understand the solution at all. At average there are about
7 of them. They could include border cases, special cases (rarely — maximal case) etc.
Main body of tests check the correctness of the solution. Here it is important to take in account all things. Extreme values of all parameters, tests for maximal time and memory consumption (they could be different). Tests for maximal and minimal answer, for overflow. Tests very different by structure. Tests which will reject all your "wrong" solutions. It may happen that inventing or seeking for such tests become a complicated problem itself.
If the problem allows to propose some unproven hypothesis — write solution based upon it. Then test the correctness of this hypothesis and if it is incorrect — create the test-case which will reject such solution.
It is important to care of writing tasks and tests in such a way that optimized brute-force will not work.
10. Writing an announcement
You are expected to announcement the time of the round, who are authors and what is proposed problem score. Surely it is "altogether fitting and proper" to thank all people who helped you. All other things are optional — your biography, jokes, story about the problem hero, pictures, recommendation to read statements of ALL the problems...
11. Conducting the round
You are to choose the time for round yourself, however you need to care of some limitations — no other important contests at the same time — and of course it should be convenient time for administration.
During the round itself it is required to be on-line and help Gerald watching how the things go, answer to user's questions. Or, perhaps, update problem statement (very, very bad — but it happens sometimes) or update something different (far more bad — never in my experience).
After the contest you are to publish editorial and announce the winners. Surely it would be also good to answer questions in comments to contest announcing post.
I really do hope that my guide will encourage you to create new interesting rounds! :)
All the steps I described are enthralling (except writing validator). If you will succeed in creating problems — write to Gerald at once. However it should be understood that preparing contest requires significant efforts and costs much toil. As for me — after getting the agreement on problems I usually spent about two weeks.
It is not that difficult because it is interesting. But it will devour great lot of your time, yes. Nevertheless you'll get great boost to your karma. The more interesting round — the more boost :)
During the whole process Gerald will help you to get out of troubles (though of course it would be better if you'll get out yourself) and check that you are moving the right way. So be not afraid — you will not be left alone!