Четвертая лекция

1. Динамика
1. Как удобно писать динамику по дереву (см. задачу из контеста)
1. Состояние вместо [v,i] кодируем, как [x], где x = next[v,i]
2. Восстановление ответа
2. Время работы динамики по дереву
1. На практике любое дерево можно сделать бинарным (рисуем биекцию)
2. На практике бывает только два крайних случая: полное бинарное дерево, линия
3. Задача: для каждого i=1..n посчитать количество способов вырезать поддерево размера i
4. T(n) = T(x) + T(n - x - 1) + x * (n-x-1) → O(n²)
5. Задача: для каждого i=1..k посчитать количество способов вырезать поддерево размера i
6. T(n) = T(x) + T(n - x - 1) + min(k, x) * min(k, n-x-1) → O(nk)
3. Задачка от Кнута за O(n²): даны n точек на прямой, выбрать k точек-центров так, чтобы сумма расстояний до ближайшего цетра была минимальна
4. Задачка про командный пункт O(n²logn): на окружности n точек, выбрать k так, чтобы площадь многоугольника была максимальна.
1. Решение за O(n³k) --- перебираем, где разрезали, динамика по состоянию [n,k], переход за линию
2. Улучшаем решение до O(n³) --- перебираем только O(n/k) разрезов
3. Другое улучшение того же решения: при переходе как-нибудь воспользоваться методом двух указателей, получаем O(n³)
4. Какие бывают методы двух указателей? Пусть даны и p[n,k] f[n,k]
1. f[n,k] монотонна, тогда бинпоиск
2. f[n,k] монотонна, p[n,k] монотонна, тогда классический метод двух указателей
3. p[n,k] монотонна, тогда перебираем в соответствующем диапазоне p[n-1,k] ≤ p[n,k] ≤ p[n,k+1] и получаем суммарное время O(n²)
5. Мерджим два улучшения, получаем O(n³/k)
6. Другая идея, состояние = [l,r,k]. Изначально решение работает за O(n³k).
7. Первое улучшение: k → k/2. Теперь O(n³logk).
8. Второе улучшение: метод двух указателей при пересчете. Теперь O(n²logk). Успех.
2. Тактика на контесте?
1. Тут была пачка жизненных примеров...
3. Геометрия (метод двух указателей, scanline, многоугольники, локализация)?