Динамика. Часть 2. (14 октября 2016)

1. Задачи на подотрезках
1. Folding: запаковать строку timus : 1238 за O(n³)
1. Решаем за O(n⁴)
2. Решаем за O(n³ log n) − догадались перебирать только делители
3. Решаем за O(n³) − догадались предподчитать динамику LCP[i,j] за O(n²)
2. Взвешенный бинпоиск за O(n³) (стоимость обращения к элементу i равна cost[i]; минимизируем худший случай при условии, что выбираем произвольный элемент)
3. Покраска забора painter (дан массив цветов − что должно получиться, один ход − покрасить отрезок, минимизировать число ходов)
1. За O(n³k). f[i,j,color]. n − длина массива, k − число различных цветов.
2. Сперва делаем лениво. Показываем, как сделать честный O(n³) (цвет равен color[l-1]).
2. [skipped] Задача take про 2D возрастающую подпоследовательность (из контеста)
1. [skipped] Решение за O(n³) номер 1: min_end[i, j, length]
2. [skipped] Решение за O(n³) номер 2: перебираем клетки [i, j] в порядке возрастания a[i, j], и считаем минимум на [0..i] × [0..j] за O(n)

1. Динамика по подмножествам
1. Множества, хранение, операции: &, |, ^, (1 << i), (x >> i) & 1
2. Для каждого числа от 0 до (2^k)-1 за O(2^k) посчитать количество бит в нём (размер каждого подмножества)
3. Для каждого числа от 0 до (2^k)-1 за O(2^k) посчитать старший бит в нём
4. Для каждого подмножества множества за O(2^k) посчитать сумму элементов в нём (кодим эту задачу)
5. Для каждого множества вершин в графе за O(2^k) проверить, независимое ли оно
2. Гамильтоновость
1. Задача о гамильтоновом пути. Решение за O(2ⁿn²).
2. Задача о гамильтоновом пути. Решение за O(2ⁿn).
3. Задача о гамильтоновом цикле.
4. Задача коммивояжёра.
3. [skipped] Динамика по скошенному (изломанному) профилю. Рекурсивный вариант на примере "количества покрытий доминошками".