Как работает скейтинг.

(Онлайн-калькулятор для расчета мест в финале: http://discoswing.ru/skating )

Нам Лебедос и Пароход поставили первое место, а Мак — третье. Какое место мы займём?
У меня такой разброс мест в финале, я вообще не представляю, какое будет место.
Как из судейских оценок вычисляют финальные места? Используется специальный алгоритм: скейтинг.
Давайте посмотрим, как он работает. И разберем реальный пример с прошлого ЧР-а.
 Алгоритм состоит из нескольких правил. Есть вполне очевидные:
  • Правило #1: Судьи обязаны проставить места всем парам;
  • Правило #2: Судьи проставляют места от 1 до N;
  • Правило #3: Судья не может поставить две и более пар на одно и то же место;
С этим всё понятно. Остальные правила базируются на определении majority (большинство): паре однозначно определяется какое-либо из мест, если она набрала больше i-ых и выше мест, чем половина от количества судей. Когда будем рассматривать примеры, всё станет ясно.
  • Правило #4: Определение мест (без учёта того, что пары могут претендовать по оценкам на одно место).
Алгоритм правила такой:
  1. Положим i = 1.
  2. Для каждой пары считаем количество i-ых и выше мест. Если для j-ой пары количество i-ых мест больше, чем половина от количества судей, то определяем её как пару, занявшую i-ое место, и вычёркиваем из рассмотрения.
  3. Если места проставлены всем парам, то алгоритм считается завершённым.
  4. Положим i = i + 1 и перейдём к пункту 2.
Рассмотрим пример 1:
Судьи Места Результат
A   B     C     D     E    1  1-2 1-3 1-4 1-5 1-6 1-7
 10 1 1 1 2 1 4 --- --- --- --- --- --- 1
 20 4 2 2 1 2 1 4 --- --- --- --- --- 2
 30 3 3 3 5 4 --- --- 3 --- --- --- --- 3
 40 2 4 5 4 3 --- 1 2 4 --- --- --- 4
 50 5 6 4 3 5 --- --- 1 2 4 --- --- 5
 60 6 5 6 6 6 --- --- --- --- 1 5 --- 6
Шаг 1. Считаем первые места. Для пары 10 их количество равно четырём, для пары 20  одно место. Однозначно определяем место пары 10 как первое и больше её не рассматриваем.
Шаг 2. Считаем для оставшихся пар количество вторых мест + количество первых мест. Для пары 20 это четыре, для пары 40  одно. Пара 20 получает второе место.
Шаг 3. Считаем для пар третьи + вторые + первые места...
...
Шаг 7. Все места посчитаны, можно раздавать призы.
  • Правило #5: Определение мест (с учётом того, что пары могут претендовать по оценкам на одно место).
Алгоритм правила такой:
  1. Положим i = 1.
  2. Для каждой пары считаем количество i-ых мест плюс места выше. Если для j-ой пары количество i-ых мест больше, чем у остальных пар, то определяем её как пару, занявшую i-ое место, и вычёркиваем из рассмотрения.
  3. Если у двух и более пар одинаковое количество i-ых мест, то считаем сумму мест для каждой пары и запоминаем (не складываем с количеством i-ых мест!). Из этих пар выбираем пару с наименьшей суммой мест. Если таких пар несколько, то положим i = i + 1 и перейдём к пункту 4, не вычёркивая из рассмотрения эти пары (но предоставим им приоритет при подсчёте i + 1 и выше мест на следующей итерации).
  4. Если места проставлены всем парам, то алгоритм считается завершённым или была произведена S + 1 итерация алгоритма, где S  количество судей.
  5. Положим i = i + 1 и перейдём к пункту 3.
Пример 2:
Судья Места Результаты
A B C D E F G 1 1-2 1-3 1-4 1-5 1-6 1-7 1-8
10 3 1 6 1 1 2 1 4 --- --- --- --- --- --- --- 1
20 2 2 1 5 3 1 3 2 4(6) --- --- --- --- --- --- 2
30 1 5 4 2 2 6 2 1 4(7) --- --- --- --- --- --- 3
40 5 4 2 4 6 5 4 --- 1 1 4(14) 6 --- --- --- 4
50 4 6 3 3 5 4 6 --- --- 2 4(14) 5 --- --- --- 5
60 6 3 5 6 4 3 5 --- --- 2 3 5 --- --- --- 6
Шаг 1. Считаем первые места. У пары 10 их 4, у 20  2, у 30  1. Пара 10 однозначно определяется как победитель.
Шаг 2. Считаем вторые + первые места. У пары 20 их 4, у 30  4, у 40  1. Так как две пары по большинству мест претендуют на второе место, то считаем сумму их оценок: 6 и 7 соответственно. У пары номер 20 сумма меньше, поэтому она становится второй, а пара 30  третьей.
...
Шаг 4. При подсчёте четвёртых + третьих + вторых + первых мест пары 40 и 50 набрали одинаковое количество как самим мест, так и одинаковые суммы этих мест. Поэтому на следующем шаге они опять рассматриваются, для них считаются пятые + ... места. Мы получаем 6 для пары 40, 5 для пары 50 и 5 для пары 60. Пара 40 становится четвёртой, пара 50 — пятой, пара 60  шестой.
Хотя на Шаге 4 пары 50 и 60 набрали одинаковое количество пятых + ... мест, у пары 50 приоритет, так как она претендовала на четвёртое место.
...
Шаг 6. Все места расставлены.

Рассмотрим последний пример 3:
Судьи Места Результаты
A B C D E F G H I 1 1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9
049 1 1 5 1 1 1 1 5 2 6 1
059 6 3 2 4 3 2 2 1 5 1 4 6(13) 7(17) 8(22) 9(28) 9(28) 9(28) 9(28) 2.5
114 2 5 1 3 4 3 3 6 1 2 3 6(13) 7(17) 8(22) 9(28) 9(28) 9(28) 9(28) 2.5
174 8 2 8 7 5 6 5 2 3 --- 2 3 3 5 4
047 5 7 3 6 7 7 4 3 6 --- --- 2 3 4 6 5
142 3 8 4 8 2 8 6 4 7 --- 1 2 4 4 5(19) --- 6
170 4 4 6 2 8 4 8 8 8 --- 1 1 4 4 5(20) --- --- 7
048 7 6 7 5 6 5 7 7 4 --- --- --- 1 3 5(26) --- --- --- 8

Это реальная таблица финала D-класса Чемпионата России 2014 года.

Шаг 1. Считаем первые места: пара 49  6 мест (большинство), пара 59  одно место, пара 114  два места. Отмечаем 49-ых как победителей и больше их не рассматриваем.
Шаг 2. Считаем вторые + первые места: 59  4 места, 114  3 места, 174  два места, 142 и 170  по одному месту. Хотя у пары 59 больше всех вторых + первых мест, им пока не присуждается второе место в финале, потому что они не набрали большинство. Идём дальше.
Шаг 3. Не буду подробно описывать, обращу лишь Ваше внимание на то, что пары 59 и 114 набрали одинаковое большинство третьих + ... мест, и сумма этих мест у них равно. Подобное было в примере 2. Пока никому никакие места в финале не раздаём, двигаемся дальше.
Шаг 4. Снова та же ситуация у пар 59 и 114, а пары 174 и 47 претендуют на четвёртое место.
Шаг 5. Пары 59 и 114 опять претендуют на второе место. Пара 174 получает четвёртое место, потому что набирает большинство и обходит пару 47, которая теперь соревнуется с парами 142 и 170 за пятое место.
Шаг 6. Претендентство на второе место между парами 59 и 114 так и не разрешилось, пара 47 получает пятое место в финале, поскольку большинство (шесть мест). Пары 142, 170 и 48 соревнуются за шестое место. Подсчёт суммы мест однозначно определяет пары 142, 170 и 48 на шестое, седьмое и восьмое места соответственно.
...
Шаг 9. Пары 59 и 144 определяем на 2-3 место, потому что их неопределённость так и не разрешилось, а алгоритм уже дошёл до своего последнего девятого шага (этот шаг последний, так как было всего девять судей).

Это был алгоритм скейтинга для одного танца в финале. Если читатели захотят продолжения, то опишу, как ведется подсчёт мест в финале за два и более танцев (и как одна оценка в финале абсолюта повлияла на результат Чемпионата)

Кирилл Трибунский
http://discofoxfamily.blogspot.ru/2014/12/skating.html