Векторные отметки
В системе P процессов. Каждый процесс выполняет события по очереди, и события пронумерованы по порядку записи в журнал: 1, 2, …, E. Кроме того, событие может получить сообщение — тогда оно знает всё, что знало событие-отправитель на момент отправки. Событие a случилось раньше события b, если от a к b можно дойти, переходя к следующему событию того же процесса или по сообщению. Если ни a не раньше b, ни b не раньше a, события параллельны.
Ответьте на вопросы о парах событий. Один из тестов — история git этого сайта: коммит — событие своей ветки, а слияние получает «сообщение» от вливаемого коммита.
Вход
В первой строке — P и E (1 ≤ P ≤ 50, 1 ≤ E ≤ 105). Дальше E строк: номер процесса p (от 1 до P), число k полученных сообщений и номера k событий-отправителей — все меньше номера текущего события. Суммарно k не больше 2·105. Затем число вопросов q (1 ≤ q ≤ 105) и q строк с номерами событий a и b.
Выход
На каждый вопрос — символ: <, если a случилось раньше b; >, если позже; =, если это одно событие; |, если параллельны.
В первом примере сообщение идёт от события 1 (процесс 1) к событию 3 (процесс 2) и от события 3 к событию 4 (процесс 3), поэтому 1 раньше 4. А событие 5 — новое событие процесса 1 — никому не передано: оно параллельно и событию 4, и событию 2.
Примеры
Пример 1
3 6 1 0 2 0 2 1 1 3 1 3 1 0 3 0 6 1 4 4 1 5 4 2 5 3 3 6 1
< > | | = >
Пример 2
2 4 1 0 2 0 1 0 2 0 4 1 3 1 2 3 4 4 2
< | | >
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Обход графа событий на каждый вопрос — до 105 шагов на вопрос. Что, если заранее записать в каждое событие, сколько событий каждого процесса оно знает?
2Идея
Это векторные часы. Вектор события — по счётчику на процесс: покомпонентный максимум вектора предыдущего события своего процесса и векторов всех полученных сообщений, а затем +1 в своём процессе. Тогда в позиции q вектора записано число событий процесса q, которые случились раньше (или совпадают с текущим, если это его процесс).
Сравнивать векторы целиком не нужно. Пусть a — i-е событие процесса p. Событие b знает a ровно тогда, когда в его векторе в позиции p стоит не меньше i: события процесса p идут цепочкой, и знать i-е — значит знать первые i. Один взгляд в одну ячейку.
3Разбор
Идём по журналу. Вектор события — копия вектора предыдущего события своего процесса (или нули), к ней покомпонентным максимумом добавляются векторы отправителей, и своя позиция растёт на единицу; её новое значение и есть номер события внутри процесса. Вопрос: если a = b — «=»; если вектор b в позиции процесса a не меньше номера a — «<»; симметрично — «>»; иначе «|».
Память — E · (P + 1) чисел, до пяти миллионов: в Go это один плоский массив, в Python — список списков, и он помещается. В истории git сайта на двадцать тысяч случайных пар 854 параллельных — 4,3 %.
3+Решение
4Сложность
O(E · P + (сумма k) · P) на векторы и O(1) на вопрос.
5Типичные ошибки
- Часы Лэмпорта. Если a раньше b, у a число Лэмпорта меньше, — но не наоборот: меньшее число бывает и у параллельного события. Ответ «|» по ним не получить; первый пример это ловит.
- Забыть предыдущее событие своего процесса. Вектор события — не только максимум отправителей: всё, что знал процесс раньше, он знает и сейчас.
- Сравнивать векторы покомпонентно. Верно, но 50 сравнений на вопрос вместо одного; в Python на ста тысячах вопросов это заметно.
Алгоритмы задачи
O(1) на событие у Лэмпорта, O(n) у векторных
2 задачи
GRA
Алгоритм
Топологическая сортировка
Выстраивает вершины графа без циклов так, чтобы все рёбра смотрели вперёд, за O(V + E).
O(V + E)
2 задачи