$ dfs, DP, 2 указателя (18 ноября 2014)

# De Bruijn sequence
## Напоминаем определения: гамильтонов цикл, Эйлеров цикл
## Задача #1: построить цикл на всех строках длины n над алфавитом k.
## Задача #2: построить цикл на всех строках длины n над алфавитом k, в которых четное число нулей.
# Задача про ориентацию графа: ориентировать граф так, чтобы максимальная исходящая степень была минимальна.
## Решение: ориентируем как-нибудь + метод локальных оптимизаций
## Другая идея: бинарный поиск по ответу.
## Оценка времени работы решения с бинарным поиском по ответу: O(E^2logD) (logD = BS, dfs = O(E), E -- максимальное число итераций)
## Доказательство корректности: если нет пути из вершины степени больше D в вершину степени меньше D, то ответ хотя бы D.
# Метод двух указателей:
## Задача про профессора и яйца, решние за O(nlogn)
### Состояние: [n,k], k ≤ logn. Переход: разделение отрезка на два.
## Даны m запросов "Количество различных чисел на отрезке [L_i,R_i]". Offline задача.
### Пусть L_i и R_i не убывают, решение за O(n) операций с хеш-таблицей.
### Пусть теперь L_i и R_i произвольны, решение за O(nlogn) + O(n^{3/2}) (без рандомизации).
### Переход методом двух указателей: f[n+1,k] ≥ f[n,k]. Максимум двух функций. Поиск p[n,k] циклом while.
## Задача про выбор двух точек на прямой, решение за O(nlogn)
### Сортируем точки. pos[n] ↑ (самая левая точка такая, что сумма слева ≥ суммы справа)
### Перебираем разделитель. Для суффикса и префикса знаем оптимум. Частичные суммы.
## Задача про k точек на прямой
### Решение за O(n^2k) с предподсчетом всего, что нужно.
### Решение за O(n^2). Само решение -- перебирать p[n,k] от p[n,k+1] до p[n+1,k]. Доказательство времени работы ∑ (p[n+1,k]-p[n,k+1]) = O(n^2).
### Корректность решения
#### f[n,k] ≤ f[n+1,k], f[n,k-1]. Граница отрезка и центр отрезка монотонно зависят друг от друга.
#### p[n+1,k] ≥ p[n,k] (возьмем решение [n,k], последний отрезок удлиним, перейдем к оптимальному [n+1,k], последний отрезок укоротим, заметим: последнее уменьшени меньше первого увеличения).
#### p[n,k-1] ≥ p[n,k] (для k=2 можем найти оптимальную границу циклом while: двигать, пока сумма слева меньше. для k=3 противоречие строится так: A,B,C и D,E границу B,C было двигать не выгодно, значит, граница D,E не дальше границы B,C т.к. сумма слева только увеличилась)