This is a tutorial to how Codeforces scoring system works and some basic strategies about it. I will only explain about rated rounds here, but note that there are other types of scoring in unrated contests.
Please do share this blog when you see questions about it.
Scoring types
There are two different types of scoring system:
- Standard (Div. 1 / Div. 2, Div. 1 + Div. 2)
- Extended ICPC (Educational, Div. 3, Div. 4)
The standard (this is not a formal name, but I don't know if one exists) scoring is Codeforces' own scoring system where each participant's rank is determined solely by their final score. On the other hand, extended ICPC literally uses the ICPC rule for calculating ranks, using number of solved problems & penalty, with slight modifications.
Standard
Contests using this scoring system have pre-determined initial scores on each problem. By initial it means you get that score when you solve it in the $$$0$$$-th minute (before exactly 1 minute passes). Each problem's score, however, will decrease every minute.
Basic formula
Let's start with the formula. In a contest with duration of $$$d$$$ minutes, the score you get by solving a problem with initial score $$$x$$$ at $$$t$$$-th minute with $$$w$$$ incorrect submissions is:
There are some things that needs detailed explanation here:
- Each $$$x$$$ is always notified in the announcement blog, at least a few hours before the contest starts. If you see 'Scoring distribution: $$$500$$$ — $$$1000$$$ — ...' in the announcement, it means that problem A will have score of $$$500$$$, problem B will have score of $$$1000$$$ and so on.
- The amount of decrement per minute is determined both by the problem's initial score and contest duration. Typically, if $$$d=120$$$, it means a $$$500$$$-scored problem loses $$$2$$$ points, $$$4$$$ points for $$$1000$$$-scored problem, $$$7$$$ points for $$$1750$$$-scored problem, etc. If $$$d=180$$$, then a $$$500$$$-scored problem loses $$$1$$$ point after the first minute, but it loses $$$2$$$ points after the second minute (so in total $$$3$$$ points).
- $$$t$$$ only treats the submission time in integer minutes. For example, 00:02:59 is the same as 00:02:00, both being $$$t=2$$$.
- $$$w$$$ is the number of incorrect submissions before your first accepted submission. All submissions after the first 'Accepted' submission do not count[1]. It also does NOT include submissions that got incorrect on (pre)test $$$1$$$ [2] as well as compilation error. 'Hacked' or 'Skipped' also count as incorrect submissions. Therefore, unless you found an obvious mistake in your 'Pretests passed' submission, you're discouraged to resubmit as getting another 'Pretests passed' will make the previous one as 'Skipped' (and therefore $$$w$$$ is increased), as well as increasing $$$t$$$. I'll explain more about pretests in the next section.
- No matter how late you were, or how many wrong submissions you made, the score never goes below $$$0.3 \cdot x$$$ as long as you have at least one 'Accepted' verdict on it.
- $$$d$$$ is fixed when the contest starts; i.e. it does not change if the round is extended during the contest.
Pretests and system test
During these rounds, your submission will be judged only on a subset of tests, called pretests. If you pass all pretests, you get 'Pretests passed' verdict. This does NOT guarantee that your submission is correct[3], but preliminarily it will be shown as you got points from that problem. After the round, all 'Pretests passed' submissions will be rejudged with the full test, and this phase is called system test. If your submission also passes all tests in system testing, it will get 'Accepted' verdict and the score you got becomes final.
Hacks
You're assigned to a room with a few dozens of participants when the contest starts. During the contest, you can lock problems on which you got 'Pretests passed', and try hacking other participants' solutions in your room. Hacking is about making an input for another submission where it would likely to get any incorrect verdict (wrong answer, time limit exceeded, etc.). Locking means you cannot resubmit on that problem again. For each successful hacking attempt, you get $$$100$$$ points. For each unsuccessful hacking attempt, you lose $$$50$$$ points. This score is independent from the basic formula and there is no limit of score you can get or lose from hacks.
After the contest, Candidate Masters and above can try uphacking, but this does NOT affect anything regarding the scores and the verdict will remain as 'Accepted' (along with the hacked mark)[4].
Subtasks
Sometimes some problems will have subtasks, typically named like 'C1', 'C2'. They can either be problems with one of them being strictly eaiser than the others, or be a little different problems with many similarities. However, being subtasks doesn't affect anything in the scoring[5] and they work just same as two different problems. These problems' score, however, is usually stated with parenthesis like $$$(1250 - 1000)$$$ in the announcement, so you can assume that this problem is actually two subtasks with $$$1250$$$ and $$$1000$$$ scores each.
Strategies
Let's say you need $$$t$$$ minutes to solve only that problem with score of $$$x$$$. Then with the most simplfieid version of the formula[6], the optimal strategy is to solve problems is to go in order of $$$\cfrac{x}{t}$$$ in decreasing order. For example, if you need $$$10$$$ minutes to solve a $$$500$$$-point problem and $$$30$$$ minutes to solve a $$$1000$$$-point problem, solving the $$$500$$$-point one is better. If you can solve the $$$1000$$$-point problem in $$$15$$$ minutes, then solving it first is better. Though, it's usually the case that a double scored problem takes far more than double time to solve, so the most recommended order to solve problems is to start with the easiest problem and so on[7].
However, you may also want to keep a few more things in mind:
- If you're left with too little time to solve $$$n$$$ problems but you think you can solve $$$n-1$$$ problems, then you can try to go for the harder ones.
- If you don't make a single submission during the round then you're unrated, so another viable strategy is to read harder problems and see if you can solve them first. If lucky, you may get a huge headstart by solving a hard problem very early.
- For subtasks, sometimes the easier subtask is significantly easier than the harder one, and after solving the easier one the harder one may not be too advantageous anymore. In this case you can skip the harder one for now and come back to it later, after solving other more rewarding problems first.
Extended ICPC
ICPC rules are simpler. There are two factors that determine one's rank:
- Number of solved problems (the more, the better)
- Penalty (the less, the better)
The number of solved problem is always the higher priority. For example, solving $$$4$$$ problems with $$$1000$$$ penalty is better than solving $$$3$$$ problems with $$$10$$$ penalty. There are no predetermined scores in ICPC rules, and all problems have equal effect on the rank.
The penalty can be calculated as the sum of the following formula for each solved problem. Unsolved problem has NO penalty no matter how many attempts you made on that problem. Let's say the time in minutes for the first 'Accepted' submission is $$$t$$$ and the number of incorrect submissions before the first accepted submission is $$$w$$$. Then the formula for the penalty is simply $$$t + 10w$$$. Note that every submission after the first 'Accepted' submission does NOT count. You may notice that the incorrect submission penalty is $$$10$$$ instead of $$$20$$$ in actual ICPC contests, and it's because of shorter contest time and less problems in Codeforces rounds, compared to real ICPC contests.
The best strategy in these rounds is to simply solve from the easiest to the hardest. There are no alternatives. However, you may want to note that getting hacked or failing system test on easier problems is far more fatal compared to failing harder problems, because of how penalty is calculated.
Another thing to note that in these rounds you can make multiple 'Accepted' submissions, and the previous ones do not get skipped. Therefore, if you have the slightest doubt in your previous submission, you can resubmit as much as you want.
Open hack
Unlike standard rounds, extended ICPC rounds do not have rooms and hacks during contest. Instead, they have an additional 12-hour phase after the contest called open hacking. In this phase, anyone (including non-participants) can try to hack any 'Accepted' submission any number of times, without any additional points or penalty. When the hacking attempt is successful, the hacked submission gets 'Hacked' verdict and then the participant's rank is recalculated accordingly. It could either the problem becomes unsolved with no other 'Accepted' submission, or that submission becomes an incorrect submission penalty if the participant has a later 'Accepted' submission, or it changes nothing if they have an earlier 'Accepted' submission.
After this phase, all successful hack tests are added to the main tests and all 'Accepted' submissions will be rejuged, and only the ones that passed all these tests will remain as 'Accepted'.
Notes
[1] Normally there will be only one accepted submission, but you can make multiple of them (I don't think this was intended to happen) if you submit another code before you get 'Pretests passed' on the previous submission.
[2] Even if you got incorrect on examples, if it's not the very first one (i.e. pretest 2+), you get incorrect submission penalty.
[3] However, recent trend is to have strong pretests, you in most cases it will also pass system test. There are always exceptions, though.
[4] Submissions made after contest (including virtual participation) are affected, as well as getting 'Hacked' verdict.
[5] Usually hacks are allowed only when you solve both subtasks, but that's another thing.
[6] ... that does not consider incorrect submission penalty and lower limit of the score, etc.
[7] This is just current trend, and the scoring may change to be more exponential later, then the strategy can also change.
If I cant even solve problem A WHAT Should I do ?
solve problem B
I used to think that problem score decrement is a function of time lapsed and number of ACs.
Cool to know it only depends on time lapsed.
Very helpful, thank you
Now make one about the rating system, meow.