Блог пользователя CtrlAlt

Поправочные коэффициенты и инфляция рейтинга
Автор CtrlAlt, 15 лет назад, По-русски

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

Формула расчёта рейтинга Codeforces подразумевает сохранение суммы очков всех участников до и после раунда за счёт поправочных коэффициентов. На основании же обработанной мной информации получилась такая табличка:

ID контеста Суммарный рейтинг до соревнования Суммарный рейтинг после соревнования Разность конечного и исходного суммарных рейтингов Количество участников
1 99000 98996 -4 66
2 183277 183266 -11 122
3 396585 396585 0 264
4 416629 416637 8 282
5 500275 500277 2 332
6 337244 337019 -225 230
7 624688 624694 6 411
8 658766 658600 -166 433
9 370684 370777 93 257
10 721607 721616 9 468
11 654544 654506 -38 426
12 416724 416790 66 290
13 806298 806296 -2 527
14 427424 427573 149 299
15 0 0 0 0
16 360107 360137 30 252
17 792517 792401 -116 513
18 326823 326756 -67 230
19 707918 707814 -104 456
20 0 0 0 0
21 0 0 0 0
22 343355 343362 7 242
23 681290 681324 34 439
24 755594 755502 -92 482
25 442971 442894 -77 313
26 785824 785785 -39 509
27 557489 557471 -18 389
28 601741 601648 -93 379
29 503269 503223 -46 355
30 881545 881570 25 570
31 564723 564831 108 401
32 334878 335010 132 240
33 948486 948488 2 614
34 574277 574221 -56 410
35 345030 345030 0 249
36 611357 611353 -4 395
37 1061236 1061230 -6 690
38 855732 856735 1003 561
39 0 0 0 0
40 937278 937268 -10 604
41 527420 527663 243 378
42 843096 843021 -75 540
43 536735 536501 -234 382
44 0 0 0 0
45 0 0 0 0
46 968402 968864 462 625
47 509244 509165 -79 371
48 763167 764380 1213 496
49 491745 491653 -92 360
50 0 0 0 0
51 916950 916874 -76 571
52 0 0 0 0
53 357866 357721 -145 260
54 720782 720739 -43 457
55 742425 742350 -75 465
56 545445 545523 78 393
57 1041254 1041315 61 659
58 607273 607189 -84 439
59 529422 529181 -241 387
60 1236062 1236082 20 784
61 603817 603824 7 438
62 396618 396735 117 250
63 546991 547204 213 402
64 0 0 0 0
65 1316018 1315990 -28 832
66 919132 919016 -116 637
67 1177498 1203002 25504 737
68 1387541 1387526 -15 865
69 972509 972536 27 676
70 1441219 1441214 -5 897
71 941005 941093 88 664
72 0 0 0 0
73 1028615 1028584 -31 628
74 1320797 1320828 31 820
75 746001 745936 -65 518
76 0 0 0 0
77 671571 671574 3 360
78 939132 939114 -18 650
79 1412089 1412006 -83 878
80 1046962 1046913 -49 727
81 1739338 1739306 -32 1073
82 2628540 2628508 -32 1657
83 729252 729139 -113 391
84 1159245 1159270 25 810
85 1593644 1593998 354 895
86 685343 684832 -511 365
87 646555 646545 -10 342
88 845853 845896 43 581
89 652307 652384 77 345
90 990319 990418 99 682
91 630967 630967 0 336
92 1068012 1068076 64 738
93 585737 585736 -1 313
94 1094185 1094186 1 752
95 596727 596731 4 318
96 1214904 1214860 -44 836
97 260632 259983 -649 132
98 0 0 0 0
99 0 0 0 0
100 0 0 0 0
101 462015 462016 1 246
102 994526 994580 54 681
103 544250 544259 9 292
104 1263047 1263037 -10 860
105 1651105 1672075 20970 1034

Строки, содержащие нули, относятся к нерейтинговым контестам.
Можно видеть, что пока поправочные коэффициенты не всегда определяются идеально.
Самое интересное, что два соревнования являются "аномальными" и повышают общий рейтинг участников более чем на 20000 пунктов — это Manthan и последний Codeforces Beta Round #81.
В чём же причина подобных отклонений?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Моё имхо таково, что сказывается округление рейтинга.
Давай прикинем. Вот у всех людей сменился рейтинг. Причём сменился на какие-то нецелые значения. Потом всё округлилось. Округление меняет значение на величину от 0 до 0.5, т.е. в среднем погрешность получается ~0.25. Это объясняет люфт в пределах порядка 1/4 количества человек.

Но такие большие значения изменения действительно настораживают.

UPD: А, криво сказал. Это не моё имхо. Это моё объяснение, почему такие соображения не работают :-)
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Незачет тебе по математике 5-ого класса - (сумма модулей)!=(модуль суммы), и поэтому математическое ожидание погрешности округлений вообще говоря намного меньше чем (кол-во участников)/4.

    Насчет Manthan'а писали, что в том раунде приведение суммы к 0 отключили и это привело к небольшой единовременной инфляции. Возможно, с последним раундом произошло то же самое. Но меня удивляет еще и, например, 86 раунд. Вот откуда могло взяться изменение суммы рейтов больше 500 при всего лишь 365 участниках?
    → Ответить
    • 15 лет назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится 0 Проголосовать: не нравится

      Чесслово, я знаю, что это ооочень грубо. Могу честно, по-сунцово-физпраковски сделать.
      Видимо, нужно сказать, что с вероятностью 68.2% погрешность будет в пределах , где n - количество участников. Как-то так. А в пределах 3σ погрешность будет с вероятностью 99.7%, если не изменяет память.
      Я всего лишь хотел показать, что даже с такой грубой оценкой настолько большие расхождения не лезут ни в какие ворота.

      → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      В 86 раунде было много народу с 0 баллов, то есть серые-зелёные заняли относительно неплохое место(265), а согласно местной политике им не положено плюса. Пруф
      → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Мне всегда было интересно, на TC рейтинги умножаются на коэффициент, чтобы сумма рейтингов до контеста была сумме рейтингов после?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
По крайней мере в Мантане так вышло, что у Гены за первое место после поправки на инфляцию была отрицательная прибавка к рейтингу, так что ручками пофиксили до +1
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

А можно в эту таблицу вставить еще колонку с разницей суммарного рейтинга после и до соревнования (или модуль этой разницы)? А то не очень наглядно получается. И постоянно отнимать неудобно.

→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить