Олимпиадное программирование: изучение и улучшение алгоритмов на соревнованиях

Олимпиадное программирование_обложка Олимпиадное программирование_165_235_макет От автора Вступительное слово Алексея Малеева, основателя Moscow Workshops ICPC Отзыв Дмитрия Гришина, основателя Mail.Ru Group Благодарность от редакции Отзыв Нияза Нигматуллина, двукратного чемпиона мира ACM ICPC 2012 и 2013 годов Предисловие Глава 1 Введение 1.1. Что такое олимпиадное программирование? 1.1.1. Соревнования по программированию 1.1.2. Рекомендации желающим поучаствовать 1.2. Об этой книге 1.3. Сборник задач CSES 1.4. Другие ресурсы Глава 2 Техника программирования 2.1. Языковые средства 2.1.1. Ввод и вывод 2.1.2. Работа с числами 2.1.3. Сокращение кода 2.2. Рекурсивные алгоритмы 2.2.1. Порождение подмножеств 2.2.2. Порождение перестановок 2.2.3. Перебор с возвратом 2.3. Поразрядные операции 2.3.1. Поразрядные операции 2.3.2. Представление множеств Глава 3 Эффективность 3.1. Временная сложность 3.1.1. Правила вычисления 3.1.2. Часто встречающиеся оценки временной сложности 3.1.3. Оценка эффективности 3.1.4. Формальные определения 3.2. Примеры 3.2.1. Максимальная сумма подмассивов 3.2.2. Задача о двух ферзях Глава 4 Сортировка и поиск 4.1. Алгоритмы сортировки 4.1.1. Пузырьковая сортировка 4.1.2. Сортировка слиянием 4.1.3. Нижняя граница временной сложности сортировки 4.1.4. Сортировка подсчетом 4.1.5. Сортировка на практике 4.2. Решение задач с применением сортировки 4.2.1. Алгоритмы заметающей прямой 4.2.2. Составление расписания 4.2.3. Работы и сроки исполнения 4.3. Двоичный поиск 4.3.1. Реализация поиска 4.3.2. Нахождение оптимальных решений Глава 5 Структуры данных 5.1. Динамические массивы 5.1.1. Векторы 5.1.2. Итераторы и диапазоны 5.1.3. Другие структуры данных 5.2. Множества 5.2.1. Множества и мультимножества 5.2.2. Отображения 5.2.3. Очереди с приоритетом 5.2.4. Множества, основанные на политиках 5.3. Эксперименты 5.3.1. Сравнение множества и сортировки 5.3.2. Сравнение отображения и массива 5.3.3. Сравнение очереди с приоритетом и мультимножества Глава 6 Динамическое программирование 6.1. Основные понятия 6.1.1. Когда жадный алгоритм не работает 6.1.2. Нахождение оптимального решения 6.1.3. Подсчет решений 6.2. Другие примеры 6.2.1. Наибольшая возрастающая подпоследовательность 6.2.2. Пути на сетке 6.2.3. Задачи о рюкзаке 6.2.4. От перестановок к подмножествам 6.2.5. Подсчет количества замощений Глава 7 Алгоритмы на графах 7.1. Основы теории графов 7.1.1.Терминология 7.1.2. Представление графа 7.2. Обход графа 7.2.1. Поиск в глубину 7.2.2. Поиск в ширину 7.2.3. Применения 7.3. Кратчайшие пути 7.3.1. Алгоритм Беллмана–Форда 7.3.2. Алгоритм Дейкстры 7.3.3. Алгоритм Флойда–Уоршелла 7.4. Ориентированные ациклические графы 7.4.1. Топологическая сортировка 7.4.2. Динамическое программирование 7.5. Графы преемников 7.5.1. Нахождение преемников 7.5.2. Обнаружение циклов 7.6. Минимальные остовные деревья 7.6.1. Алгоритм Краскала 7.6.2. Система непересекающихся множеств 7.6.3. Алгоритм Прима Глава 8 Избранные вопросы проектирования алгоритмов 8.1. Алгоритмы с параллельным просмотром разрядов 8.1.1. Расстояние Хэмминга 8.1.2. Подсчет подсеток 8.1.3. Достижимость в графах 8.2. Амортизационный анализ 8.2.1. Метод двух указателей 8.2.2. Ближайшие меньшие элементы 8.2.3. Минимум в скользящем окне 8.3. Нахождение минимальных значений 8.3.1. Троичный поиск 8.3.2. Выпуклые функции 8.3.3. Минимизация сумм Глава 9 Запросы по диапазону 9.1. Запросы к статическим массивам 9.1.1. Запросы о сумме 9.1.2. Запросы о минимуме 9.2. Древовидные структуры 9.2.1. Двоичные индексные деревья 9.2.2. Деревья отрезков 9.2.3. Дополнительные приемы Глава 10 Алгоритмы на деревьях 10.1. Базовые понятия 10.1.1. Обход дерева 10.1.2. Вычисление диаметра 10.1.3. Все максимальные пути 10.2. Запросы к деревьям 10.2.1. Нахождение предков 10.2.2. Поддеревья и пути 10.2.3. Наименьшие общие предки 10.2.4. Объединение структур данных 10.3. Более сложные приемы 10.3.1. Центроидная декомпозиция 10.3.2. Разновесная декомпозиция Глава 11 Математика 11.1. Теория чисел 11.1.1. Простые числа и разложение на простые множители 11.1.2. Решето Эратосфена 11.1.3. Алгоритм Евклида 11.1.4. Возведение в степень по модулю 11.1.5. Теорема Эйлера 11.1.6. Решение уравнений в целых числах 11.2. Комбинаторика 11.2.1. Биномиальные коэффициенты 11.2.2. Числа Каталана 11.2.3. Включение-исключение 11.2.4. Лемма Бёрнсайда 11.2.5. Теорема Кэли 11.3. Матрицы 11.3.1. Операции над матрицами 11.3.2. Линейные рекуррентные соотношения 11.3.3. Графы и матрицы 11.3.4. Метод исключения Гаусса 11.4. Вероятность 11.4.1. Операции с событиями 11.4.2. Случайные величины 11.4.3. Марковские цепи 11.4.4. Рандомизированные алгоритмы 11.5. Теория игр 11.5.1. Состояния игры 11.5.2. Игра ним 11.5.3. Теорема Шпрага–Гранди Глава 12 Дополнительные алгоритмы на графах 12.1. Сильная связность 12.1.1. Алгоритм Косарайю 12.1.2. Задача 2-выполнимости 12.2. Полные пути 12.2.1. Эйлеровы пути 12.2.2. Гамильтоновы пути 12.2.3. Применения 12.3. Максимальные потоки 12.3.1. Алгоритм Форда–Фалкерсона 12.3.2. Непересекающиеся пути 12.3.3. Максимальные паросочетания 12.3.4. Покрытие путями 12.4. Деревья поиска в глубину 12.4.1. Двусвязность 12.4.2. Эйлеровы подграфы Глава 13 Геометрия 13.1. Технические средства в геометрии 13.1.1. Комплексные числа 13.1.2. Точки и прямые 13.1.3. Площадь многоугольника 13.1.4. Метрики 13.2. Алгоритмы на основе заметающей прямой 13.2.1. Точки пересечения 13.2.2. Задача о ближайшей паре точек 13.2.3. Задача о выпуклой оболочке Глава 14 Алгоритмы работы со строками 14.1. Базовые методы 14.1.1. Префиксное дерево 14.1.2. Динамическое программирование 14.2. Хеширование строк 14.2.1. Полиномиальное хеширование 14.2.2. Применения 14.2.3. Коллизии и параметры 14.3. Z-алгоритм 14.3.1. Построение Z-массива 14.3.2. Применения 14.4. Суффиксные массивы 14.4.1. Метод удвоения префикса 14.4.2. Поиск образцов 14.4.3. LCP-массивы Глава 15 Дополнительные темы 15.1. Квадратный корень в алгоритмах 15.1.1. Структуры данных 15.1.2. Подалгоритмы 15.1.3. Целые разбиения 15.1.4. Алгоритм Мо 15.2. И снова о деревьях отрезков 15.2.1. Ленивое распространение 15.2.2. Динамические деревья 15.2.3. Структуры данных в вершинах 15.2.4. Двумерные деревья 15.3. Дучи 15.3.1. Разбиение и слияние 15.3.2. Реализация 15.3.3. Дополнительные методы 15.4. Оптимизация динамического программирования 15.4.1. Трюк с выпуклой оболочкой 15.4.2. Оптимизация методом «разделяй и властвуй» 15.4.3. Оптимизация Кнута 15.5. Разное 15.5.1. Встреча в середине 15.5.2. Подсчет подмножеств 15.5.3. Параллельный двоичный поиск 15.5.4. Динамическая связность Приложение Сведения из математики Формулы сумм Множества Математическая логика Функции Логарифмы Системы счисления Библиография Предметный указатель This invaluable textbook presents a comprehensive introduction to modern competitive programming. The text highlights how competitive programming has proven to be an excellent way to learn algorithms, by encouraging the design of algorithms that actually work, stimulating the improvement of programming and debugging skills, and reinforcing the type of thinking required to solve problems in a competitive setting. The book contains many "folklore" algorithm design tricks that are known by experienced competitive programmers, yet which have previously only been formally discussed in online forums and blog posts. Topics and features: Reviews the features of the C++ programming language, and describes how to create efficient algorithms that can quickly process large data sets Discusses sorting algorithms and binary search, and examines a selection of data structures of the C++ standard library Introduces the algorithm design technique of dynamic programming, and investigates elementary graph algorithms Covers such advanced algorithm design topics as bit-parallelism and amortized analysis, and presents a focus on efficiently processing array range queries Surveys specialized algorithms for trees, and discusses the mathematical topics that are relevant in competitive programming Examines advanced graph techniques, geometric algorithms, and string techniques Describes a selection of more advanced topics, including square root algorithms and dynamic programming optimization This easy-to-follow guide is an ideal reference for all students wishing to learn algorithms, and practice for programming contests. Knowledge of the basics of programming is assumed, but previous background in algorithm design or programming contests is not necessary. Due to the broad range of topics covered at various levels of difficulty, this book is suitable for both beginners and more experienced readers. Dr. Antti Laaksonen has worked as a teacher and researcher at the University of Helsinki and Aalto University, Finland. He has served as one of the organizers of the Finnish Olympiad in Informatics since 2008, and as the Scientific Chair of the Baltic Olympiad in Informatics in 2016. He has also coached and led the Finnish team at several international programming contests, including the International Olympiad in Informatics 2009-2016, and has established experience in teaching programming and algorithms