Динамика (28 октября 2014)

  1. Работа с множествами, как с целыми числами. Примеры на все операции.
    1. Биекция между числами 0..2n-1 и подмножествами {0,1,...,n-1}
    2. Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов.
    3. Пересечение, объединение, разность. Проверка, содержится ли.
    4. Добавить к множеству элемент: +, ^, |
  2. Динамика по подмножествам
    1. Сумма на подмножестве: рекурсия, динамика
    2. Количество бит в числе, старший бит, перевернутая битовая запись
    3. Пример задачи: покрыть множество {0,1,...,n-1} минимальным числом множеств из набора A1,...,Am
  3. Задача: покрасить вершины графа в минимальное число цветов
    1. Предподсчет good[A] за O(2nn2). Решение за O(4n).
    2. Перебор всех {под/над}множеств всех множеств циклами for за O(3n), решение нашей задачи за O(3n + 2nn2).
    3. Замена O(2nn2) на O(2n) (good[] - динамика).
    4. Бонус: описание решения за O(2.44n).
  4. Гамильтонов путь и цикл
    1. Определения.
    2. Решение задачи про путь за O(2nn2) времени и O(2nn) памяти is[A, v] → is[A|2x,x].
    3. Сводим задачу про цикл к задаче про путь.
    4. Улучшаем память до 2n (битовый массив, минимальное изменение кода) end[A] |= 2v.
    5. Улучшаем время до 2nn (пересекается ли adj[x] c end[A^2x])