Спортивное программирование

Стивен Халим, Феликс Халим

Спортивное программирование

Competitive  
Programming 3

The New Lower Bound of Programming Contests

Steven Halim, Felix Halim

Спортивное  
программирование

Новый нижний предел соревнований по программированию

Стивен Халим, Феликс Халим

Москва, 2020

УДК 004.02, 004.424
ББК 22.18
Х17

Халим С., Халим Ф.
Х17 
Спортивное программирование / пер. с англ. Н. Б. Желновой, А. В. Снастина. – М.: ДМК Пресс, 2020. – 604 с.: ил. 

ISBN 978-5-97060-758-9

Книга содержит задачи по программированию, аналогичные тем, которые 
используются на соревнованиях мирового уровня (в частности, ACM ICPC и IOI). 
Помимо задач разного типа приводятся общие рекомендации для подготовки 
к соревнованиям, касающиеся классификации заданий, анализа алгоритмов и пр. 
Кроме стандартных тем (структуры данных и библиотеки, графы, математика, 
вычислительная геометрия) авторы затрагивают и малораспространенные – им 
посвящена отдельная глава.
В конце каждой главы приводятся краткие решения заданий, не помеченных 
звездочкой, или даются подсказки к ним. Задания сложного уровня (помеченные 
звездочкой) требуют самостоятельной проработки.
Издание адресовано читателям, которые готовятся к соревнованиям по программированию или просто любят решать задачи по информатике. Для изучения 
материала требуются элементарные знания из области методологии программирования и знакомство хотя бы с одним из двух языков программирования –  
C/C++ или Java.

УДК 004.02, 004.424
ББК 22.18

Russian­language edition copyright © 2020 by DMK Press. All rights reserved.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав.

 
© Steven Halim, Felix Halim, 2013
ISBN 978­5­97060­758­9 (рус.) 
©  Оформление, издание, перевод, 
ДМК Пресс, 2020

Содержание

Вступление ................................................................................................................... 11

Предисловие ............................................................................................................... 13

От издательства ......................................................................................................... 27

Об авторах этой книги .......................................................................................... 28

Список сокращений ................................................................................................ 30

Глава 1. Введение ..................................................................................................... 32

1.1. Олимпиадное программирование ....................................................................... 32
1.2. Как стать конкурентоспособным ......................................................................... 35
1.2.1. Совет 1: печатайте быстрее! .......................................................................... 36
1.2.2. Совет 2: быстро классифицируйте задачи ................................................. 37
1.2.3. Совет 3: проводите анализ алгоритмов ...................................................... 40
1.2.4. Совет 4: совершенствуйте свои знания языков  
программирования .................................................................................................... 46
1.2.5. Совет 5: овладейте искусством тестирования кода ................................. 48
1.2.6. Совет 6: практикуйтесь и еще раз практикуйтесь! .................................. 52
1.2.7. Совет 7: организуйте командную работу (для ICPC) ............................... 53
1.3. Начинаем работу: простые задачи ...................................................................... 54
1.3.1. Общий анализ олимпиадной задачи по программированию .............. 54
1.3.2. Типичные процедуры ввода/вывода ........................................................... 55
1.3.3. Начинаем решать задачи ............................................................................... 57
1.4. Задачи Ad Hoc ........................................................................................................... 60
1.5. Решения упражнений, не помеченных звездочкой ........................................ 68
1.6. Примечания к главе 1 .............................................................................................. 73

Глава 2. Структуры данных и библиотеки ................................................. 76

2.1. Общий обзор и мотивация  ................................................................................... 76
2.2. Линейные структуры данных – встроенные библиотеки .............................. 79
2.3. Нелинейные структуры данных – встроенные библиотеки .......................... 90
2.4. Структуры данных с реализациями библиотек, написанными  
авторами этой книги ...................................................................................................... 99
2.4.1. Граф ..................................................................................................................... 99
2.4.2. Система непересекающихся множеств ......................................................103
2.4.3. Дерево отрезков ...............................................................................................107
2.4.4. Дерево Фенвика ...............................................................................................112
2.5. Решения упражнений, не помеченных звездочкой .......................................118
2.6. Примечания к главе 2 .............................................................................................121

 Содержание

