"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. "

It would be really cool if we know seed_i before. We will know the maximum rank required to have an increase in our rating.

But the problem is seed_i can only be calculated when we know who all the actual participants beforehand. Which is not possible because many registrants do not actually participate in the live contest.

One solution can be to do the calculations in the live contest and update seed_i for each participant after a fixed interval of time (say 10 minutes and if new participants get added). 😀😃

Would be awesome to have a expected rank on dashboard while we solve problems in the live contest. Can't imagine the adrenaline rush :P

My thoughts parallel those of JohStraat below, though perhaps changing geometric to arithmetic mean is a bit of an overcorrection in terms of punishing bad performances. It seems to me the current rating system is a collection of hacks on Elo, designed to have some desired effect. It works fairly well but has some strange properties: for instance, if the number of contestants changed drastically, the relative meaning of geometric mean would change.

I would rather instead we build a rigorous statistical model. For example, how about we suppose a person's rating r is drawn from a distribution centered at their "true skill" s with variance σ₁². Their performance p in a specific contest is drawn from a distribution centered at s with variance σ₂². Player i beats Player j iff p_i > p_j. Now we should perform a Bayes update, changing each player's rating to the mean of their posterior marginal distribution for s (the prior has s independently drawn for each player from logistic(r, σ₁²)).

Technical issues: the Bayes update may require numerical integration. I believe many of the partial sums can be precomputed and shared, so it should be fast enough. In a basic implementation, σ₁ and σ₂ should be global constants. If we want to get fancier, σ₂ can be a function of certain factors that affect how accurately the contest measures skill; for instance, it makes sense to have σ₂ be inversely proportional to the square root of the contest length. σ₂ might also be higher for contestants who are much too strong or too weak for a given contest's difficulty. σ₁ can be a property of each contestant, subject to Bayes update jointly with r: normally each contest will decrease the uncertainty, so we should also increment σ₁² by a constant amount to account for the fact that people's skills change. Giving unrated coders a very high σ₁ also prevents them from giving or draining too many points from the system for inflation or deflation.

I don't know how feasible it is, but it would be nice to invent a formula that naturally preserves some invariant such as (or maybe something involving the $\sigma_1$s), as normal Elo does...

Ok I wrote up a draft! I plan to write more in the future, but for now just assume σ₁ < σ₂ and they are global constants.

https://github.com/EbTech/EloR

I conjecture that this system will have better properties than previous ranking-based update algorithms such as currently used by CF and TC.

you can understood the whole concept from here..

https://en.wikipedia.org/wiki/Glicko_rating_system

Yes, that isn't even inflation, it is inequality which isn't a problem in contests. The problem is if 400 rating difference doesn't signify a 10 to 1 win-loss ratio. Mike said that Tourist had an expected position of 1.7, but if you look at his history it isn't even close to that:

http://mirror.codeforces.com/contests/with/tourist

Sure he wins often, but he isn't even close to averaging a rank of 1.7 even before the blunder. And that blunder which is statistically impossible given his rating just lost him as much rating as he would get from winning 2 competitions. So he would have an expected rank of 1.7 if he just continued to alternate getting rank 1 twice and rank 168 once which doesn't really add up. Actual elo is made in such a way that it should be all but impossible to reach ratings as high as 3500, such ratings signify that there is a problem with how the rating is calculated.

Difference between 1st and 10th place is much larger than between 41st and 50th.

Rating should be relative to not absolute. If because of some magic spell, all users become two times better than they were, keeping rating without changes is only sane solution. Moreover I guess it is a reasonable assumption that average level of cf member is almost constant function in time.

Last time there was a poll and most of participants didn't care about history preserving

are you referring to this (under ELO system and expected rank): link ?

Let $$$n$$$ be the no of participants in a contest. $$$n$$$ is typically 20k-40k, but the rating range is [-500,4500], let $$$R = 5000$$$,

The current algorithm calculates everyone's rating in $$$O(n*n*logR)$$$

The rating calculation can be done in $$$O(n*R)$$$, for 35-70x speedup.
Update 1: The rating calculation can be done in $$$O(R*R+n*logR)$$$, for 140-550x speedup.

for (Contestant a : contestants) {
    a.seed = 1;
    for (Contestant b : contestants) {
        if (a != b) {
            a.seed += getEloWinProbability(b, a);
        }
    }
}

for (Contestant contestant : contestants) {
    double midRank = Math.sqrt(contestant.rank * contestant.seed);
    contestant.needRating = getRatingToRank(contestants, midRank);
    contestant.delta = (contestant.needRating - contestant.rating) / 2;
}

private int getRatingToRank(List<Contestant> contestants, double rank) {
    int left = 1;
    int right = 8000;

    while (right - left > 1) {
        int mid = (left + right) / 2;

        if (getSeed(contestants, mid) < rank) {
            right = mid;
        } else {
            left = mid;
        }
    }

    return left;
}