"Нам Лебедос и Пароход поставили первое место, а Мак - третье. Какое место мы займём?"
"У меня такой разброс мест в финале, я вообще не представляю, какое будет место."
Подобные вопросы часто возникают на турнирах. А всё потому что участники не совсем представляют, как происходит расчёт финальных оценок. Хочу раскрыть всю суть алгоритма skating, чтобы больше не возникало вопросов.
Алгоритм состоит из нескольких правил. Есть вполне очевидные:
- Правило #1: Судьи обязаны проставить места всем парам;
- Правило #2: Судьи проставляют места от 1 до N;
- Правило #3: Судья не может поставить две и более пар на одно и то же место;
С этим всё понятно. Остальные правила базируются на определении majority (большинство): паре однозначно определяется какое-либо из мест, если она набрала больше i-ых и выше мест, чем остальные пары. Когда будем рассматривать примеры, всё станет ясно.
- Правило #4: Определение мест (без учёта того, что пары могут претендовать по оценкам на одно место).
Алгоритм правила такой:
- Положим i = 1.
- Для каждой пары считаем количество i-ых и выше мест. Если для j-ой пары количество i-ых мест больше, чем у остальных пар, то определяем её как пару, занявшую i-ое место, и вычёркиваем из рассмотрения.
- Если места проставлены всем парам, то алгоритм считается завершённым.
- Положим 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: Определение мест (с учётом того, что пары могут претендовать по оценкам на одно место).
Алгоритм правила такой:
- Положим i = 1.
- Для каждой пары считаем количество i-ых мест плюс места выше. Если для j-ой пары количество i-ых мест больше, чем у остальных пар, то определяем её как пару, занявшую i-ое место, и вычёркиваем из рассмотрения.
- Если у двух и более пар одинаковое количество i-ых мест, то считаем сумму мест для каждой пары и запоминаем (не складываем с количеством i-ых мест!). Из этих пар выбираем пару с наименьшей суммой мест. Если таких пар несколько, то положим i = i + 1 и перейдём к пункту 4, не вычёркивая из рассмотрения эти пары (но предоставим им приоритет при подсчёте i + 1 и выше мест на следующей итерации).
- Если места проставлены всем парам, то алгоритм считается завершённым или была произведена S + 1 итерация алгоритма, где S — количество судей.
- Положим 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 место, потому что их неопределённость так и не разрешилось, а алгоритм уже дошёл до своего последнего девятого шага (этот шаг последний, так как было всего девять судей).
Это был алгоритм skating для одного танца в финале. Если читатели захотят продолжения, то опишу, как производится подсчёт мест в финале за два и более танцев.
Комментариев нет:
Отправить комментарий