Глава 3. Некоторые способы решения задач .........................................124
3.1. Общий обзор и мотивация ...................................................................................124
3.2. Полный перебор ......................................................................................................125
3.2.1. Итеративный полный перебор ....................................................................127
3.2.2. Рекурсивный полный перебор (возвратная рекурсия) ..........................130
3.2.3. Советы ................................................................................................................134
3.3. «Разделяй и властвуй» ...........................................................................................146
3.3.1. Интересное использование двоичного поиска ........................................146
3.4. «Жадные» алгоритмы ............................................................................................152
3.4.1. Примеры ............................................................................................................153
3.5. Динамическое программирование ....................................................................160
3.5.1. Примеры DP ......................................................................................................161
3.5.2. Классические примеры ..................................................................................171
3.5.3. Неклассические примеры .............................................................................184
3.6. Решения упражнений, не помеченных звездочкой .......................................192
3.7. Примечания к главе 3 .............................................................................................195

Глава 4. Графы ...........................................................................................................197
4.1. Общий обзор и мотивация ...................................................................................197
4.2. Обход графа ..............................................................................................................198
4.2.1. Поиск в глубину (Depth First Search, DFS) ..................................................198
4.2.2. Поиск в ширину (Breadth First Search, BFS) ...............................................200
4.2.3. Поиск компонент связности (неориентированный граф) ....................202
4.2.4. Закрашивание – Маркировка/раскрашивание компонент  
связности .....................................................................................................................203
4.2.5. Топологическая сортировка (направленный ациклический граф) ....204
4.2.6. Проверка двудольности графа .....................................................................206
4.2.7. Проверка свойств ребер графа через остовное дерево DFS ..................207
4.2.8. Нахождение точек сочленения и мостов (неориентированный  
граф) ..............................................................................................................................209
4.2.9. Нахождение компонент сильной связности (ориентированный  
граф) ..............................................................................................................................212
4.3. Минимальное остовное дерево ...........................................................................218
4.3.1. Обзор ..................................................................................................................218
4.3.2. Алгоритм Краскала .........................................................................................219
4.3.3. Алгоритм Прима ..............................................................................................221
4.3.4. Другие варианты применения .....................................................................222
4.4. Нахождение кратчайших путей из заданной вершины во все  
остальные (Single – Source Shortest Paths, SSSP) .....................................................229
4.4.1. Обзор ..................................................................................................................229
4.4.2. SSSP на невзвешенном графе .......................................................................230
4.4.3. SSSP на взвешенном графе ...........................................................................232
4.4.4. SSSP на графе, имеющем цикл с отрицательным весом .......................237
4.5. Кратчайшие пути между всеми вершинами ....................................................242
4.5.1. Обзор ..................................................................................................................242
4.5.2. Объяснение алгоритма DP Флойда–Уоршелла .........................................243
4.5.3. Другие применения ........................................................................................246

Содержание  7

4.6. Поток ..........................................................................................................................253
4.6.1. Обзор ..................................................................................................................253
4.6.2. Метод Форда–Фалкерсона ............................................................................254
4.6.3. Алгоритм Эдмондса–Карпа ..........................................................................256
4.6.4. Моделирование графа потока – часть I ......................................................257
4.6.5. Другие разновидности задач, использующих поток ..............................259
4.6.6. Моделирование графа потока – часть II ....................................................261
4.7. Специальные графы ...............................................................................................264
4.7.1. Направленный ациклический граф ............................................................265
4.7.2. Дерево .................................................................................................................274
4.7.3. Эйлеров граф ....................................................................................................276
4.7.4. Двудольный граф .................................................................................................277
4.8. Решения упражнений, не помеченных звездочкой .......................................287
4.9. Примечания к главе 4 .............................................................................................291

