CS
Задачник Базовый курс EN

Задача

Список покупок на двоих

распределённые системы репликация хеш-таблица симуляция

Список покупок живёт в нескольких копиях — у каждого члена семьи в телефоне. Каждая копия меняет список у себя и время от времени получает целиком состояние другой копии. Чтобы копии сходились и ничего не терялось, список устроен как OR-множество (множество с наблюдаемым удалением).

  • add r x — копия r добавляет элемент x. Каждое добавление получает новую метку — пару (r, k), где k — номер этого добавления среди добавлений копии r, считая с 1. Копия запоминает пару (x, метка).
  • remove r x — копия r вычёркивает x: все метки элемента x, которые она видит сейчас, становятся удалёнными. Метки, которых она ещё не видела, не трогаются.
  • sync a b — копия b получает состояние копии a: объединяет свои пары с парами a, а свои удалённые метки — с удалёнными метками a.
  • show r — показать список копии r: элемент в списке, если у него есть хотя бы одна неудалённая метка.

Выполните операции и выведите ответы на все show.

Вход

В первой строке — число копий R и число операций n (1 ≤ R ≤ 20, 1 ≤ n ≤ 2·104). Дальше n операций, по одной в строке. Элементы — целые от 1 до 109, номера копий — от 1 до R. Операций sync не больше 1500, операций show — не больше 300.

Выход

На каждую операцию show — строку с элементами списка по возрастанию через пробел или -, если список пуст.

В первом примере второй член семьи вычёркивает молоко (7), а первый, ещё не зная об этом, снова добавляет молоко. Вычёркивание касается только той метки, которую видел второй, поэтому после обмена молоко в списке у обоих: одновременное добавление побеждает удаление. Во втором примере одно и то же число 5 добавили две копии, и вычеркнуть его до конца удаётся, только когда третья копия увидела обе метки.

Примеры

Пример 1

Вход
2 10
add 1 7
add 1 9
sync 1 2
remove 2 7
add 1 7
show 2
sync 2 1
sync 1 2
show 1
show 2
Выход
9
7 9
7 9

Пример 2

Вход
3 12
add 1 5
add 2 5
sync 1 3
remove 3 5
show 3
sync 2 3
show 3
remove 3 5
sync 3 1
sync 3 2
show 1
show 2
Выход
-
5
-
-

Ограничения

Время · Python
8000 мс
Время · Go
4000 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Почему нельзя хранить просто множество элементов и множество удалённых элементов? Что станет с молоком из первого примера, если «вычеркнуть» значит «больше никогда»?

2Идея

Удаляется не элемент, а конкретные добавления, которые удаляющий видел. Поэтому у каждого добавления своя метка, и состояние копии — два множества: пары (элемент, метка) и удалённые метки. Оба только растут, и слияние — объединение; объединение коммутативно, ассоциативно и идемпотентно, поэтому копии, получившие одни и те же состояния в любом порядке и сколько угодно раз, видят одно и то же. Элемент в списке, если у него осталась живая метка. Добавление, о котором удаляющий не знал, его удаление не задевает, — отсюда правило «добавление побеждает».

3Разбор

Для каждой копии — множество пар и множество удалённых меток, счётчик своих добавлений. add кладёт новую пару. remove переносит в удалённые все метки элемента из своих пар. sync — два объединения. show — элементы пар с метками не из удалённых, без повторов, по возрастанию.

Удалённые метки хранятся навсегда, как надгробия в RGA: без них пришедшая позже старая пара снова оживила бы элемент. В настоящих системах надгробия со временем убирают, когда все копии подтвердили, что их видели.

3+Решение
4Сложность

add — O(1); remove и show — O(размер состояния копии); sync — O(размер состояния отправителя). Состояние растёт с числом добавлений, поэтому в задаче ограничено число обменов и показов.

5Типичные ошибки
  • Удалять элемент, а не метки. Так устроено «двухфазное множество»: вычеркнутое не вернётся никогда. Первый пример это ловит.
  • Удалять метки, которых не видел. Если remove вычеркнет элемент и во всех будущих состояниях, параллельное добавление пропадёт — это ровно та потеря, от которой OR-множество защищает.
  • Метка без номера копии. Номер добавления сам по себе не уникален: у двух копий есть своё «первое добавление».

Алгоритмы задачи

SYS Структура данных CRDT Данные, копии которых правят независимо и сливают в любом порядке: счётчики, множества, текст. O(1) на операцию у счётчика и множества; вставка в текст — O(1) в среднем 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи
Каталог алгоритмов