12. Комбинаторика и теория вероятностей
Числа Каталана, сочетания, размещения, принцип включений-исключений, формула условной вероятности и полной15. Полиномиальное хеширование
Хеширование для строк, получение хеша подстроки, реверснутой строки, циклически сдвинутой16. Полиномиальное хеширование. Продолжение
Двойное хеширование, мотивация, разбор задач на полиномиальное хеширование
17. Префикс функция
Префикс функция, алгоритм Кнута-Морисса-Пратта, решение базовых задач на префикс функцию18. z-функция
z-функция, алгоритм Манакера, поиск кол-ва различных подстрок, подполиндромов
19. Строковые структуры данных
Бор, использование бора для быстрого поиска строки, подстроки, сортировки строк, цифровой бор
20. Строковые структуры данных. Продолжение
Суффиксный массив, longest common prefix21. Проведение контеста + разбор
Пишем пробное соревнование в формате реальной олимпиады, разбираем задачи
22. Введение
DFS, BFS, основные свойств, поиск циклов, компонент связности23. Продолжение изучения основ
Поиск компонент сильной связности, мостов и точек сочленения, топологическая сортировка
24. Нахождение кратчайших путей
Алгоритм Дейкстры25. Нахождение кратчайших путей. Продолжение
Форд-Беллмана, Флойд-Уоршелла (+ дп на поддеревьях)26. СНМ
Система непересекающихся множеств, эвристики (сжатие путей, весовая)
27. Минимальный остов
Поиск минимальных остовных деревьев (алгоритмы Прима и Краскала)
28. Проведение контеста + разбор
Пишем пробное соревнование в формате реальной олимпиады, разбираем задачи