Кто может стать лидером
Кластер Raft из n серверов пережил сбой: часть серверов лежит, а сеть могла разделиться на группы, которые друг друга не слышат. Начинаются выборы. О журнале каждого сервера известно только, какова его последняя запись: её срок и номер.
Кандидат голосует за себя. Другой сервер отдаёт ему голос, если сам работает, слышит кандидата (они в одной группе) и журнал кандидата не отстаёт от его собственного: срок последней записи у кандидата больше, или срок тот же, а номер не меньше. Кандидат побеждает, если голосов больше половины от всех n серверов — лежащих тоже. Считайте, что в новом сроке ещё никто ни за кого не голосовал. Для каждого кластера выведите всех серверов, которые могут стать лидером.
Вход
В первой строке — число кластеров q (1 ≤ q ≤ 105). Для каждого — число серверов n (1 ≤ n ≤ 9) и n строк «t i u g»: срок и номер последней записи (1 ≤ t, i ≤ 109), 1 — сервер работает, 0 — лежит, номер группы сети (от 1 до n). Всего серверов во всех кластерах не больше 3·105.
Выход
Для каждого кластера — номера серверов (с единицы), которые могут выиграть выборы, по возрастанию через пробел, или 0, если таких нет.
Первый пример — рисунок 8 статьи о Raft. В первом кластере лидер S1 лежит, а его запись срока 2 уже у S2 и S3; выиграть может и S5, у которого последняя запись срока 3, — и тогда он перезапишет запись срока 2. Во втором кластере S1 успел довести до S2 и S3 запись своего срока 4, и S5 уже не победит.
Примеры
Пример 1
2 5 2 2 0 1 2 2 1 1 2 2 1 1 1 1 1 1 3 2 1 1 5 4 3 0 1 4 3 1 1 4 3 1 1 1 1 1 1 3 2 1 1
2 3 5 2 3
Пример 2
2 5 5 40 1 1 5 40 1 1 5 38 1 2 4 30 1 2 5 39 1 2 3 3 7 1 1 3 7 1 1 3 7 1 1
5 1 2 3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Голоса нужно больше половины от n, а не от группы: группа из двух серверов кластера из пяти не выберет лидера никогда. А кто внутри группы отдаст голос — зависит только от сравнения последних записей.
2Идея
Для каждого работающего кандидата c посчитаем, сколько работающих серверов его группы (вместе с ним самим) имеют последнюю запись не новее его: пару (срок, номер) не больше его пары в лексикографическом порядке. Если таких больше n/2, c может победить. Это то самое ограничение выборов из статьи: оно и гарантирует, что новый лидер знает все зафиксированные записи.
3Разбор
Серверов в кластере не больше девяти, и сравнить каждого с каждым — 81 сравнение. Сравнение по сроку и номеру — именно в таком порядке: журнал со старшим сроком последней записи новее, даже если он короче. Во втором примере в группе из трёх серверов побеждает только S5 с последней записью (5, 39): у S3 запись (5, 38) — голосов наберётся два, у S4 срок 4 — только свой.
Почему ограничение работает. Зафиксированная запись есть у большинства. Любое большинство пересекается с большинством, которое проголосует за нового лидера, — хотя бы один сервер в обоих. Этот сервер голосует только за журнал не хуже своего, а в его журнале зафиксированная запись есть; поэтому она есть и у победителя.
3+Решение
4Сложность
O(n²) на кластер, всего O(Σn²).
5Типичные ошибки
- Без сравнения журналов. Если голосовать за любого, лидером станет сервер, пропустивший зафиксированные записи, и сотрёт их у остальных.
- Большинство группы. Нужно больше половины от всех n серверов: лежащие и отрезанные тоже считаются в знаменателе.
- Сравнение по длине. Сначала срок последней записи, потом номер: короткий журнал со старшим сроком новее длинного.