Динамика по подмножествам, по профилю (2 декабря 2019)

  1. Задача: покрасить вершины графа в минимальное число цветов
    1. Напоминание: умеем за 3n + 2nn2
    2. 2nn2 → 2n (можно ещё раз, если уже было)
    3. Алгоритм перебора всех максимальных по включению за 3n/3 = 1.44n
    4. Покраска вершин, описание решения за O(2.44n). Доказательство: (1+1.44)n

  2. Задачи на подмножествах
    1. [есть в прошлом теордз!] Рюкзак (Set Cover: покрыть множество {0,1,...,n-1} минимальным числом множеств из набора A1,...,Am
    2. Перевёрнутая битовая запись числа (001101 → 101100)
− Перерыв −
  1. Meet-In-The-Middle
    1. Решение задачи о рюкзаке
      1. Выбрать подмножество заданной суммы за 2n/2 (2 способа: сортировка, хеш-таблица)
      2. Выбрать подмножество веса до W максимальной стоимостью за 2n/2n (сортировка и префиксный минимум)
    2. Решение задачи о поиске максимальной клики (подводка к кликам: выбрать дружную компанию на день рождения)
      1. За 2n
      2. Классический Meet-In-The-Middle. 2n/2n (до 2n/2 можно не оптимизировать)
      3. Перебор (две ветки: берём или не берём) с отсечением запоминанием + док-во того, что не более 2n/2 состояний

  2. DP и скошенный профиль через рекурсию (задача про доминошки)
    1. Перебор за O(2wh/2) go(x,y), если клетка уже покрыта, пропускаем, иначе 2 варианта
    2. Запоминание → получили динамику → доказали число состояний O(2w,h}wh), улучшили до O(2min(w,h)wh)
    3. Из доказательства видно, что можно хранить не map, а массив f[w,h,2w]
    4. Как в общем случае кодировать матрицу? Матрица → битовое число длины wh → остаток по модулю (1018+3)