Практический минимум. Разбор.
- "A", "Малыш и Карлсон", "karlsson" - Функция Гранди
- "B", "Две кучки", "heaps" - Динамика (двумерная)
- "C", "Одна кучка", "heaps2" - Динамика (одномерная)
- "D", "Комфортабельная рассадка", "comfort" - Простая задача на Функцию Гранди
- "E", "Компоненты связности", "connect" - wiki dfs
- "F", "Флойд", "floyd" - wiki floyd
- "G", "Функция", "function" - Рекурсия с запоминанием
- "H", "Покрытие доминошками" - Полный перебор
- "I", "Расстояние в графе", "bfsrev" - wiki bfs
- "J", "Улиточки", "snails" - Поток # т.е. нужно написать dfs)
- "K", "Ёжики", "hedgehog" - Перебор всех подмножеств
- "L", "Pairs. Паросочетание", "pairs" - Паросочетание # т.е. снова нужно написать dfs)
- "M", "Сумма простая", "sum0" - Частичные суммы на префиксах
- "N", "Сумма", "sum" - Дерево отрезков
- "O", "Points on the plane", "fenwick" - Двумерное дерево Фенвика
- "P", "Общий предок", "lca" - Двоичный подъем
- "Q", "Самое дешевое ребро", "minonpath" - Двоичный подъем еще раз
- "R", "Сравнения подстрок", "substrcmp" - Посчитать Хэш подстроки за O(1)
- "S", "Словарь", "dictionary" - Сложить все строки в Бор
- "T", "Суффиксный массив", "suffarray" - Просто запустить функцию sort
- "U", "Простые числа", "primes" - Решето Эратосфена
- "V", "LCP для суффиксного массива", "sufflcp" - Посчитать LCP (можно за O(n), можно хэшами с бинпоиском)
- "W", "Глобальный разрез", "stor" - Реализовать алгшоритм Штор-Вагнера (что-то очень похожее на алгоритм Дейкстры)
- "X", "Такси", "taxi" - Свести задачу к паросочетанию в двудольном графе
- "Y", "Bridges. Мосты", "bridges" - Написать dfs + 1 if
- "ZA", "TopSort. Топологическая сортировка", "topsort" - И вновь нужно написать dfs
- "ZB", "Chip Installation", "chip" - 2-SAT
- "ZC", "Грани планарного графа", "theuler" - Воспользоваться Теоремой Эйлера
- "ZD", "Гамильтонов цикл в полном графе", "fullham" - =)