Hey guys it's your favorite purple not anymore CF shitposter here. We're back to hopefully non-controversial useless information lol

I think anecdotally we all have this gut feeling that it's harder to get a X perf in a div 2 than a div 3, and in turn harder to get X perf in a div 1 than a div 2. Is this urban legend or a real phenomenon?

Methodology

I took several of the most recent separated div 1 and div 2 rounds where the div 1 round has the same problems shifted by 2 positions.

For each contestant in the div 2 round, we'll:

• Calculate and record their div 2 perf
• Convert to estimated div 1 score by dropping problem A/B, adjusting timestamps on the rest of the problems, and recalculating the score based on the problem values for div 1. (We will discard anyone who solves C/D/E/F before A/B)
• Calculate and record their div 1 perf from the new score we calculate.

Calculating performance (CP lesson time!)

Using FFT, our favorite :yayy:

Let's formally define performance as, position $$$p$$$ having performance $$$x$$$ means that if your rating was $$$x$$$, then the expected value of your placing is $$$p$$$.

If we make places 0-based (winning would be 0th place), we can use linearity of expectation:

where $$$E[\text{tourist}]$$$ is the chance of you losing to tourist, which is given by

where $$$y$$$ is the rating of the other participant and $$$x$$$ is the performance.

This is how Codeforces (and we) will calculate the performance.

Now the fun part is that we can speed this up using FFT. Instead of having an quadratic-type algorithm where you have to spend $$$O(n)$$$ time summing up all those expectations for every performance you want to calculate, let's convolve them.

Define a one-hot encoding array $$$a$$$ such that $$$a_i$$$ is the number of people in the field with rating $$$i$$$. For example, if there are 2 people with rating 3 and 1 person with rating 4, we might have $$$a = [0, 0, 2, 1, 0]$$$.

Then, the place of a performance $$$x$$$, which I will call $$$f(x)$$$, is:

Do you see the convolution/cross-correlation yet? We essentially want to convolve an array $$$b$$$ that contains all the lose-chances in a sliding window along the array $$$a$$$. That would calculate all the performances of all the ratings in a range $$$[l, r]$$$ in time $$$(r-l) \log (r-l)$$$.

Here's an illustration to try to show this more concretely. Let's assume that in this fictional rating system, you trade games when your rating is equal, have a 70% chance to win if your rating is 1 point higher, and are guaranteed to win if your rating is 2 or more points higher. In other words, $$$b$$$ would look like $$$[..., 0, 0, 0.3, 0.5, 0.7, 1, 1, ...]$$$

Then suppose our one-hot is $$$a = [1, 0, 0, 1, 2]$$$: 1 person with rating 1, 1 person with rating 4, 2 people with rating 5. We would calculate:

rating       1    2    3    4    5
    a        1    0    0    1    2
       0.3  0.5  0.7   1    1    1    1     # suppose our rating is 1

# Expected placing: 1*0.5 + 0*0.7 + 0*1 + 1*1 + 2*1 = 3.5
# So placing 3.5 would be a performance of 1 rating.

rating       1    2    3    4    5
    a        1    0    0    1    2
            0.3  0.5  0.7   1    1    1     # suppose our rating is 2 now

# Expected placing: 1*0.3 + 0*0.5 + 0*0.7 + 1*1 + 2*1 = 3.3
# So placing 3.3 would be a performance of 2 rating.

# And so on, moving the window

Once we have that, we take the time spent to solve div 2 C/D/E/... and map that to div 1 A/B/C. This allows us to calculate the score and performance in the div 1 round.

Results

I analyzed all 15 div 1/2 separated rounds over roughly the last year. The results are... weird.

This is the graph of div 2 vs div 1 performance over them all.

For the most recent round 1105, for most people in the 1800 to 2300 range, div 1 was roughly 50 to 120 rating points harder.

However, over all rounds, div 1 was approximately 400 points harder than div 2. There was a lot of variance between rounds; some had div 1s up to 600 points harder, and others had div 1s that were actually a few points easier. This doesn't really make a lot of sense; intuitively we all know that can't be true.

Some explanations for the somewhat crazy results could include:

• You do lose the time you spent on div 2 A/B into a black hole forever. Even if we adjust the penalty, you may lose the ability to solve an additional problem if you just needed another like 5 or 10 minutes of time.
• You are "fresher" in div 1, since you don't have to spend any mental energy on div 2 A/B.
• There could be some bias in the data. Maybe a lot of people who "place well but not too well" in div 2 were boosted by really fast/accurate solves on div 2 A/B that go away when we remove them in div 1. For example for most people in the 1600-2000 perf range their div 1 data is really only the time it took them to solve problem C after B, or to solve problems C and D. It is also possible that div 1 rewards solves on harder problems more than speed on early problems.
• "Unregister scumming." Basically you read problem A (maybe also B) and try to solve it in your head, if you don't get the idea fast enough then you just give up and unregister. You don't become committed to the round until you send your first submission. Unregister scumming is much more effective in div 1 because the first problem is already decently hard — I could unregister scum in div 1 fairly effectively, in the contests where I get a fast solve on A I'd be at a sizable advantage, or I could quit if the problem looks like implementation hell, WA hell, or something like that. On the other hand, if I tried to unregister scum in div 2 it would be way harder since problem A will always be a fast solve to me anyway.
• Maybe my method is just bugged?
• Or div 1 could really be deflated by that much in comparison to div 2.

If you were hoping for a number with a nice-looking confidence interval attached, sorry! Unfortunately this data is not nice to work with. You can find the rest of the high-res graphs for each contest at https://github.com/greatericontop/Codeforces-Div1vsDiv2/tree/main/assets/per_contest. You can also get the source code there and run some tests yourself and/or potentially find a bug in my approach that might be causing the results lol

Why do ratings desync?

Ratings can only compare skill across a population if the entire population interacts. Otherwise, such as in the case of div 1 and div 2, you may end up with "div 1 flavored rating" and "div 2 flavored rating" that cannot be compared to each other.

The solution is to make sure the populations mix as much as possible. I think CF does a pretty decent job at this. We have combined 1+2 rounds every so often that mix everyone together, and div 3/4 participants can also participate in div 2 which does some mixing there.

A quick note on problem ratings

You may also have a gut feeling that a 2100-rated div 3/4 problem is easier than a 2100-rated div 1/2 problem.

I think this is true given what we know about div 1 vs div 2 flavored ratings. What also could be a factor is positioning — a div 3 F may be the same difficulty as a div 2 D, but div 3 contestants had less time during the contest to solve it on average. That can artificially drive up the rating of the div 3 problem.