Глаа 5. Математика .................................................................................................293
5.1. Общий обзор и мотивация ...................................................................................293
5.2. Задачи Ad Hoc и математика ................................................................................294
5.3. Класс Java BigInteger ...............................................................................................303
5.3.1. Основные функции .........................................................................................303
5.3.2. Дополнительные функции  ...........................................................................305
5.4. Комбинаторика ........................................................................................................311
5.4.1. Числа Фибоначчи ............................................................................................311
5.4.2. Биномиальные коэффициенты ...................................................................312
5.4.3. Числа Каталана ................................................................................................313
5.5. Теория чисел .............................................................................................................319
5.5.1. Простые числа ..................................................................................................319
5.5.2. Наибольший общий делитель и наименьшее общее кратное ..............322
5.5.3. Факториал .........................................................................................................322
5.5.4. Нахождение простых множителей с помощью  
оптимизированных операций пробных разложений на множители ...........323
5.5.5. Работа с простыми множителями ...............................................................324
5.5.6. Функции, использующие простые множители ........................................325
5.5.7. Модифицированное «решето» .....................................................................327
5.5.8. Арифметические операции по модулю .....................................................327
5.5.9. Расширенный алгоритм Евклида:  
решение линейного диофантова уравнения ......................................................328
5.6. Теория вероятностей ..............................................................................................334
5.7. Поиск цикла ..............................................................................................................336
5.7.1. Решение(я), использующее(ие) эффективные структуры данных ......337
5.7.2. Алгоритм поиска цикла, реализованный Флойдом ................................337
5.8. Теория игр .................................................................................................................340
5.8.1. Дерево решений ..............................................................................................341
5.8.2. Знание математики и ускорение решения ...............................................342
5.8.3. Игра Ним ...........................................................................................................343
5.9. Решения упражнений, не помеченных звездочкой .......................................344
5.10. Примечания к главе 5 ..........................................................................................346

 Содержание

Глава 6. Обработка строк ....................................................................................349
6.1. Обзор и мотивация .................................................................................................349
6.2. Основные приемы и принципы обработки строк ..........................................350
6.3. Специализированные задачи обработки строк ..............................................353
6.4. Поиск совпадений в строках ................................................................................360
6.4.1. Решения с использованием библиотечных функций ............................361
6.4.2. Алгоритм Кнута–Морриса–Пратта .............................................................361
6.4.3. Поиск совпадений в строках на двумерной сетке ...................................364
6.5. Обработка строк с применением динамического программирования .....366
6.5.1. Регулирование строк (редакционное расстояние) ..................................366
6.5.2. Поиск наибольшей общей подпоследовательности ...............................369
6.5.3. Неклассические задачи обработки строк с применением  
динамического программирования......................................................................370
6.6. Суффиксный бор, суффиксное дерево, суффиксный массив .......................372
6.6.1. Суффиксный бор и его приложения ...........................................................372
6.6.2. Суффиксное дерево .........................................................................................374
6.6.3. Практические приложения суффиксного дерева ....................................375
6.6.4. Суффиксный массив .......................................................................................379
6.6.5. Практические приложения суффиксного массива .................................386
6.7. Решения упражнений, не помеченных звездочкой ........................................392
6.8. Примечания к главе ................................................................................................396

Глава 7. (Вычислительная) Геометрия ........................................................398
7.1. Обзор и мотивация .................................................................................................398
7.2. Основные геометрические объекты и библиотечные функции для них ...400
7.2.1. Нульмерные объекты: точки .........................................................................400
7.2.2. Одномерные объекты: прямые ....................................................................403
7.2.3. Двумерные объекты: окружности ...............................................................408
7.2.4. Двумерные объекты: треугольники ............................................................411
7.2.5. Двумерные объекты: четырехугольники ...................................................414
7.2.6. Замечания о трехмерных объектах .............................................................415
7.3. Алгоритмы для многоугольников с использованием библиотечных  
функций ............................................................................................................................418
7.3.1. Представление многоугольника ..................................................................419
7.3.2. Периметр многоугольника ............................................................................419
7.3.3. Площадь многоугольника ..............................................................................420
7.3.4. Проверка многоугольника на выпуклость ................................................420
7.3.5. Проверка расположения точки внутри многоугольника .......................421
7.3.6. Разделение многоугольника с помощью прямой линии .......................422
7.3.7. Построение выпуклой оболочки множества точек ..................................424
7.4. Решения упражнений, не помеченных звездочкой ........................................430
7.5. Замечания к главе ...................................................................................................434

