[4]

1. [games] Привести пример выигрышной игры $G$, такой что $G \oplus G$ не проигрышная.
2. [games] O-MAX: нужно в многоугольнике проводить диагонали... непересекающиеся. Кто не может ходить, тот проиграл.
3. [data structures, treap] Перевернуть отрезок строки, проверить совпадает ли подстрока с заданным словом. Усложнение: проверить, совпадают ли отрезки строки [a..b] и [c..d].
4a. [flow] Найти в неорграфе любой вершинно простой путь из $a$ в $b$, проходящий через $c$. 
4b. [flow, NP-hard] Доказать, что предыдущая задача NP-сложная для ориентированного графа (можно использовать сведение к задаче про два пути).
5. [mincost flow] Найти в неорграфе кратчайший ребрно простой путь из $a$ в $b$ через $c$. 
6. [flow] У всех ребер в неор графе есть веса. Нужно найти разрез минимального веса (можно усложнить, сказать, что веса вещественные, или, что разрез глобальный).
7. [flow] Привести пример, в котором имеет место следующая ситуация, либо докажите, что такого не может быть.
     В графе $G$ с помощью (а) метода Форда-Фалкерсона (б) алгоритма Эдмондса-Карпа был найден поток $F$.
     Затем поток $F$ декомпозировали, и результат чего явились не только пути из $s$ в $t$, но и циклы.
8. [matching] Дан двудольный граф, в котором каждая вершина имеет степень $k$.
     Представить множество ребер графа как объединение $k$ полных паросочетаний. $O(k^2V^2)$.
9a. [strings, hashes] Число подпалиндромов за O(nlogn)
9b. [strings, hashes] Максимальный подпалиндром за O(nlogn)
9c. [strings, hashes] Самый длинный общий подпалиндром за O(nlogn)
10. [strings, sufftrees] Найти самую длинную строку, которая встречается как подстрока хотя бы k раз за O(n)
11. [data structures, segment tree] Запрос: знакопеременная сумма на отрезке. Массив можно менять в точке (усложнение: на отрезке)
12. [data structures, segment tree] Painter: покрасить отрезок в цвет C, вывести суммарную длину и количество отрезков цвета 0.
13a. [strings] Предложите метод сортировки строк над константным алфавитом (например, размера 4) за O(n): решение бором
13b. [strings] Предложите метод сортировки строк над константным алфавитом (например, размера 4) за O(n): решение цифровой сортировкой
13c. [strings] Доказать, что если алфавит произвольный, быстрее O(nlogn) не получится
14. [lca] Дано дерево. В вершинах числа. Запрос: за O(1) посчитать сумму на пути в дереве.
15. [scanline, persistent] Дан Scanline, который в Offline считает количество точек в прямоугольнике. Сделать из него Online с помощью persistent segment tree.

[5]

1. [lca, двоичный подъемы] Поиск LCA в лесу, за $O(log^2n)$ в Online с дополнительной операцией: подвесить корень одного дерева к вершине другого дерева.
2. [lca, двоичный подъемы] Поиск LCA в лесу, за $O(logn)$ в Offline с дополнительной операцией: подвесить корень одного дерева к вершине другого дерева.
3. [LR-flow] Округление матрицы. Дана вещественная матрица. Нужно округлить каждое число вверх или вниз так, чтобы суммы в строках и столбцах тоже округлились.
4. [matching, cover] Дан орграф. Можно за a_i все ребра, входящие в вершину i, за b_i удалить все ребра, исходящие из i. Удалить весь граф за минимальную стоимость.
5. [mincost flow] За O(VE) найти в двудольном графе с весами w_{ij} = a_i + b_j паросочетание минимального веса.
6. [mincost flow] Есть k автоматов. Выполнить i-й заказ = занять один из автоматов на время [L_i..R_i]. Нужно выполнить заказы максимальной суммарной стоимости.
7. [strings, sufftrees] Даны 2 строки длины n. Найти самый длинный общий подпалиндром за O(n).
8. [strings, sufftrees] Даны 2 строки длины n и число k. Найти k-ю лексикографически общую подстроку за O(n).
9. [data structures, segment tree] Даны результаты запросов min(l,r). Восстановите исходный массив. O(nlogn).
10. [data structures, lca] На дереве искать минимум на пути и менять значение в вершине. Online. Быстрее чем за O(n).
11. [data structures] Дано дерево. Запрос (v, x): "количество вершин со значением <= x в поддереве вершны v". O(log^2n) в online. O(nlogn) в offline.
12. [greedy] Чтобы взять человека в партию, нужен авторитет хотя бы a_i, после взятия человека авторитет меняется на b_i. Числа b_i могут быть отрицательны. Нужно взять как можно больше людей. (acmp.572, старый питерский ЧФ)
13. [mincost flow] evacuate: Дан поток размера k. Улучшить его стоимость за O(VE).
14. [flow] Дана матрица. Представить ее в виде суммы перестановочных матриц (в каждой строке, каждом столбце ровно один элемент).

[5+]

1. [data structures, persistent] k-я порядковая статистика на отрезке за O(logn) в Online.
2. [matchings] максимальная антицепь (теорема Дилворта). Дан транзитивно замкнутый ацикличный орграф, найти максимальное независимое множество.
3. [data structures, lca-rmq] запросы в дереве: сумма весов ребер на пути, изменить вес ребра. Решение в Online за O(logn).
4. [data structures, lca] В вершинах дерева записаны числа. Найти для каждой вершины число различных чисел в поддереве. O(nlogn). Более сложная версия: O(n).
5. [strings] Найти строку, которая валит полиномиальный хеш для фиксированных коэффициента домножения и простого модуля до 10^{18}.
6. [euler paths, treap] Добавляются и удаляются ребра. В каждый момент времени граф -- лес. Нужно Online за O(logn) отвечать на запрос, есть ли путь между a и b.
7. [greedy] Даны n <= 10^4 машинок, i-ю нужно a_i обрабатывать на первом автомате, b_i на втором. Обработка -- непрерываемый процесс. Порядок машин и порядок применения автоматов не важен. Минимизировать время завершения.
8. [cut] Матан: выбрать множество вершин, что в них не входят ребра, при этом сумма чисел в вершинах максимальна.
9. [cut] Hard-life: выбрать множество вершин такое, что |E|/|V| --> max