Лекция dfs, DP, 2 указателя

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