Hi!
1) What do you think, what should be a good problemset in CF round?
For example, in ACM-ICPC contest Bill Poucher think that, in addition to having each team solve at least one problem, it’s essential to plan the problemset in to make sure while each problem is solved by at least one team, no team solves all the problems and stays focused until the very end.
2) What should be the pretests? Should the author tries to consider all the cases in the protests? Or should the author specifically to put a few cases for hacks?
for second question:
when you are solving a problem there is some times that you think you solved the problem but after some
minutes you understand your solution was wrong by a example! i think good pretests does n't contain this examples.
1) It should not be based around a certain topic. There should be variety. The whole contest should not be around Mathematics or just Graph Theory. In my opinion, Problem A and B should have solutions that do not require any knowledge of a certain topic. Just Programming skills, and knowledge of STL or equivalent in Java. Obviously, it should not favour a programming language too. Even though, I mainly prefer Java, I would not like seeing a BigInteger problem.
2) Hacks exist, and that's why Pretests should be designed carefully.
Pretests should always TLE problems that use a naive approach. Submitting O(N^2) when the problem needs O(N) or lower should not pass pretests. Otherwise, it's a very easy hack for anyone in his room.
Very non-correct solutions should also get a WA. Submitting obvious wrong greedy when it's a DP problem should be caught by pretests. Otherwise, a very easy hack.
Hack points should be rewarded to those who can come with tricky test cases, or know how to debug a code.
I'd say tricky cases should not be included. ( i.e. what happens if n = 1, or what if the number is a prime,etc), or missing a certain case in an implementation problem.
That's what hacking should be rewarded for IMO.
I think that only C++ and Java should be supported in div1 in Codeforces. It would be too hard for organizers to always guarantee that it's possible to solve a problem in Python — the intended solution in Python is sometimes as slow as brute force in C++.
I think that n = 1 should be included, unless organizers think that many will try to hack in this problem (short implementation; weak pretests and thus hacks in the leaderboard).
I like this kind of blogs because some of them are very useful.
There are a lot of problems in an acm-style contest (5 hours, 3-person teams). It allows for huge diversity of difficulty and topics. It's possible to challenge the best teams with 3-4 hard problems and still have something for those who know almost no algorithms.
CF rounds are something different though. Fewer problems, less time. I have no doubts that every problem should be solved, otherwise it means it's too hard for 2 hours (and some time needed for at least 2-3 other problems). If the best participant solves 4 of 5 problems then an average participant won't likely even read D and E — because of differences in skills/experience. I think that it's fine to allow 5-10 people to solve everything and it's fine that the winner solved everything in 1:30 (30 minutes before the end). Then, weaker participants also may have fun (and it's not fun to be able to solve only 1 problem). Sometimes, the fastest guys can gain more points by hacking. Also, it's possible to stress test your solutions. I think it's more important to give them at least 1-2 interesting problems. They shouldn't mind ending with ABCDE if they have spent 30 minutes of thinking in D or E.
That being said, I still think that it's awesome if organizers manage to prepare a contest where D and E will be each solved by many but nobody will solve everything. But it's awesome only if other participants are still pleased with easier problems. Because of only 2 hours, it's hard for organizers to achieve exactly what they want (seriously, think about it).
I think that A should be solvable for everybody (at least everybody being in this particular division).
Problems A and B may have weak pretests because codes are usually short and thus easy to read and hack. I agree with FatalEagle's comment that "the pretests for problems which greatly affect standings [...] should be nearly identical to final tests". Of course, there are exceptions. In some problems participants may try to squeeze their randomized/heuristic/slow approach to pass tests. Pretests' goal is to catch bugs in hard problems, not to allow people to test and squeeze their wrong approach.
Organizers should also keep in mind the danger of someone with a fake account. He can submit a shitty solution only to lock it and see others' submissions. Then, he will submit a correct solution with his main account. It means that some pretests other than samples must exist and most of the time it shouldn't be extremely easy to past pretests.
In each problem pretests should contain one max-test. It should catch a bug of leaving an uncommented brute force in your code or some other stupid bug causing worse complexity. It should also give some info that your solution likely has a good enough constant factor. And finally, it won't allow to submit brute force and do something I described in the previous paragraph.
In some easy problems organizers must decide which mistakes they want to catch in pretests. I find it a bit strange because it affects contestants a lot later. Some will make a mistake organizers have chosen to catch, some will make a mistake organizes decided to leave (the solution will pass pretests). It isn't nice but I think we shouldn't care much about it because in the long run everybody has the same situation. Once you will suffer because of weak pretests, the other time they will catch your mistake. So, there are no conclusions from this paragraph, other than "organizers shouldn't care much about this issue".
I think that each problem should contain some description about pretests. Maybe the number of pretests, maybe their strength described with one word (weak/medium/etc.). I guess that most of you won't agree with me so I don't think this idea will be ever used. The logic behind my idea is the following. First, in CF rounds the problem difficulty is revealed (you know the number of points) so it isn't that absurd to also say something about the strength of pretests. Also, it would make a contest less random because: (1) It would tell you if you must test your solution a lot. (2) It would tell you if it makes sense to hack other people. I understand that organizers may be wrong with their judgment about the strength of pretests, but the situation is similar with the difficulty of problems, revealed as the number of points. Thus, I don't think it's a big drawback.
I think that in shared problems (CDE for div2, ABC for div1) organizers should care more about div1 and adjusting the strength of pretests for them. For div2 the goal should be to get into div1. You aren't able to do it if and only if you get low places in div2. In all sports it's important to correctly sort best participants and it's secondary to care if someone gets 150-th or 200-th place. Don't get me wrong — learning is important and div2 is important. At the same time, adjusting everything for top guys should be a bit bigger priority. Let me give you an example. Let's say that div1C is quite easy to come up with and also the implementation is short. But, the its main difficulty are corner cases. You may not like this kind of problems but sometimes they do appear (I think it's fine btw.). In div1 a lot of people will submit this problem and organizers should IMO consider making pretests weak to allow hacks. At the same time this is div2E and maybe in some rooms there won't be even 2 submissions. Thus, there won't be a lot of hacking. For div2, it would be better to make strong pretests. And my point is this kind of situation should be decided in favor of div1. If you are in div2 and solve not-easy problems then you will eventually advance to div1 anyway.