Что зафиксировано
Лидер Raft в сроке T держит журнал из L записей; у каждой записи свой срок, и вдоль журнала сроки не убывают. Последователи по мере репликации сообщают лидеру, сколько записей журнала у них уже совпадает с его журналом: «последователь f подтвердил m записей». Лидер считает и себя — у него все L.
Запись с номером i зафиксирована, если у большинства серверов (больше половины из n, считая лидера) подтверждено не меньше i записей и запись i сделана в текущем сроке T. Вместе с ней зафиксированы все записи перед ней. Граница фиксации никогда не уменьшается. После каждого подтверждения выведите номер последней зафиксированной записи.
Вход
В первой строке — n, L, T и начальная граница фиксации c (n нечётно, 3 ≤ n ≤ 9, 1 ≤ L ≤ 105, 0 ≤ c ≤ L). Во второй — сроки записей журнала по порядку: L чисел, не убывают, каждый от 1 до T. В третьей — число подтверждений q (1 ≤ q ≤ 2·105), дальше q строк «f m»: последователь f (от 1 до n − 1; лидер — сервер 0) подтвердил m записей (0 ≤ m ≤ L). Подтверждения одного последователя не убывают. Сначала у всех последователей подтверждено 0.
Выход
q строк: граница фиксации после каждого подтверждения.
Первый пример — конец рисунка 8 из статьи о Raft. Запись срока 2 уже у трёх серверов из пяти, но не зафиксирована: лидер срока 4 фиксирует её только вместе со своей записью, когда та дойдёт до большинства.
Примеры
Пример 1
5 3 4 1 1 2 4 4 1 2 2 2 1 3 2 3
1 1 1 3
Пример 2
3 4 3 2 1 1 2 2 3 1 3 2 4 1 4
2 2 2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Запись, которая есть у большинства, — это запись с номером не больше (n/2 + 1)-го по величине числа подтверждений. Какая из таких записей — последняя сделанная в текущем сроке?
2Идея
Сроки вдоль журнала не убывают, а T — наибольший возможный, поэтому записи текущего срока — хвост журнала с некоторого номера first (или их нет вовсе). Пусть M — (⌊n/2⌋ + 1)-е по величине число подтверждений, считая лидера с его L: ровно столько записей есть у большинства. Если M ≥ first, запись M — текущего срока и у большинства, граница становится max(c, M). Если M < first, новых зафиксированных записей нет, даже если M больше c.
3Разбор
Серверов не больше девяти, и после каждого подтверждения достаточно отсортировать девять чисел. Почему правило именно такое, показывает вторая сцена статьи. Запись старого срока у большинства ещё может быть перезаписана: сервер, чья последняя запись новее по сроку, выигрывает выборы голосами тех, у кого эта старая запись лежит последней, — и заставляет их журналы совпасть со своим. А запись текущего срока у большинства уже не перезапишет никто: будущий лидер должен получить голос хотя бы одного из этого большинства, а тот голосует только за журнал не хуже своего, — значит, в журнале победителя эта запись есть. Поэтому старые записи фиксируются только «под прикрытием» новой.
3+Решение
4Сложность
O(L + q·n log n).
5Типичные ошибки
- Считать только копии. Граница M без проверки срока — ровно та ошибка, которую разбирает рисунок 8: в первом примере такое решение выведет 2 уже на втором подтверждении.
- Забыть лидера. Его журнал тоже входит в большинство, и в нём все L записей.
- Граница назад. Если подтверждения не дотягивают до прежней границы, она не уменьшается.