Динамика комбинаторная и на подмножествах (26 ноября 2024)

1. Для старшей группы: анекдот (цель: показать, что динамика, это не только про пути)
   1. Динамика − часто это или "найти путь в графе", или "число путей в графе". Но не только.
   2. Приведите пример! Ответ: динамика по подотрезкам.
   
   
2. Динамика по подотрезкам (цель: закрепить уже изученное на практике, порядок переходов)
   1. Пример: произведение матриц. Сводим задачу к меньшим такого же вида.
   2. Динамика тоже описывается графом, но не является напрямую задачей поиска пути на этом графе
   
   
3. DP и возведение матрицы в степень
   1. Пути в графе (количество путей длины ровно k)
   2. Числа фибоначчи (начали на практике)
   3. Рекуррентные соотношения за O(k³ log n) (начали на практике)
   4. Реклама: рекуррентные соотношения можно решать и за O(k log k log n)
   
   
4. Комбинаторика
   1. Картинка с 6 перестановками и рассказ "какие задачи мы хотим решать" (object2index, index2object, next, prev)
   2. Указание лектору: начать нужно с перестановок, там формулы. Затем обязательно скобочные последовательности, там уже динамика.
   3. Объект по номеру, номер по объекту: примеры − перестановки, скобочные последовательности
   4. Зачем это нужно? Хранение объекта минимальным числом бит (например, на диске или состояние динамики; например, разбиение на слагаемые)
   5. Следующий лексикографически: пример перестановка, скобочная последовательность
   6. Зачем это нужно? Перебор всех объектов без рекурсии
   
   
5. Работа с множествами, как с целыми числами. Примеры на все операции.
   1. Биекция между числами 0..2ⁿ-1 и подмножествами {0,1,...,n-1}
   2. Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов.
   3. Пересечение, объединение, разность. Проверка, содержится ли.
   4. Добавить к множеству элемент: +, ^, |
   
   
6. Динамика по подмножествам
   1. Задачи: количество единичных бит в числе и сумма на подмножестве
   2. Версия за 2ⁿn и рекурсивная версия за 2ⁿ
   3. Динамика: количество бит в числе (popcount[i] = popcount[i/2] + i%2)
   4. Динамика: сумма на подмножестве (sum[i] = sum[i ^ bit] + w[bit])
   
   
7. Гамильтонов путь и цикл
   1. Определения.
   2. Решение задачи про путь за O(2ⁿn²) времени и O(2ⁿn) памяти is[A, v] → is[A|2^x,x].
   3. Сводим задачу про цикл к задаче про путь.
   4. Улучшаем память до 2ⁿ (битовый массив, минимальное изменение кода) end[A] |= 2^v.
   5. Улучшаем время до 2ⁿn (пересекается ли adj[x] c end[A^2^x])
   
   
8. Задача: покрасить вершины графа в минимальное число цветов
   1. Предподсчет good[A] за O(2ⁿn²). Решение за O(4ⁿ).
   2. Перебор всех подмножеств всех множеств циклами for за O(3ⁿ), решение нашей задачи за O(3ⁿ + 2ⁿn²).
   3. Замена O(2ⁿn²) на O(2ⁿ) (good[] - динамика).