Дорожная карта: в каком порядке учить

Темы в олимпиадном программировании стоят друг на друге. Динамика на деревьях без обходов графа — это заучивание кода, а не понимание. Хеши без понимания, зачем нужен модуль, — источник вечных «почему у меня неверный ответ на десятом тесте».

Поэтому порядок изучения — не вопрос вкуса. Есть темы, которые бесполезно брать раньше срока: вы потратите на них втрое больше времени и всё равно не будете применять их сами.

Три правила порядка

Сначала то, что нужно везде. Оценка сложности, префиксные суммы, два указателя, сортировка. Эти четыре темы встречаются в задачах на любую другую тему.

Инструмент — после задачи, которая его требует. Дерево отрезков, взятое до того, как вы столкнулись с задачей «сумма на отрезке с изменениями», запоминается как обряд. Взятое после — как решение проблемы.

Одна новая тема за раз. Две параллельно дают ощущение движения и нулевой результат: на контесте вы не вспомните ни одну.

Ступень 1. База

1. Ввод-вывод, ветвления, циклы
2. Строки и списки
3. Функции и рекурсия
4. Оценка сложности — раньше всех алгоритмов: без неё непонятно, зачем они
5. Префиксные суммы
6. Два указателя и скользящее окно
7. Простые числа и решето

Ступень 2. Продвинутый

8. Сортировки и задачи после сортировки
9. Двоичный поиск: по массиву, потом по ответу
10. Стек, очередь, дек
11. Жадные алгоритмы и доказательство обменом
12. Графы: представление, обход в глубину, обход в ширину
13. Компоненты связности, двудольность
14. Кратчайшие пути: Дейкстра, Флойд, Форд — Беллман
15. Динамика: одномерная, по таблице, рюкзаки
16. Битовые операции и маски

Ступень 3. Профи

17. Топологическая сортировка, DAG, конденсация
18. Строки: префикс-функция и Z-функция
19. Боры и Ахо — Корасик
20. Хеши и сравнение подстрок
21. Дерево отрезков, корневая декомпозиция
22. Динамика по подотрезкам, по маскам, на деревьях
23. Геометрия
24. Теория игр

Что зависит от чего

Что можно брать не по порядку

Геометрия и теория игр стоят особняком: они почти ни на что не опираются, кроме базы, и их можно взять раньше, если такие задачи вам нравятся. Это единственное разумное исключение — остальные перестановки обходятся дороже, чем кажется.

В учебнике платформы двадцать разделов и больше двухсот статей. Читать их подряд по номерам не нужно — порядок ниже соответствует порядку тем.

Сначала

1. «Основы» — 4 статьи. Как устроена задача, как читать условие, что такое сложность
2. «Линейные алгоритмы» — 15 статей. Префиксные суммы, два указателя, окно
3. «Сортировки» — 12 статей
4. «Поиск» — 10 статей. Двоичный поиск и поиск по ответу

Дальше

5. «Жадные алгоритмы» — 10 статей. Обратите внимание на доказательства, а не на примеры
6. «Теория чисел» — 10 статей
7. «Рекурсия и перебор» — 10 статей
8. «C++ и STL» — 10 статей. Если переходите с Python
9. «Динамическое программирование» — 14 статей
10. «Графы» — 23 статьи, самый большой раздел. Читайте по частям вместе с решением задач
11. «Битовые операции» — 12 статей

Уровень перечневых

12. «Строки» — 11 статей
13. «Хеши» — 10 статей. После строк: так видно, что чем удобнее
14. «Отрезки и сканирующая прямая» — 10 статей
15. «Запросы на деревьях» — 8 статей
16. «Остовные деревья и СНМ» — 6 статей
17. «Динамика на графах» — 7 статей
18. «Корневая декомпозиция» — 6 статей
19. «Геометрия» — 20 статей
20. «Теория игр» — 8 статей

Как читать

Не подряд и не целиком. Рабочий порядок такой: берёте раздел, читаете две-три статьи, идёте решать задачи на них, возвращаетесь за следующими. Раздел «Графы» из двадцати трёх статей, прочитанный за вечер, не оставит после себя ничего.

Каждая статья заканчивается ссылками на соседние — по ним удобно достраивать тему, когда упёрлись в конкретной задаче.

Честные ориентиры при двух-трёх часах в неделю. Они не обещание, а точка отсчёта: если у вас вдвое дольше — это нормально, если втрое — стоит поменять способ занятий, а не количество часов.

Самый частый способ растянуть эти сроки вдвое — учить темы, не решая задач. Второй по частоте — решать задачи только на те темы, которые уже получаются.

Следующий урок — чек-лист развития: там способ проверить, что вы движетесь, а не топчетесь.