Все задачи
Сложно Решено: 0 Процент решений: 0%

Победитель по методу ранжированных пар

Найдите победителя выборов по методу ранжированных пар, закрепляя победы в парных сравнениях, которые не образуют цикл.

Чему вы научитесь

  • Строить таблицу парных предпочтений по ранжированным бюллетеням
  • Сортировать победы по перевесу с точными правилами при равенстве
  • Закреплять рёбра, только если граф остаётся ациклическим

Условие

Метод ранжированных пар выбирает победителя, рассматривая все парные сравнения кандидатов. Каждый избиратель ранжирует всех кандидатов, и кандидат a побеждает кандидата b, если a ставят выше b больше избирателей, чем ставят b выше a. Перевес этой победы равен (число избирателей за a) − (число избирателей за b). Пары, где у обеих сторон поровну, не рассматриваются.

  1. Отсортируйте победы по перевесу, начиная с наибольшего. При равном перевесе раньше идёт победа с меньшим номером победителя, а затем с меньшим номером проигравшего.
  2. Пройдите по победам в этом порядке и закрепите каждую как стрелку от победителя к проигравшему, если только эта стрелка не замкнёт цикл с уже закреплёнными стрелками (то есть если проигравший ещё не может дойти до победителя по закреплённым стрелкам). Такая победа пропускается.
  3. Победителями становятся кандидаты, в которые не входит ни одна закреплённая стрелка.

Реализуйте ranked_pairs_winner(candidates, ballots).

Входные данные

candidates: имена кандидатов. Кандидат i - это candidates[i].

ballots: по одной строке на избирателя: номера кандидатов (с 0) от самого предпочтительного к наименее предпочтительному. В каждой строке каждый кандидат встречается ровно один раз.

Выходные данные

Верните имена всех кандидатов, в которые не входит ни одна закреплённая стрелка, в том порядке, в котором они идут в candidates. Обычно это одно имя; их может быть несколько, если в некоторых парах была ничья, а если бюллетеней нет, это все кандидаты.

Ограничения

1 ≤ длина candidates ≤ 9

0 ≤ количество бюллетеней ≤ 200

Примеры

Пример 1
Ввод:
candidates = ["Ann", "Bob", "Cal"]
ballots = [
    [0, 1, 2],
    [0, 1, 2],
    [0, 1, 2],
    [1, 2, 0],
    [1, 2, 0],
    [2, 0, 1],
    [2, 0, 1],
    [2, 0, 1],
    [2, 0, 1]
]

Ожидаемый вывод:
expected = ["Cal"]
Ввод:
std::vector<std::string> candidates = {"Ann", "Bob", "Cal"};
std::vector<std::vector<long long>> ballots = {
    {0, 1, 2},
    {0, 1, 2},
    {0, 1, 2},
    {1, 2, 0},
    {1, 2, 0},
    {2, 0, 1},
    {2, 0, 1},
    {2, 0, 1},
    {2, 0, 1}
};

Ожидаемый вывод:
std::vector<std::string> expected = {"Cal"};
Ввод:
string[] candidates = new string[] {"Ann", "Bob", "Cal"};
long[][] ballots = new long[][] {
    new long[] {0, 1, 2},
    new long[] {0, 1, 2},
    new long[] {0, 1, 2},
    new long[] {1, 2, 0},
    new long[] {1, 2, 0},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1}
};

Ожидаемый вывод:
string[] expected = new string[] {"Cal"};

Пояснение

Cal побеждает Ann со счётом 6:3 (перевес 3), Ann побеждает Bob 7:2 (перевес 5), а Bob побеждает Cal 5:4 (перевес 1). Закрепляем Ann над Bob, затем Cal над Ann; Bob над Cal замкнул бы цикл, поэтому пропускаем. В Cal не входит ни одна стрелка: ["Cal"].

Пример 2
Ввод:
candidates = ["Ann", "Bob"]
ballots = [
    [0, 1],
    [1, 0]
]

Ожидаемый вывод:
expected = ["Ann", "Bob"]
Ввод:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
    {0, 1},
    {1, 0}
};

Ожидаемый вывод:
std::vector<std::string> expected = {"Ann", "Bob"};
Ввод:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0}
};

Ожидаемый вывод:
string[] expected = new string[] {"Ann", "Bob"};

Пояснение

У Ann и Bob ничья 1:1, поэтому ни одна стрелка не закрепляется и возвращаются оба: ["Ann", "Bob"].

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

В каждом бюллетене кандидат предпочтительнее всех, кто стоит после него.

Подсказка 2

Перед тем как закрепить стрелку от победителя к проигравшему, выполните поиск от проигравшего по закреплённым стрелкам; если дошли до победителя, пропустите эту победу.

Подсказка 3

В конце победитель - это кандидат без входящих закреплённых стрелок.

Ожидаемая сложность

время O(b × c^2 + c^4), доп. память O(c^2)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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