Теоретическая практика для 111-й группы

1. Скобочные последовательности: изменить последовательность из двух типов скобок до правильной добавлением мин числа скобок за O(N³).
1. изменить = можно в любые места вставлять
2. изменить = можно в любые места вставлять, из любых мест удалять, любую скобку заменять на другую.
2. Следующий объект: билет из 2N цифр называется счастливым, если в нем одинаковая сумма первых и последних N цифр. Дано число длины 2N - найти ближайшие снизу и сверху счастливые билеты
3. Взяли числа от 1 до N, отсортировали лексикографически, как строки, число x получило номер p. Даны x и p, нужно восстановить минимально возможное N. O(log³N)
4. Найти число с max числом делителей от 1 до N за o(N) (с доказательством времени работы)
5. Дана матрица из черных, белых, серых клеток. Серые могут стать черными или белыми по вашему желанию. Сказать, можно сделать из матрицы кусок шахматной доски с квадратными клетками. O(N³).
6. Найти max паросочетание в произвольном графе за O(N*2^N)
7. Дан массив. Посчитать число возрастающих подпоследовательностей в нем за O(N²).
1. Число возрастающих (для 1, 1, 1, 1 ответ 4)
2. Число ралличных возрастающих (для 1, 1, 1, 1 ответ 1)
8. Даны N точек. Нужно выбрать 3, образующие треугольник max площади за O(N²).

Практика

1. Про скобочные последовательности (b)
2. Про паросочетание