Hello everyone.
The idea of dynamic problem scores is not new. As far as I can remember, something that was discussed back in 2000. Since then, the issue has surfaced several times — one of the latest experiments have been organized by Alex_KPR.
Why do we need different problem scores? As correctly observed RAD, they are actually needed for contests where the solution has a chance to fail after coding phase. For example, Bob solved easy A, and Peter solved easy A and really hard B. But Peter's A failed system tests and he solved B later (and may not from the first attempt). In this case, if the problems were equal in value, Peter will take place below Bob, that somehow unfair.
Typically Codeforces problems has divible by 500 values: 500, 1000, 1500, etc. Usually we try to pick up a 5-problems sets, varying in complexity. In this case, each contestant will find interesting problems (for him/her). The traditional set of tasks includes problems 500-1000-1500-2000-2500.
In practice, it's not that simple. Sometimes it turns out that the authors and testers did not guess the complexity of the problem in terms of regular contestants. What to do?
The experiment is as follows. Assign the value of the task dynamically depending on the number who have solved this problem. During the main contest time here will be taken into account the submissions with verdict "Pretests passed", but after system test — "Accepted". Of course, solutions of out-of-competition participants will not be counted.
The idea is as follows:
- If a problem solved by half to all the contestants, then it is worth 500 points,
- If a problem solved by quater to half of all the contestants, then it is worth 1000 points,
- And so on.
More formally, in the following table:
Solvers fraction | Max. problem points |
(1/2, 1] | 500 |
(1/4, 1/2] | 1000 |
(1/8, 1/4] | 1500 |
(1/16, 1/8] | 2000 |
(1/32, 1/16] | 2500 |
[0, 1/32] | 3000 (maximum problem score) |
Number of round participants = who made at least one attempt in this round.
That's it! As you can see the idea is very simple and not overloaded with formulas and details. You may view results of past Codeforces contests by links like "Final standings". We temporary recalculated results according experimental rules. Later we will return them back.
Today 2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) will use such experimental rules. We guarantee that the problem A will be easiest problem (as Jury thinks), but the order of the remaining problems — random. Good luck!
Smoother dynamic problem scores (250 pts steps)
Smoother realization of dynamic problem scores with a step of 250 points has been implemented. As before, if the amount of contestants who solved a problem is increased twice, max. problem score is decreased by 500 points. Now also if the amount of successful contestants is increased times, score is decreased by 250 points. The table below illustrates max. problem score dependency from the percentage of contestants who solved the problem.
Solvers fraction | Max. problem points |
(0.707, 1] | 250 |
(0.500, 0.707] | 500 |
(0.353, 0.500] | 750 |
(0.250, 0.353] | 1000 |
(0.176, 0.250] | 1250 |
(0.125, 0.176] | 1500 |
(0.088, 0.125] | 1750 |
(0.062, 0.088] | 2000 |
(0.044, 0.062] | 2250 |
(0.031, 0.044] | 2500 |
(0.022, 0.031] | 2750 |
[0, 0.022] | 3000 |