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

  1. Динамика по подотрезкам
    1. Сводим задачу к меньшим такого же вида
    2. Динамика тоже описывается графом, но не является напрямую задачей поиска пути на этом графе

  2. Тестирование (на примере pn+1,k ≥ pn,k ≥ pn,k-1)
    1. Стресс-тестирование

  3. Доказательство pn+1,k ≥ pn,k ≥ pn,k-1
    1. Первое: два раза рисуем 4 картинки, в первом случае в 4-й центр − q1, во втором случае − q2
    2. Второе через первое, добавляем строгость

  4. Комбинаторика
    1. Объект по номеру, номер по объекту: примеры − перестановки, скобочные последовательности
    2. Зачем это нужно? Хранение объекта минимальным числом бит (например, на диске или состояние динамики; например, разбиение на слагаемые)
    3. Следующий лексикографически: пример перестановка, скобочная последовательность
    4. Зачем это нужно? Перебор всех объектов без рекурсии

  5. Работа с множествами, как с целыми числами. Примеры на все операции.
    1. Биекция между числами 0..2n-1 и подмножествами {0,1,...,n-1}
    2. Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов.
    3. Пересечение, объединение, разность. Проверка, содержится ли.
    4. Добавить к множеству элемент: +, ^, |

  6. Динамика по подмножествам
    1. Задачи: количество единичных бит в числе и сумма на подмножестве
    2. Версия за 2nn и рекурсивная версия за 2n
    3. Динамика: количество бит в числе (bn[i] = bn[i/2] + i%2)
    4. Динамика: сумма на подмножестве (sum[i] = sum[i bit] + w[bit])

  7. Гамильтонов путь и цикл
    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])

  8. Задача: покрасить вершины графа в минимальное число цветов
    1. Предподсчет good[A] за O(2nn2). Решение за O(4n).
    2. Перебор всех подмножеств всех множеств циклами for за O(3n), решение нашей задачи за O(3n + 2nn2).
    3. Замена O(2nn2) на O(2n) (good[] - динамика).
    4. Алгоритм перебора всех максимальных по включению за 3n/3 = 1.44n
    5. Покраска вершин, описание решения за O(2.44n).