Дни экзаменов
В сессии n экзаменов. Некоторые пары экзаменов нельзя ставить в один день: у них общие студенты. В один день можно провести сколько угодно экзаменов, лишь бы никакие два из них не конфликтовали. За сколько дней можно провести всю сессию?
В одном из тестов вместо экзаменов — двадцать самых упоминаемых ролей «Войны и мира» из статьи о раскраске графа: две роли конфликтуют, если персонажи встречаются в одной главе, а ответ — сколько нужно актёров.
Вход
В первой строке число экзаменов n и число конфликтующих пар m (1 ≤ n ≤ 20, 0 ≤ m ≤ n(n − 1)/2). Дальше m строк a b: экзамены a и b нельзя ставить в один день (1 ≤ a, b ≤ n, a ≠ b, пары не повторяются).
Выход
Одно число — наименьшее число дней.
Примеры
Пример 1
5 5 1 2 1 5 2 3 3 4 4 5
3
Пример 2
9 13 1 2 1 5 2 5 2 7 3 5 4 5 4 8 4 9 6 7 6 8 7 8 7 9 8 9
3
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 13 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если какие-то q экзаменов конфликтуют попарно, дней нужно не меньше q. Может быть, ответ — наибольшая такая группа? Проверьте на первом примере: пять экзаменов по кругу.
2Подсказка 2
Жадные способы из статьи — даже DSatur — ответа не гарантируют: на втором примере DSatur берёт четыре дня, а хватает трёх. Нужен точный способ, и экзаменов всего двадцать. Сколько всего подмножеств экзаменов? А что, если не искать расписание, а посчитать, сколько их?
3Идея
День — это независимое множество экзаменов: никакие два не конфликтуют. Сессия за k дней — это k независимых множеств, которые вместе покрывают все экзамены: если какой-то экзамен попал в несколько, оставим его в первом. Значит, ответ — наименьшее k, при котором число таких наборов положительно. А число наборов считается формулой включений и исключений через одно число на каждое подмножество экзаменов.
4Разбор
Обозначим через V все экзамены, а через i(S) — число независимых подмножеств множества S, пустое тоже считается.
Число упорядоченных наборов (I1, …, Ik) независимых множеств, которые вместе покрывают V, равно
$$a_k = \sum_{S \subseteq V} (-1)^{|V \setminus S|}\, i(S)^k.$$
i(S)k — это число наборов из k независимых множеств, которые все лежат внутри S. Возьмём какой-нибудь набор, и пусть U — объединение его множеств. Он посчитан в слагаемом каждого S, содержащего U, со знаком (−1)|V ∖ S|. Такие S получаются из V выбрасыванием любого подмножества T из V ∖ U, и сумма знаков равна ΣT (−1)|T| = (1 − 1)|V ∖ U|. Это ноль, если U ≠ V, и единица, если набор покрывает всё. Значит, каждый покрывающий набор посчитан ровно один раз, а остальные — ноль раз.
Числа i(S) для всех 2n подмножеств считаются по одному сложению на каждое. Возьмём в S экзамен v с наименьшим номером. Независимые подмножества S без v — это i(S ∖ {v}), а с v — те, где нет его соседей: i(S ∖ {v} ∖ соседи(v)). Подмножества и соседей удобно хранить битовыми масками, как в динамике по маскам: «S без v» — это S ^ low, где low = S & -S.
Дальше для k = 1, 2, … считаем ak и останавливаемся на первом ненулевом. Числа огромные — i(S) доходит до 220, а степень до двадцатой, — поэтому считаем по модулю двух больших простых. Пока k меньше ответа, ak равно нулю точно, и по любому модулю тоже ноль. На ответе ak положительно, и ноль по обоим модулям получился бы, только если оно делится на их произведение, — на тестах такого нет, это проверено точным перебором. На Python степени для всех миллиона подмножеств сразу удобно держать в массиве numpy: произведение двух чисел меньше 109 помещается в int64.
4+Решение
5Сложность
O(2n·n) времени и O(2n) памяти: миллион подмножеств и до двадцати степеней. Этот способ предложили Андреас Бьёрклунд, Тор Хусфельдт и Микко Койвисто в 2006 году; до них лучшие точные алгоритмы перебирали подмножества подмножеств, и им требовалось около 2,4n шагов.
Перебор с возвратом из статьи — DSatur, который при тупике пробует другой цвет, — на этих тестах тоже успевает, но гарантии у него нет: бывают графы, где он перебирает экспоненциально много раскрасок, прежде чем докажет, что меньше нельзя.
6Типичные ошибки
- Наибольшая клика. Нижняя оценка, но не ответ. Пять экзаменов по кругу не содержат трёх попарно конфликтующих, а дней нужно три. В графе Грёча из третьего теста нет даже треугольников, а дней нужно четыре.
- DSatur без возвратов. Это
wrong.py: на втором примере он ставит экзамены в четыре дня. - Степени без модуля. i(S)k не помещается ни в какой встроенный тип. На Python большие целые спасут правильность, но не время: миллион длинных чисел на каждое k — это уже много.
- Знаки. Знак слагаемого зависит от того, сколько экзаменов выброшено, а не сколько оставлено: (−1)n − |S|.
Алгоритмы задачи
O(V + E) — жадно в данном порядке и «наименьший последним»; O((V + E) log V) — DSatur с кучей
2 задачи
DP
Приём
Динамика по маскам
Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю.
O(2ⁿ · n²) для коммивояжёра
2 задачи