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

  1. Динамика: общие идеи
    1. Динамика вперед, назад, рекурсивно-ленивая (на примере задачи про калькулятор)
    2. Динамика и ацикличный граф: состояния, переходы, вперед, назад, ленивая
    3. Рюкзак. Только веса, ценностей нет. Решение за O(nW) и O(W) памяти с восстановлением ответа.
  2. Примеры задач
    1. Наибольшая общая подпоследовательность двух, трех (делаем память линейной, квадратной)
    2. Найти кратчайший путь/количество путей коня, который ходит только вправо (общие слова про ацикличный граф, в ацикличном графе просто искать путь)
    3. Нужно упаковать строку: задача folding, динамика на подотрезках
    4. Нужно упаковать строку: LZSS
    5. Нужно посчитать количество путей длины k. Или кратчайший путь длины k. Решение с возведением матрицы в степень.
  3. Битовые операции
    1. Посмотреть i-й бит, присвоить i-й бит, обнулить i-й бит, множество всех элементов.
    2. Пересечение, объединение, разность. Проверка, содержится ли.
    3. Старший бит, младший бит.
  4. Динамика по подмножествам
    1. Сумма на подмножестве, количество бит в числе, старший бит, младший бит, перевернутая битовая запись.
    2. Для каждого множества посчить количество независимых подмножеств за O(2n).
    3. Гамильтонов путь за O(2nn2) времени, за O(2nn) времени.
    4. Гамильтонов путь за O(2nn) времени.
    5. Перебор всех подмножеств, надмножеств. Раскраска графа в минимальное количество цветов за O(3n).
    6. Решение мультирюкзака (унести все вещи минимальным числом подходов) за O(3n).
  5. Динамика по скошенному профилю
    1. Перебор + запоминание хеш-таблицей + полиномиальный хеш
    2. Прямое написание за O(2min(w,h)wh) времени и O(2min(w,h)) памяти
    3. Бонус хеш-таблицы: хранятся только достижимые состояния (ленивость). Бонус рекурсии: удобно пересчитывать состояние.
    4. Динамика по профилю по графу (обойдем поиском в ширину, в таком порядке запустим перебор с запоминанием)
Если останется время:
  1. Задача про погрузку грузов (можно брать вещи с двух концов последовательности, в ящик помещается W, минимизировать кол-во ящиков)
    1. Пример 2 3 4 5 6 7, W = 9 : 2+3+4 = Wrong Way, 2+7, 3+6, 4+5 = 3 ящика
    2. Решение за O(n4) f[L, R] → [a, b]
    3. Решение за O(n3) f[L, R] → [a, b], где b = min возможный (два указателя)
    4. Измельчаем переход [a,b,f,w], динамики с is[a,b,f,w], w[a,b,f], f[a,b,w]
    5. Динамика за квадрат времени: pair(f, w) [a,b]
    6. Оптимизация памяти до линии
    7. Фукнция: можно считать расстояние от начальной вершины до текущей, можно расстояние от текущей до конечной (смотрим, что изменится)
    8. Функция: можно делать пересчет вперед и назад, можно лениво (смотрим, что изменится)