Бонусные лекции

  1. convex hull trick + Лямбда-оптимизация
    1. CHT
      1. Задача про квадраты и сумму площадей, решение динамикой за O(n2)
      2. Раскрываем переход, видим добавляющиеся отсортированные по углу прямые, верхнюю огибающую
      3. Добавление прямой: стек, поиск maxY(x) = бинпоиск или второй указатель
    2. Лямбда-оптимизация
      1. Задача, алгоритм. Хотим ровно k квадратов. Имеем только f = maxk f(k), но можём f' = maxk (f(k) + λ k), бинпоиск по λ
      2. Выпуклая f(k). Касательные. Корректность.
      3. Источники выпуклых функций: всё, что сводится к паросочетанию или mincost потоку.
  2. Динамика по сложному состоянию
    1. Юнг
    2. Изоморфизм деревьев
      1. map : vector → int
      2. хеши → бор → за O(n) без хешей
    3. Динамика по профилю, изломаному профилю: доминошки и рекурсия (будет на общей лекции!)
    4. Жуткому профилю: дедекаэдр, грид-тор, кубик с гранями-гридами... Построим граф =)

  3. Формула включения-исключения
    1. Посчитать кол-во чисел от 1 до 109
      1. Которые не делятся ни на одно из p1, p2, ... pn
      2. Которые не делятся ни на одно из a1, a2, ... an
      3. Взаимнопросты с m
    2. Посчитать число путей из (1,1) в (n,n) вправо-вверх (n ≤ 109), не проходящих ни через одну из заданных клеток (xi,yi)
    3. Заданы числа n ≤ 1012 и k ≤ 100, сколько множеств из k чисел имеют lcm = n? neerc
    4. Мёбиус: количество подпоследовательностей с НОД=1 cf
    5. Суммы в подмножествах
      1. Как посчитать для каждого подмножества сумму по всем его подмножествам? (ДП)
      2. Обратная задача: как по суммам в подмножествах посчитать исходных значения? (ФВИ, или чуть поменять ДП)
    6. Количество беспорядков (перестановок без pi = i)
    7. Цэшки: количество матриц 250*250, в которых в каждой строке/столбце min=1 cf
  4. NP-трудное
    1. Покраска за 2n без восстановления ответа
    2. Количество гамильтоновых путей за 2nnm и полином памяти
  5. Бонус: число неприводимых многочленов степени n над Fp (мёбиус)