Codeforces: Rating Is Fixed (bug, go away!)

Правка en1, от MikeMirzayanov, 2016-04-06 20:34:58

Hello!

Last weeks I was concerned (and probably, you too) about abnormal rating growth of our leaders. Of course, first of all I'm talking about tourist, his rating is just rushed into the sky.

Последние недели как и вы я был обеспокоен аномальным ростом рейтинга у наших лидеров. Конечно, в первую очередь речь идет о

There were even comments from a series of "I told, and it happened"

After the first round of VK Cup 2016, I carefully investigated the reasons of such growth and found a simple and trivial bug in the rating formulas. It's funny that even after being published, nobody found it. Look at this function:

    private double getSeed(List<Contestant> contestants, Contestant contestant, int rating) {
        Contestant extraContestant = new Contestant(null, 0, 0, rating);
        double result = 1;
        for (Contestant other : contestants) {
            result += getEloWinProbability(other, extraContestant);
        }
        return result;
    }

Remind, this feature is to calculate the expected participant place, if its rating suddenly became equal to rating. Of course, it should not take account of the participant itself (to whom we currently assign new hypothetical rating). The correct code must be:

        for (Contestant other : contestants) {
            if (other != contestant) {
                result += getEloWinProbability(other, extraContestant);
            }
        }

This bug led to the fact that taking the first place tourist actually won a very serious opponent. Himself. This led to a significant increase in its rating, even if the first was quite expected.

The good news is that this bug has a statistically significant effect only in the very rare cases when the winner (or close to the winner) had a very high rating (yes, contrary to "anti-heroes" is also true). If we take an arbitrary round and recalculate the rating formulas corrected, almost all participants will receive exactly (or very close) rating.

After consulting with tourist and Petr, I came to the following plan of action:

  • Today we had chronologically recalculated all ratings from the revolution of 2015,
  • If difference between the change according to the corrected rating formulas and the historical change (according to formulas with a bug) is no more than 3, the historic change continued to be used,
  • If difference between the change according to the corrected rating formulas and the historical change (according to formulas with a bug) is more than 3, the change is replaced with the correct rating in history.

It turned out that this bug did not affect practically all users. Bug touched only the top. I apologize to those who had descended from heaven to earth — but it was impossible to leave it as is. I wish leaders to get those ratings that were before rating fix.

Mike.

Теги codeforces, ratings, fix, bug

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский MikeMirzayanov 2016-04-06 20:35:28 126
en1 Английский MikeMirzayanov 2016-04-06 20:34:58 3207 Initial revision for English translation
ru1 Русский MikeMirzayanov 2016-04-06 20:10:43 3217 Первая редакция (опубликовано)