Как читать условие и выбирать алгоритм

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

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

Зачем это нужно

Начинающие бросаются кодить, едва прочитав условие, — и тонут в багах или получают TLE. Опытные сначала думают: что на самом деле просят, какие ограничения, какая сложность пройдёт, какой приём из арсенала подходит. Этот урок — про метод работы над задачей, который экономит время и нервы. Мы собираем воедино всё, что изучили: ограничения → асимптотика → выбор приёма. Без этой дисциплины даже знание всех алгоритмов не спасёт.

Шаг 1. Понять, что именно спрашивают

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

Шаг 2. Прочитать ограничения — это полподсказки

Ограничения на n почти кричат о нужной сложности (вспомни урок об асимптотике). Это самый недооценённый источник информации.

Увидел n = 18 — почти наверняка ждут 2^n. Увидел n = 2·10^5 — квадрат не пройдёт, ищи n log n. Эта связка «ограничение → асимптотика → приём» — главный навык олимпиадника.

Шаг 3. Сопоставить с известными паттернами

Спортивное программирование во многом — это узнавание. Держи в голове карту сигналов:

• «Кратчайший путь / минимум шагов» в графе/сетке → BFS (без весов) или Дейкстра (с весами).
• «Минимальное/максимальное значение, при котором...» → бинпоиск по ответу.
• «Сумма/минимум на отрезке + обновления» → дерево отрезков; без обновлений → префиксные суммы.
• «Сколькими способами / максимум при ограничении» → динамическое программирование.
• «Подотрезок/подстрока с условием» → два указателя или скользящее окно.
• «Связность / компоненты / объединение» → DSU или обход.
• «Выбрать с локально лучшим шагом» → жадность (но докажи!).

Шаг 4. Прикинуть и проверить идею до кода

Прежде чем писать, ответь себе: сколько операций сделает мой план на максимальном тесте? Покажем быструю прикидку прямо в коде.

import math

# Допустим, придумали решение за O(n log n). Пройдёт ли при n = 2*10^5?
n = 2 * 10**5
ops_nlogn = n * math.log2(n)
ops_n2 = n * n
limit = 10**8                       # грубый бюджет операций

print("O(n log n):", int(ops_nlogn), "-> пройдёт:" , ops_nlogn < limit)
print("O(n^2):    ", ops_n2, "-> пройдёт:", ops_n2 < limit)

Прикидка мгновенно показывает: O(n log n) для 2·10^5 — это ~3.5·10^6 операций (с запасом), а O(n^2) — 4·10^10 (безнадёжно). Такую оценку делай в уме за секунды — она отсекает заведомо медленные идеи.

Вывод:

O(n log n): 3521928 -> пройдёт: True
O(n^2):     40000000000 -> пройдёт: False

Шаг 5. Не забывай про подзадачи (формат ВсОШ)

Если задача даёт частичные баллы за группы тестов, не обязательно сразу писать полное решение. Часто разумно: забрать лёгкие подзадачи простым переборным или квадратичным решением (баллы в кармане!), а уже потом думать над полным. Иногда полное решение и не нужно — хватает того, что укладывается в твой уровень.

Чек-лист перед кодом

1. Сформулировал суть задачи в одном предложении?
2. Прочитал все ограничения, включая n, время, память?
3. Определил нужную сложность по ограничениям?
4. Узнал паттерн и выбрал приём?
5. Прикинул число операций — точно пройду?
6. Продумал особые случаи: n=0, n=1, пустой ввод, одинаковые элементы?

Итог

• Сначала переформулируй задачу без антуража в одно сухое предложение.
• Ограничения на n подсказывают нужную сложность, а та — класс алгоритма.
• Узнавай паттерны: «кратчайший путь», «минимум при условии», «число способов» и т. д.
• Прикинь число операций до кода; в формате ВсОШ не пренебрегай частичными баллами.