↵
Основная концепция используемых формул — мы расширяем принципы рейтинга Эло для встреч более чем двух участников.↵
↵
Каждый участник характеризуется величиной рейтинга $r_i$ — целое число (возможно отрицательное). Грубо говоря, чем это значение выше, тем лучше участник выступает в соревнованиях. Рейтинг это подсчитывается/пересчитывается таким образом, чтобы выполнялось равенство:↵
↵
$$P_{i,j}=\frac{1}{1+10^{\frac{r_j-r_i}{400}}},$$↵
↵
где $P_{i,j}$ вероятность того, что $i$-й участник победит на соревновании $j$-го. Таким образом вероятность победы одного участника над другим определяется только разностью их рейтингов. Например, если разница рейтингов двух участников равна 200, то побеждает сильнейший с вероятностью примерно 0.75. При разнице рейтинга 400 вероятность возрастает до 0.9.↵
↵
После очередного соревнования величины $r_i$ меняются так, чтобы в большей степени соответствовать основной формуле рейтинга. В данном случае “вероятность” какое-то расплывчатое понятие, последние соревнования вносят больший вклад в ожидаемый результат.↵
↵
Рассмотрим момент до начала раунда и посчитаем для каждого участника его ожидаемое место (его называют $seed_i$). Ожидаемое место равно сумме вероятностей по всем другим участникам обойти данного плюс один (плюс один берется из-за 1-индексации): ↵
↵
$$seed_i=\sum\limits_{\substack{j = 1 \\ j \ne i}}^nP_{j,i}.$$↵
↵
Например, перед [contest:573] при рейтинге 3503 ожидаемое место у [user:tourist,2015-10-06] было примерно 1.7, а у [user:Petr,2015-10-06] при рейтинге 3029 ожидаемое место было примерно 10.7.↵
↵
Общая идея пересчета рейтинга такова: если участник занимает место ниже своего ожидаемого, то его рейтинг следует уменьшить, а если участник занимает место выше своего ожидаемого, то его рейтинг следует увеличить.↵
↵
Посчитаем для участника среднее геометрическое его текущего места и ожидаемого, пусть эта величина равна $m_i$. В самом деле, это какое-то среднее значение между ними, оптимистично сдвинутое в сторону меньшего из мест. Найдем (с помощью бинарного поиска) такой рейтинг $R$, которым должен бы был иметь этот участник, чтобы всё-таки ожидаемо занимать место $m_i$ (среди того же набора участников). Текущий рейтинг участника должен быть изменен так, чтобы стремиться к $R$. Поэтому, изменение рейтинга участника в раунде вычисляется как $d_i=(R-r_i)/2$.↵
↵
Это почти всё, кроме фазы борьбы с инфляцией. Заметим, что при инфляции богатые становятся еще богаче, поэтому будем бороться именно с этим. Если предположить, что рейтинг был уже посчитан справедливо (то есть каждый участник имеет свой статистически обоснованный рейтинг), то математическое ожидание изменения рейтинга по любому участнику должно быть равно 0. Выберем группу наиболее высокорейтинговых участников раунда (по рейтингу $r_i$ — до начала раунда) и скажем, что сумма их рейтингов должна остаться неизменной. В качестве размера такой группы выбирается эвристическая величина $s=\min(n, 4\sqrt{n})$. Если $d_i$ таковы, что их сумма для этой группы не равна 0, то ко всем им (по всем $n$ участникам) прибавляется некоторое значение (вычитается) так, чтобы их сумма по $s$ наиболее высокорейтинговым участникам стала равна 0.↵
↵
<i>После раунда 327 ограничили этот эффект: сначала к каждому изменению прибавляется величина $inc = -sum(d_i) / n - 1$ (то есть $d_i$ меняются), затем прибавляется $inc = min(max(-sum(d_i) / s, -10), 0)$. Таким образом, эффект изменения рейтингов из абзаца выше ограничен падением каждого рейтинга не более чем на 10.</i>↵
↵
Кстати, для любого логически непротиворечивого рейтинга должны выполняться несколько инвариантов:↵
↵
* если участник $A$ имел рейтинг хуже участника $B$ и выступил хуже него на текущем раунде, то и его рейтинг после пересчета должен быть не лучше чем у $B$;↵
* если $A$ выступил лучше $B$, но имел до раунда хуже рейтинг, то ему должны прибавить не меньше единиц рейтинга чем участнику $B$.↵
↵
В частности, для обновленного рейтинга Codeforces эти инварианты проверяются на выполнение при любом пересчете рейтинга.↵
↵
Ознакомиться с используемым кодом можно по ссылке: [submission:13861109].
↵
The basic idea of Codeforces rating system is to generalize Elo rating to support games with multiple participants.↵
↵
Each community member is characterized by value $r_i$ — integer number. Roughly speaking, the higher value means better results in the contests. Rating is calculated/recalculated so that the equality strives to be correct:↵
↵
$$P_{i,j}=\frac{1}{1+10^{\frac{r_j-r_i}{400}}},$$↵
↵
where $P_{i,j}$ is probability that the $i$-th participant has better result than the $j$-th participant. ↵
Therefore for two participants the probability to win/lose depends on subtraction of their ratings.↵
For example, if the difference of ratings is equal to 200 then stronger participant will win with probability ~0.75. If the difference of ratings is equal to 400 then stronger participant will win with probability ~0.9. ↵
↵
After a contest the values $r_i$ change in a way to satisfy main formula better.↵
↵
Let’s calculate expected place $seed_i$ for each participant before contest. It equals to the sum over all other participants of probabilities to win (to have better place than) the $i$-th plus one because of 1-based place indices:↵
↵
$$seed_i=\sum\limits_{\substack{j = 1 \\ j \ne i}}^nP_{j,i}.$$↵
↵
For example, before [contest:573] [user:tourist,2015-10-26] had rating 3503 and his seed was ~1.7, and [user:Petr,2015-10-26] had rating 3029 and expected place ~10.7.↵
↵
General idea is to increase $r_i$ if actual place is better than $seed_i$ and to decrease $r_i$ if actual place is worse than $seed_i$.↵
↵
Having $seed_i$ and actual place, let’s calculate their geometric mean $m_i$. You can think about it as an something average between $seed_i$ and actual place shifted to the better place. Using binary search find such rating value $R$ which the $i$-th participant should have to have a $seed_i=m_i$. Obviously the rating $r_i$ should be modified to become closer to $R$. We use $d_i=(R-r_i)/2$ as rating change for the $i$-th participant.↵
↵
↵
↵
↵
It's almost all except the phase of fighting against inflation. Inflation works as follows: the rich get richer. We will try to avoid it. If we assume that the rating was already calculated fair (i.e. everybody has perfect statistically based rating) then expected change of rating after a contest is equal to zero for any participant. ↵
↵
Choose a group of the most rated (before the round) participants and decide that their total rating shouldn’t change. We use heuristic value $s=\min(n, 4\sqrt{n})$ as a size of such group. Let’s find the sum of $d_i$ over participants from group and adjust all values $d_i$ (for all participants) to make the sum to be zero. In other words, $r_i = r_i + inc$, where $inc = - sum_s / s$, $sum_s$ is sum of $d_i$ over $s$ participants from chosen group.↵
↵
<i>After the round 327 we restricted the effect in following way. Firstly, we do $r_i = r_i + inc$, where $inc = -sum(d_i) / n - 1$, $sum(d_i)$ is sum of all $d_i$. It makes the sum of all $d_i$ to be near zero and non-positive in the same time. Secondly, we apply idea from the previous paragraph, but $inc = min(max(-sum_s / s, -10), 0)$. Thus, the effect of modification can not reduce rating for more than ~10 points.</i>↵
↵
By the way, for any consistent rating the following assertions should be true:↵
↵
* if the participant $A$ had worse rating than the participant $B$ before the contest and finished the contest on the worse place then after recalculations the the rating of $A$ can’t be greater than the rating of $B$↵
* if $A$ finished the contest better than $B$ but $A$ had worse rating before the contest then $A$ should have equal or greater rating change than $B$.↵
↵
In particular, formulas are tested to satisfy the both items on each ratings recalculation.↵
↵
You may read the actual Codeforces code to recalculate ratings here: [submission:13861109].↵
↵
↵
