MikeMirzayanov's blog

Codeforces: Rating Is Fixed (bug, go away!)
By MikeMirzayanov, history, 9 years ago, translation, In English

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.

  • Vote: I like it
  • +878
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +112 Vote: I do not like it

Haha, some time ago I thought about exactly such a hypothetical reason of why tourist rating is skyrocketing — "maybe tourist is gaining so much, because he is winning against tourist?". However my estimation of that being true times my laziness led me not to investigate it in more details :<.

Btw that "Yay :)" from my depicted comment above was my reaction to not allowing two person teams in online mirror of VK Cup :P.

→ Reply
»
9 years ago, # |
  Vote: I like it +20 Vote: I do not like it

This can also be easily fixed by initializing result = 0.5

TopCoder rating formulas

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I wonder something was wrong ...
Now tourist challenges is more interesting.

→ Reply
»
9 years ago, # |
  Vote: I like it +182 Vote: I do not like it

So tourist was Chuck Norris of programming, who can beat himself.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    In fact, every user defeated himself in every contest :P

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      As well as lost to himself in every contest.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        Actually no :). Expected position was by 0.5 larger than it should be which corresponds to adding our virtual ghost and winning with it and fact that our ghost lost with us doesn't count for the real competitor as losing :).

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      So we all had a moment of Chuck Norris.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Interesting. How? If my contest standing is 3000, but I am expected to be near 1000, then I did not defeat myself, or did I? Wait, do I even understand any of this...

      → Reply
»
9 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Just wondering, why is it 3, not 2 or 4?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    And the LORD spake, saying, "First shalt thou take out the difference, then shalt thou compare the difference to three, no more, no less. Three shall be the number thou shalt use to compare, and the number for comparison shall be three. Four shalt thou not use, neither use thou two, excepting that thou then proceed to three. Five is right out"

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +25 Vote: I do not like it

It seems it effected my contribution, today I woke up and it was decreased by 2 =)) (just kidding)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    affected*

    ^That's how you decrease your contribution points

    → Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The rating value that appeared for some time yesterday (mentioned here) was the rating calculated by the corrected formulas?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    No. Rating calculated by corrected formulas are current ratings :).

    → Reply
»
9 years ago, # |
  Vote: I like it +59 Vote: I do not like it

→ Reply