Codeforces: исправление рейтинга (баг, уходи!)

Revision ru1, by MikeMirzayanov, 2016-04-06 20:10:43

Привет!

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

Были даже комментарии из серии "я же говорил, что так и будет"

После первого раунда VK Cup 2016 я внимательно изучил причины подобного роста и обнаружил простой и банальный баг в формулах подсчета рейтинга. Забавно, что даже будучи опубликованным этот код не вызвал скепсиса. Посмотрите в эту функцию:

    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;
    }

Напомню, что эта функция вычисляла ожидаемое место участника, если бы его рейтинг был равен rating. Конечно, она не должна учитывать самого участника, кому мы в данный момент присвоили гипотетической значение рейтинга. Правильный код должен содержать проверку:

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

Этот баг приводил к тому, что занимая первое место tourist фактически побеждал одного очень серьезного противника. Себя самого. Это приводило к значительному росту его рейтинга, даже если первое место было довольно ожидаемым.

Хорошая новость состоит в том, что этот баг оказывал статистически значимый эффект лишь в очень редких случаях: когда победитель (или близкий к победителю участник) и так имел очень большой рейтинг (да-да, обратное для "антигероев" тоже верно). Если взять произвольный раунд и пересчитать рейтинг по исправленным формулам, то практически все участники получат в точности (или очень близкое) изменение рейтинга.

Посоветовавшись с tourist и Petr, я пришел с следующему плану действий:

  • сегодня были хронологически пересчитаны все рейтинги от революции 2015-го года,
  • если в изменение рейтинга по исправленным формулам отличалось от исторического изменения (по формулам с багом) не более чем на 3, то продолжало использоваться историческое изменение,
  • если в изменение рейтинга по исправленным формулам отличалось от исторического изменения (по формулам с багом) более чем на 3, то в истории рейтингов изменение подменялось на правильное.

Оказалось, что практически на всех пользователей этот баг никак не повлиял. Баг задел только самый топ — и чем выше участник к топу, тем сильней оказалось влияние.

Я приношу извинения тем, кого пришлось опустить с небес на землю — но оставлять как есть, конечно, было нельзя. Топам же я желаю поднажать и вернуть те рейтинги, что были у вас до исправления формул.

М.

Tags codeforces, рейтинг, баг

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MikeMirzayanov 2016-04-06 20:35:28 126
en1 English MikeMirzayanov 2016-04-06 20:34:58 3207 Initial revision for English translation
ru1 Russian MikeMirzayanov 2016-04-06 20:10:43 3217 Первая редакция (опубликовано)