Competitive Programmer's Handbook (2018) [pdf]
Книга «Competitive Programmer’s Handbook» Антти Лааксонена — это практическое руководство по алгоритмам и структурам данных, ориентированное на подготовку к программным соревнованиям. Оно охватывает основные темы: сложность алгоритмов, сортировку, поиск, динамические массивы, множества, словари, итераторы, полный перебор, жадные алгоритмы и динамическое программирование. Особое внимание уделяется реализации на C++ и эффективному написанию кода под ограничениями времени и памяти.
В разделе о сложности алгоритмов объясняются правила оценки времени работы, классы сложности (O, Ω, Θ) и методы оценки эффективности. Приводятся примеры, такие как максимальная сумма подмассива (алгоритм Кадане), демонстрирующие линейные решения. В части про сортировку рассматриваются теоретические основы, реализация в C++ через std::sort и применение бинарного поиска. Описываются структуры данных: векторы, множества (set, multiset), словари (map, multimap), их итераторы и практическое использование.
Раздел о полном переборе включает генерацию подмножеств, перестановок и использование backtracking с эвристиками обрезки поиска. Метод «встреча посередине» представлен как способ снизить экспоненциальную сложность до приемлемой для задач с n ≈ 40. Жадные алгоритмы иллюстрируются на примерах монетной задачи, планирования задач и минимизации сумм, с акцентом на условия, при которых жадность оптимальна. Динамическое программирование раскрывается через классические задачи: монеты, наибольшая возрастающая подпоследовательность, пути в сетке и рюкзак, с акцентом на определение состояний и переходов. В приложении даны ссылки на ключевые исследования и ресурсы, включая работы по алгоритмам Прима, Шарара и Тарьяна, а также полезные платформы вроде USACO и Szkopuł.