Глава 8. Более сложные темы .........................................................................436
8.1. Обзор и мотивация .................................................................................................436
8.2. Более эффективные методы поиска ...................................................................436

Содержание  9

8.2.1. Метод поиска с возвратами с применением битовой маски ...............437
8.2.2. Поиск с возвратами с интенсивным отсечением ....................................442
8.2.3. Поиск в пространстве состояний с применением поиска  
в ширину или алгоритма Дейкстры ......................................................................444
8.2.4. Встреча в середине (двунаправленный поиск) ........................................446
8.2.5. Поиск, основанный на имеющейся информации: A* и IDA* ................448
8.3. Более эффективные методы динамического программирования .............455
8.3.1. Динамическое программирование с использованием битовой  
маски .............................................................................................................................455
8.3.2. Некоторые общие параметры (динамического  
программирования) ..................................................................................................456
8.3.3. Обработка отрицательных значений параметров  
с использованием метода смещения ....................................................................458
8.3.4. Превышение лимита памяти? Рассмотрим использование  
сбалансированного бинарного дерева поиска как таблицы  
запоминания состояний ..........................................................................................460
8.3.5. Превышение лимита памяти/времени? Используйте более  
эффективное представление состояния ..............................................................460
8.3.6. Превышение лимита памяти/времени? Отбросим один параметр, 
будем восстанавливать его по другим параметрам ..........................................462
8.4. Декомпозиция задачи ............................................................................................467
8.4.1. Два компонента: бинарный поиск ответа и прочие ..............................468
8.4.2. Два компонента: использование статической задачи RSQ/RMQ ........470
8.4.3. Два компонента: предварительная обработка графа  
и динамическое программирование ....................................................................471
8.4.4. Два компонента: использование графов ..................................................473
8.4.5. Два компонента: использование математики .........................................474
8.4.6. Два компонента: полный поиск и геометрия ..........................................474
8.4.7. Два компонента: использование эффективной структуры данных ...474
8.4.8. Три компонента ...............................................................................................475
8.5. Решения упражнений, не помеченных звездочкой .......................................484
8.6. Замечания к главе ...................................................................................................485

Глава 9. Малораспространенные темы ......................................................487
Общий обзор и мотивация ...........................................................................................487
9.1. Задача 2­SAT .............................................................................................................488
9.2. Задача о картинной галерее .................................................................................491
9.3. Битоническая задача коммивояжера .................................................................492
9.4. Разбиение скобок на пары ....................................................................................495
9.5. Задача китайского почтальона ............................................................................496
9.6. Задача о паре ближайших точек ..........................................................................497
9.7. Алгоритм Диница ....................................................................................................499
9.8. Формулы или теоремы...........................................................................................500
9.9. Алгоритм последовательного исключения переменных, или метод  
Гаусса .................................................................................................................................502
9.10. Паросочетание в графах ......................................................................................505
9.11. Кратчайшее расстояние на сфере (ортодромия) ...........................................509

 Содержание

9.12. Алгоритм Хопкрофта–Карпа..............................................................................511
9.13. Вершинно и реберно не пересекающиеся пути ............................................512
9.14. Количество инверсий ...........................................................................................513
9.15. Задача Иосифа Флавия ........................................................................................515
9.16. Ход коня ..................................................................................................................516
9.17. Алгоритм Косараджу ............................................................................................518
9.18. Наименьший общий предок ..............................................................................519
9.19. Создание магических квадратов (нечетной размерности) ........................522
9.20. Задача о порядке умножения матриц ..............................................................523
9.21. Возведение матрицы в степень .........................................................................525
9.22. Задача о независимом множестве максимального веса .............................530
9.23. Максимальный поток минимальной стоимости ..........................................532
9.24. Минимальное покрытие путями в ориентированном  
ациклическом графе ......................................................................................................533
9.25. Блинная сортировка .............................................................................................535
9.26. Ро­алгоритм Полларда для разложения на множители целых чисел ......538
9.27. Постфиксный калькулятор и преобразование выражений ........................540
9.28. Римские цифры .....................................................................................................543
9.29. k­я порядковая статистика .................................................................................545
9.30. Алгоритм ускоренного поиска кратчайшего пути .......................................549
9.31. Метод скользящего окна .....................................................................................550
9.32. Алгоритм сортировки с линейным временем работы.................................553
9.33. Структура данных «разреженная таблица» ....................................................555
9.34. Задача о ханойских башнях................................................................................558
9.35. Замечания к главе .................................................................................................559

