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

Задача

Параллельные пары

распределённые системы контроль версий двоичный поиск два указателя подсчёт вариантов

Журнал событий устроен так же, как в задаче «Векторные отметки»: P процессов выполняют события по очереди, а событие может получить сообщение и тогда знает всё, что знало событие-отправитель. Событие a случилось раньше b, если от a к b можно дойти по следующим событиям процессов и по сообщениям; если ни одно не раньше другого, события параллельны.

Сколько всего пар параллельных событий? Пара неупорядоченная: {a, b} считается один раз. Один из тестов — история git этого сайта, где коммит — событие своей ветки, а слияние получает «сообщение» от вливаемого коммита.

Вход

В первой строке — P и E (1 ≤ P ≤ 30, 1 ≤ E ≤ 5·104). Дальше E строк: номер процесса p, число k полученных сообщений и номера k событий-отправителей, все меньше номера текущего события; суммарно k не больше 105.

Выход

Одно число — количество пар параллельных событий.

В первом примере параллельны пять пар: событие 5 — новое событие процесса 1, о котором никто не узнал, — параллельно событиям 2, 3, 4 и 6; кроме того, параллельны события 1 и 2. Во втором примере процессы не переписываются, и параллельна каждая пара событий разных процессов.

Примеры

Пример 1

Вход
3 6
1 0
2 0
2 1 1
3 1 3
1 0
3 0
Выход
5

Пример 2

Вход
2 4
1 0
2 0
1 0
2 0
Выход
4

Ограничения

Время · Python
10000 мс
Время · Go
2000 мс
Память
256 МБ
Проверка
7 тестов

Разбор

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

1Подсказка 1

Перебрать все пары — больше миллиарда при пятидесяти тысячах событий. Возьмите событие e процесса p и другой процесс q. Какие события q раньше e, какие позже — и как они расположены вдоль q?

2Идея

Посчитаем векторные часы, как в «Векторных отметках». События процесса q, которые раньше e, — это первые VCe[q] событий q: знать j-е событие цепочки — значит знать и все до него. События q, которые позже e, — это те, кто знает e, то есть у кого в позиции p стоит не меньше номера e внутри p. Вдоль процесса q эта позиция только растёт, поэтому знающие e образуют хвост цепочки q, а его начало находится двоичным поиском. Всё, что между первыми VCe[q] событиями и хвостом, параллельно e.

3Разбор

Для каждой пары процессов (p, q) выпишем, сколько знает о p каждое событие q, — неубывающий список. Для i-го события e процесса p найдём в нём первую позицию со значением не меньше i; параллельных e событий q — эта позиция минус VCe[q]. Сумма по всем e и q ≠ p считает каждую параллельную пару дважды — с каждой стороны, — поэтому делим на два. Пары внутри одного процесса никогда не параллельны.

Вместо двоичного поиска годятся и два указателя: при переходе к следующему событию p граница хвоста в q только сдвигается вперёд. В истории git сайта параллельных пар 31 873 из 790 653 — около 4 %: ветки живут недолго и вливаются в основную часто.

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

O(E · P) на векторы и O(E · P · log E) на подсчёт (с двумя указателями — O(E · P)). Ответ доходит до миллиарда с лишним — в пятом тесте процессы не переписываются вовсе, — так что нужен 64-битный счётчик.

5Типичные ошибки
  • Равные числа Лэмпорта. Параллельные события могут иметь любые числа Лэмпорта, а равные числа бывают только у параллельных — но далеко не у всех. Ответ выходит меньше; первый пример это ловит.
  • Перебор пар с векторами. Верно, но O(E² · P) — десятки миллиардов операций.
  • Пара дважды. Сумма по событиям видит каждую пару с обеих сторон; не забудьте поделить.

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

SYS Алгоритм Часы Лэмпорта и векторные часы Логические часы: одно число Лэмпорта согласовано с «случилось раньше», вектор по процессам отличает «раньше» от «параллельно». O(1) на событие у Лэмпорта, O(n) у векторных 2 задачи SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи
Каталог алгоритмов