Олимпиадные задачи по программированию: из чего состоят и какие бывают

У олимпиадной задачи всегда одна и та же разметка: условие, формат ввода, формат вывода, ограничения на числа и время работы, примеры. Решение читает данные со входа, печатает ответ на выход и должно уложиться в лимит. Типов задач примерно десяток, и почти каждая олимпиадная задача до регионального этапа сводится к одному из них.

Как читать условие

Разделов в условии пять, и каждый читают по-своему.

Само условие описывает, что происходит. Формат ввода говорит, сколько чисел подаётся и в каком порядке; отступление от него судья считает неверным ответом, даже если ответ посчитан правильно. Формат вывода задаёт, что именно печатать — одно число, несколько через пробел или строку. Ограничения — самый важный раздел, потому что по ним считается, какое решение пройдёт по времени. Примеры нужны для проверки себя, и одного примера почти никогда не хватает: они специально простые.

Порядок чтения у опытных участников обратный. Сначала смотрят ограничения, потом формат вывода, и только потом само условие — потому что ограничения решают, какой способ вообще имеет смысл придумывать.

Как по ограничениям понять, что перебор не пройдёт

Прикидка одна и считается в уме. Судья успевает порядка десяти миллионов простых действий в секунду на Python. Дальше смотрят, сколько действий сделает задуманное решение при самых больших числах из условия.

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

Это и есть главный навык, которого нет в школьной информатике: считать стоимость решения до того, как оно написано.

Типы олимпиадных задач

Прямое моделирование

Условие описывает процесс по шагам, и достаточно повторить его в цикле. Такие задачи стоят первыми на школьном этапе. Ошибаются в них не на алгоритме, а на чтении: пропустили условие «если очередь пуста» и получили неверный ответ на одном тесте.

Задачи этого типа: Моделирование процессов.

Разбор случаев

Ответ считается по-разному в нескольких ситуациях, и вся работа в том, чтобы найти все ситуации и не пропустить крайнюю. Обычно теряют границы: ноль, одно число, все числа одинаковые.

Задачи этого типа: Разбор случаев.

Жадный выбор

На каждом шаге берут лучший вариант из доступных и надеются, что итог окажется лучшим. Жадность работает не всегда, поэтому в олимпиадной задаче её надо не угадать, а обосновать: показать, что замена любого выбора на другой ответ не улучшает.

Задачи этого типа: Обмен и назначение.

Сортировка как подготовка

Задача выглядит сложной, пока данные лежат в случайном порядке, и становится простой после сортировки. Это самый частый приём, который превращает перебор пар в один проход.

Задачи этого типа: Сортировки.

Префиксные суммы

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

Задачи этого типа: Префиксные суммы.

Два указателя

По отсортированному массиву идут двумя границами навстречу или следом друг за другом. Заменяет двойной цикл одним проходом, и именно это чаще всего вытаскивает решение из лимита времени.

Задачи этого типа: Два указателя.

Бинарный поиск по ответу

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

Задачи этого типа: Бинарный поиск по ответу.

Динамическое программирование

Ответ для большой задачи собирают из ответов для её частей, которые уже посчитаны и записаны. Самый большой раздел олимпиадной информатики: с него начинается разница между муниципальным и региональным этапом.

Задачи этого типа: DP 1D.

Графы: обход и достижимость

Города и дороги, комнаты и двери, клетки лабиринта — всё это графы. Обход в ширину заодно даёт кратчайший путь, если все переходы равноценны.

Задачи этого типа: BFS/DFS.

Теория чисел

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

Задачи этого типа: Теория чисел (НОД, НОК, остатки).

Строки

Поиск подстроки, палиндромы, разбор текста по разделителям. В Python значительная часть таких задач решается встроенными операциями, и это тот случай, когда язык экономит время на туре.

Задачи этого типа: Строки.

Задачи из нашего банка по уровням

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

Уровень школьного этапа

Решается прямым повторением условия.

Уровень муниципального этапа

Нужен приём: сортировка, префиксные суммы, два указателя.

Уровень регионального этапа

Приёмы приходится соединять, а лимит времени отсекает перебор.

Весь банк с фильтрами по темам и уровням — в каталоге задач. Срез по классу лежит отдельно: 7 класс, 9 класс, 11 класс.

Частые вопросы

Где брать олимпиадные задачи по программированию?

Задачи прошлых лет публикуют организаторы олимпиад, но у них обычно нет проверки: решение некуда отправить. Тренироваться удобнее там, где есть автоматический судья и разбор попытки. У нас банк задач разложен по темам и по уровням сложности, каждая задача проверяется на скрытых тестах, и всё открыто бесплатно.

Как понять, какого уровня задача?

По тому, что она требует. Если ответ считается прямым повторением условия — это уровень школьного этапа. Если нужен приём вроде сортировки, префиксных сумм или двух указателей — муниципального. Если приёмы надо соединить или заметить свойство, которого в условии нет, — регионального. У нас эти три уровня обозначены L1, L2 и L3.

Почему правильное решение не проходит по времени?

Потому что число операций растёт быстрее, чем размер входных данных. Прикидка простая: судья успевает порядка десяти миллионов простых действий в секунду на Python. Если в условии сказано, что чисел до ста тысяч, а решение перебирает все пары, действий получается десять миллиардов, и лимит не выдерживается. Считать такую прикидку надо до того, как писать код.

Сколько задач нужно решить, чтобы пройти школьный этап?

Считать в задачах неправильно, потому что решённая заново задача того же типа почти ничего не добавляет. Правильнее считать в темах: школьный этап закрывается языком и первыми приёмами, это 8–10 тем и примерно 3–4 месяца занятий по 15–30 минут в день.

Что это за занятие целиком — на странице олимпиадного программирования. Маршрут подготовки по шагам — с нуля до олимпиады.