Приложение А. uHunt ............................................................................................562

Приложение В. Благодарности .......................................................................567

Список используемой литературы ...............................................................569

Предметный указатель ........................................................................................574

Издательство «ДМК Пресс» выражает благодарность техническим редакторам 
книги «Спортивное программирование», а именно: 

 
 Олегу Христенко – главный судья Moscow Workshops; технический координатор Олимпиадных школ МФТИ, Moscow Workshops Juniors и международных сборов по программированию для подготовки к соревнованиям по программированию; сопредседатель жюри Moscow Programming 
Contest; соавтор курса «Быстрый старт в спортивное программирование» в рамках RuCode;

 
 Филиппу Руховичу – к.ф.­м.н.; преподаватель кафедры алгоритмов 
и технологий программирования МФТИ; двукратный призер и победитель Всероссийской олимпиады школьников по информатике; финалист 
ACM ICPC 2014; четырехкратный призер NEERC (2010–2013); сотренер 
бронзовых призеров ICPC 2019; методист отделения информатики летних и зимних Олимпиадных школ МФТИ; соавтор курса «Быстрый старт 
в спортивное программирование» в рамках RuCode;

 
 Владиславу Невструеву – преподаватель летних и зимних Олимпиадных школ МФТИ, Летней компьютерной школы; преподаватель «Открытых Московских тренировок»; автор задач на олимпиады: «Квалификационный этап Moscow Programming Contest», «Когнитивные 
технологии», «Муниципальный этап Всероссийской олимпиады школьников»; соавтор курса «Быстрый старт в спортивное программирование» 
в рамках RuCode.

Коллеги из Национального университета Сингапура оказывают 
значительное влияние на развитие сообщества олимпиадного программирования во всем мире. С молодым исследователем в области 
компьютерных наук Стивеном Халимом и его коллегой профессором 
Сан Теком мы в 2019 году провели сборы Discover Singapore в рамках 
международного образовательного проекта Moscow Work shops, который зародился 8 лет назад на кампусе Московского физико­технического института 
(МФТИ). Сингапур в 2020 году готовился стать городом проведения международной 
олимпиады школьников по информатике IOI. Хотя в планы вмешалась пандемия, 
олимпиада все же пройдет в онлайн­режиме, а очно город примет IOI в 2021 году. 
В России достаточно развито соревновательное программирование, популярны 
олимпиады и чемпионаты на школьном и студенческом уровне. Благодаря высоким 
достижениям российских студентов на международных соревнованиях по программированию, заявку на проведение чемпионата мира по программированию «ICPC 
World Finals 2020» выиграла Москва, принимающим вузом стал МФТИ. Российские 
студенты последние 20 лет уверенно доминируют на этом соревновании, а МФТИ – 
единственный вуз в мире, который на сегодняшний день имеет непрерывную череду медалей ICPC больше трех. Мы создали самый большой образовательный проект в мире по алгоритмическому программированию Moscow Workshops, который 
принес новые возможности более 3,5 тысячи студентов 61 страны. Независимым 
критерием подтверждения их успехов становятся результаты на чемпионате ICPC 
и старт карьеры в ведущих компаниях ИТ­индустрии.
На кампусе московского Физтеха с 2018 года проводится отбор и подготовка национальной сборной на IOI. Также к этой олимпиаде школьников со всего мира могут подготовиться в школе Moscow Workshops Juniors. В 2019 году российская сборная 
взяла 4 золотые медали IOI, трое из этих ребят учились в Juniors, как и еще 12 медалистов из сборных Беларуси, Азербайджана, Киргизии, Дании, Сирии, Турции, Болгарии 
и Индии. Первые выпускники лагеря уже показывают выдающиеся успехи: в прошлом 
году стартап AI Factory, созданный выпускником Juniors Александром Машрабовым 
с напарниками, купила компания Snap за $166 млн. В 2020 году мы совместно с 10 российскими вузами на принципах открытости, равенства, уважения, единства запустили 
первый учебный фестиваль по алгоритмическому программированию и искусственному интеллекту RuCode для всех желающих попробовать свои силы. В рамках фестиваля мы выпустили вводный онлайн­курс «Быстрый старт в спортивное программирование» на платформе Stepik, провели интенсивы и чемпионаты по искусственному 
интеллекту и алгоритмическому программированию. Мероприятия охватили 12 тысяч человек, в том числе взрослых, и мы будем проводить фестиваль и дальше, чтобы 
популяризировать ИТ­знания. RuCode был задуман так, чтобы сильные технические 
вузы из разных регионов России смогли передать свои лучшие практики учащимся, 
дать широкий спектр образовательных методик. Книга Стивена Халима – это тоже 
экскурс, но в систему подготовки коллег с Востока, которые так же стабильно показывают выдающиеся результаты на соревнованиях по программированию. Уверены, что 
книга поможет изучить все самые необходимые алгоритмы и поднять ваш уровень 
знаний в программировании до уровня чемпионов мира. 

