Количество простых чисел

1. π(10¹²) = ?
2. f(N, d) --- количество чисел от 1 до N, у которых все делители ≥ d
3. Ans = f(N, √N) + π(√N)
4. f(N, d) = f(N, d - 1) - f(N / d, d)
5. Отсечение 1: f(N, d) предподсчитано, если N ≤ 10⁶
6. Отсечение 2: f(N, d) = 0, если d > N
7. Отсечение 3: f(N, 1) = N, f(N, k) можно узнать бинпоиском по массиву всех таких чисел для малых k.
8. Оценка времени работы:

Алгоритмы сжатия

1. LZSS за O(N²)
2. LZSS за O(NlogN)
3. LZW за O(N)

Нестандартное дерево с перебаллансировкой

1. BST. Док-во того, что логарифм.
2. Одномерное дерево отрезков с вставкой в середину
3. 2D дерево отрезков с добавлением точки

Потоки

1. Теория. Введение.
2. Алгоритм: max Flow, min Cut
3. Связь с паросочетанием в двудольном графе: max Matching, min Cover
4. Быстрый алгоритм поиска: Scaling^* за O(E²)

Задачи на потоки.

1. Удаление графа
2. Восстановление матрицы по суммам в сторках и столбцах
3. Покрытие грида с дырками доминошками
4. Покраска регулярного графа (случай k = 2^s, случай произвольного k = Д.З)
5. Замощение грида минимальным числом палок 1xN