Алексей Малеев,  
проректор МФТИ,  
основатель международного образовательного проекта Moscow Workshops

На протяжении всего существования Mail.ru Group мы ставили перед собой амбициозные цели, главная из которых – стать центром 
притяжения самых ярких талантов, способных генерировать новые 
идеи, оставаясь при этом на стыке практики и академии. 
 Выиграть борьбу за таланты можно, только позволив каждому 
участнику раскрыть свой потенциал, в том числе и в рамках чемпионатов. За почти 10 лет мы провели их больше 100, ориентируясь на ведущие 
мировые практики. В процессе работы мы поняли, что конкуренция и соревновательный дух, вступающие в синергию с опытом и экспертизой, позволяют достигать по­настоящему заметных высот. 
Уверен, что книга «Спортивное программирование» Стивена Халима и Феликса 
Халима поможет не только школьникам и студентам, поставившим перед собой 
амбициозную цель добиться заметных результатов на международных олимпиадах ICPC и IOI, но и всем тем, кто мечтает достичь новых профессио нальных высот 
и стать более конкурентоспособным при решении сложных IT­задач. 
Желаю вам увлекательного чтения. Дерзайте!

Дмитрий Смыслов,
вице­президент по персоналу и образовательным проектам

Спортивное программирование в некотором роде определило мою 
жизнь. Я увлекся разработкой еще на ZX Spectrum, позже принял 
участие в школьной олимпиаде, задачи которой показались довольно простыми... и не смог остановиться. Программирование 
увлекло меня свободой, которую оно дает для выражения мыслей: 
здесь практически нет рамок, и любую задумку можно реализовать 
быст ро и эффективно. Победа на олимпиадах помогла поступить на факультет ВМК 
МГУ, а затем пройти путь от джуна­разработчика до руководителя отдела и совладельца бизнеса.
Сейчас я издаю медиа Tproger. В комментариях мы часто сталкиваемся с мнением, что для работы спортивное программирование бесполезно: «в повседневной 
жизни требуется решать задачи, которые никак не связаны с теми, что предлагаются на контестах вроде ICPC». Я не согласен.
Конечно, напрямую навыки спортивного программирования не помогут. Но 
придумывание оптимальных алгоритмов, воспитание в себе внимания к деталям, 
да хотя бы просто разминка для ума значительно упрощают достижение успехов 
в карьере разработчика. Именно по этой причине я всегда с симпатией относился 
к кандидатам, которые участвовали в олимпиадах по программированию или просто нарешивали задачки из архивов. Везде есть исключения, но такие люди чаще 
проектировали и реализовывали действительно хорошие продукты.
Готовы попробовать? Регистрируйтесь на любом сайте с архивом задач, берите 
эту книгу в помощники, и вперед.
Если вы уже участвуете в контестах, то найдете в книге «Спортивное программирование» Стивена Халима и Феликса Халима много полезных техник и советов, 
чтобы стать лучше.
И помните, если будет сложно – это нормально. Не останавливайтесь, только так 
можно достичь настоящих высот в любом деле.

Алексей Михайлишин, 
генеральный директор Tproger

Вступление

Однажды (это случилось 11 ноября 2003 года) я получил письмо по электронной почте, автор которого писал мне:

«Я должен сказать, что на сайте университета Вальядолида Вы положили 
начало новой ЦИВИЛИЗАЦИИ. Своими книгами (он имел в виду «Задачи по программированию: пособие по подготовке к олимпиадам по программированию» [60], написанное в соавторстве со Стивеном Скиеной) 
Вы вдохновляете людей на подвиги. Желаю Вам долгих лет жизни, чтобы 
служить человечеству, создавая новых супергероев – программистов».

Хотя это было явным преувеличением, письмо заставило меня задуматься. 
У меня была мечта: создать сообщество вокруг проекта, который я начал как 
часть моей преподавательской работы в университете Вальядолида. Я мечтал 
создать сообщество, которое объединило бы множество людей с разных концов 
света, связанных единой высокой целью. Выполнив несколько запросов в поисковике, я быстро нашел целое онлайн­сообщество, объединявшее несколько 
сайтов, обладавших всем тем, чего не хватало сайту университета Валья долида.
Сайт «Методы решения задач» Стивена Халима, молодого студента из Индонезии, показался мне одним из наиболее интересных. Я увидел, что однажды 
мечта может стать реальностью, потому что на этом сайте я нашел результат 
кропотливой работы гения в области алгоритмов и программирования. Более 
того, цели, о которых он говорил, вполне соответствовали моей мечте: служить 
человечеству. И еще я узнал, что у него есть брат, Феликс Халим, разделяющий 
его увлечение программированием.
До начала нашего сотрудничества прошло довольно много времени, но, 
к счастью, все мы продолжали параллельно работать над реализацией этой 
мечты. Книга, которую вы сейчас держите в руках, является лучшим тому доказательством.
Я не могу представить лучшего дополнения для архива задач университета 
Вальядолида. Эта книга использует множество примеров с сайта университета 
Вальядолида, тщательно отобранных и разбитых по категориям по типам задач и методам их решения. Она оказывает огромную помощь пользователям 
данного сайта. Разобрав и решив большинство задач по программированию из 
этой книги, читатель сможет легко решить не менее 500 задач, предложенных 
«Онлайн­арбитром» университета Вальядолида, и попасть в число 400–500 
лучших среди 100 000 пользователей «Онлайн­арбитра».
Книга «Спортивное программирование» также подходит для программистов, которые хотят улучшить свои позиции на региональных и международных соревнованиях по программированию. Ее авторы прошли через эти соревнования (ICPC и IOI) вначале как участники, а теперь и как тренеры. Она также 
рекомендуется новичкам – как говорят Стивен и Феликс во введении: «Книгу 
рекомендуется прочесть не один, а несколько раз».

 Вступление

Кроме того, она содержит исходный код на C++, реализующий описанные 
алгоритмы. Понимание задачи – это одно, знание алгоритма ее решения – другое, а правильная реализация решения через написание краткого и эффективного кода – третья непростая задача. Прочитав эту книгу трижды, вы поймете, 
что ваши навыки программирования значительно улучшились и, что еще важнее, вы стали более счастливым человеком, чем были раньше.
Мигель А. Ревилла,  
Университет Вальядолида,
создатель сайта «Онлайн­арбитр»,
член Международного оргкомитета ICPC 
http://uva.onlinejudge.org; http://livearchive.onlinejudge.org

Участники финального мирового турнира в Варшаве, 2012.  
Слева направо: Фредерик Нимеля, Карлос, Мигель Ревилла, Мигель-младший, Феликс, Стивен