Как отлаживать олимпиадные задачи: поиск бага за минимальное время ГАЙД

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

Этот гайд — про работу с WA (wrong answer), TL (time limit), RE (runtime error) и MLE (memory limit). Везде, где можно, держим один принцип: первое, что нужно сделать с багом, — точно его воспроизвести. Не «переписать алгоритм», не «попробовать ещё раз», а получить минимальный вход, на котором ошибка повторяется.

---

Шаг 0: до начала отладки

Перечитать своё решение

Звучит банально. Но в 30–40% случаев баг находится при втором чтении кода без всякого запуска. Что искать на первом просмотре:

• < vs <= в граничных условиях циклов — самая распространённая ошибка.
• + vs -, * vs / — переставленные операции.
• Тип переменной — в C++ int для произведения двух чисел до $10^5$ переполнится при возведении в квадрат.
• Где-то забытая инициализация — ans = 0, dp[0] = 0, visited[start] = True.
• Скопированный с другой задачи кусок — старая глобальная переменная, забытое cin >> n; от прошлой задачи.

Чтение должно занимать минуту-две. Если за это время баг не очевиден — переходим к воспроизведению.

Перечитать своё условие

Тоже банально. Тоже работает в трети случаев. Открываем условие и точно сверяем:

• Формат ввода: что в первой строке, что во второй.
• Что именно надо вывести: «количество» или «сумма», «по модулю» или нет.
• Ограничения: $n \le 10^5$ или $10^6$? Это меняет допустимую сложность.
• Тонкости: «гарантируется, что ответ умещается в …», «считать с одного» или «с нуля», «если решения нет — вывести -1».

Если в условии нашлось расхождение с кодом — переписали и снова отправили. Если не нашлось — переходим к воспроизведению.

---

Шаг 1: точно воспроизвести ошибку

При WA — найти контртест

Идеальный контртест — минимальный вход, на котором ваш код даёт неверный ответ. Источники:

• Примеры из условия. Если падает на примере 2, его и берём как контртест.
• Контртест из системы. Codeforces показывает «Wrong answer on test 4», иногда показывает первые 100 символов теста. Этого часто достаточно.
• Ручной мини-тест. Если падает на «system test 28» и теста не видно — конструируем самостоятельно. Тривиальные случаи: $n = 1$, $n = 2$, все элементы одинаковы, все нули, отрицательные значения (если разрешены), максимальные значения.

При TL — выяснить асимптотику

Запустить решение локально на максимально допустимом входе. Сгенерировать его одной строкой Python:

print(1000000)
print(*range(1, 1000001))

Если локально упирается в 5–10 сек, а лимит 2 — сложность алгоритма выше допустимой, надо переделывать. Если локально 0.5 сек, а на сервере 2 — упирается в IO (медленное чтение/вывод), исправляем чтение.

При RE — найти место падения

В C++ — добавить cerr принты до и после подозрительных строк, запустить локально, увидеть, после какой строки падает. На сервере — посмотреть код возврата: signal 11 (SIGSEGV) — выход за границы массива; signal 6 (SIGABRT) — assert, исключение из STL; signal 8 (SIGFPE) — деление на ноль.

В Python — поймать traceback, увидеть строку. IndexError — выход за границы списка; KeyError — обращение к несуществующему ключу словаря; RecursionError — превышен лимит рекурсии (надо итеративно или sys.setrecursionlimit).

При MLE — посчитать память на бумаге

int[10^7] в C++ — 40 МБ; long long[10^7] — 80 МБ. Лимит обычно 256 МБ, иногда 64 МБ. Двумерный массив int[3000][3000] — 36 МБ — нормально; int[10000][10000] — 400 МБ — нет.

В Python накладные расходы — около 28 байт на int в list. [0] * 10**7 занимает порядка 280 МБ. Альтернативы: array.array, numpy, или просто уменьшить размер.

---

Шаг 2: локализация бага бисекцией

Получили контртест, на котором падает. Не пытаемся «переписать алгоритм». Сначала — локализовать, в какой именно функции/строке расхождение с ожидаемым ответом.

Метод: пол-программы за раз

В коде есть условные «контрольные точки»: после чтения ввода, после сортировки, перед основным циклом, в каждой итерации, перед выводом. Печатаем значения переменных в каждой точке. Сверяем с тем, что ожидаем по руке.

Пример: задача на DP. Не уверены, в каком переходе ошибка. Прогоняем входной пример руками и записываем ожидаемый dp[i] для каждого $i$. Печатаем dp после заполнения. Первое расхождение — между $i - 1$ и $i$, значит, баг в переходе на $i$-й шаг. Уже не вся программа, а конкретные пять строк.

При TL — измерить время по частям

Если уверены в корректности алгоритма, но TL: добавить time.perf_counter() в Python или chrono::steady_clock в C++ перед каждой подозрительной операцией. Часто оказывается, что 80% времени уходит на одну строку с неудачной сложностью (например, if x in big_list вместо if x in big_set).

Тактика «закомментировать вывод»

Очень мощный приём при WA. Берём контртест и закомментируем большие куски логики. Например, в задаче с двумя стадиями: получили ввод, прогнали стадию 1, вывели промежуточный результат. Если стадия 1 верна — баг в стадии 2. Бисекция в полном смысле — каждая итерация уменьшает «область бага» вдвое.

---

Шаг 3: stress test против brute force

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

Что такое brute force

Простое решение, которое точно работает, но медленно. Для задачи на массив длины $n \le 10^5$ — наивное $O(n^2)$ или $O(n^3)$, которое на маленьких $n$ (скажем, $n \le 20$) сработает мгновенно.

Для задачи «выбрать подмножество с условием» — переборщик $2^n$. Для «оптимальный ход в игре» — рекурсия с мемоизацией без оптимизаций.

Шаблон stress test (Python)

import random, subprocess, sys

for it in range(1000):
    # 1. Сгенерировать случайный тест
    n = random.randint(1, 6)
    a = [random.randint(1, 10) for _ in range(n)]
    test = f"{n}\n{' '.join(map(str, a))}\n"

    # 2. Запустить оба решения
    out_main = subprocess.run(['./main'], input=test, capture_output=True, text=True).stdout
    out_brute = subprocess.run(['./brute'], input=test, capture_output=True, text=True).stdout

    # 3. Сравнить
    if out_main.strip() != out_brute.strip():
        print(f"MISMATCH on iter {it}")
        print("Input:")
        print(test)
        print("Main:", out_main.strip())
        print("Brute:", out_brute.strip())
        sys.exit(1)

print("OK 1000 tests")

Что важно:

• Маленькие $n$ в тестах. $n \le 5$–$10$ обычно достаточно. Большие тесты — отвлекают и медленнее проходят.
• Малые значения. Числа $a_i$ — до 10 или 20. Это не уменьшает покрытие, а ускоряет.
• Тысяча итераций. За 30 секунд проходит без проблем. На 100 — могут упустить редкий баг.

Как найти контртест в обратку

Stress test даёт минимальный вход, на котором падает. Дальше — обычная отладка из шага 2. Это исключительно эффективный приём: даже на CF 2000+ задачах опытные участники начинают с stress test, если не видят бага глазами.

---

Шаг 4: проверка крайних случаев из чек-листа

После каждого изменения кода — мысленный прогон по чек-листу:

• $n = 1$ — частный случай? Бывает, что цикл начинается с for i in range(1, n): и при $n = 1$ не выполняется ни разу, ответ остаётся неинициализированным.
• Все элементы одинаковы. В жадных задачах часто ломается «выбор лучшего», когда «лучших» несколько.
• Все нули / все максимальные. Переполнение или некорректная инициализация INF.
• $n$ на границе ограничений. $n = 10^6$ — проверить, что код не делает $O(n^2)$.
• Граница < vs <=. Самая частая ошибка в бинпоиске.
• Целочисленное переполнение. В C++ произведение двух int-значений до $10^9$ — long long обязательно.
• Считают «по модулю»? Если задача с модулем, проверить, что каждое умножение/сложение сопровождается % MOD.
• Что выводить при «нет решения»? Часто -1, иногда IMPOSSIBLE, иногда специальный формат. Условие.

Этот чек-лист стоит записать однажды и пробегать его перед отправкой каждой задачи. Через 50–100 задач превращается в автоматический рефлекс.

---

Самодисциплина на контесте

Отладка вне контеста — это про методологию. Отладка на контесте — про методологию и управление временем. Несколько правил, которые экономят рейтинг лучше любого алгоритма.

Бюджет на одну задачу

Раунд Div.2 — 2 часа, 5–6 задач. На самую сложную из тех, что хотите решить, разумно потратить 40–60 минут. Если задача не идёт 40 минут — переключаемся на следующую. Возврат — после прохода по всем доступным.

Когда переписать с нуля

Если после двух циклов «изменили код → отправили → WA» баг не локализуется, закройте файл и напишите заново. Часто это занимает 15 минут и сразу даёт AC, потому что в новой версии нет «случайно унаследованных» ошибок.

Сигналы для переписывания:

• Код выглядит «слепленным», много веток, несколько if-ов добавлены «на всякий случай».
• Не уверены в корректности базовых частей (чтение, вывод).
• Каждая правка ломает что-то новое.

Когда не переписывать

• Уверены в общей структуре, баг точечный.
• Уже потратили 30+ минут — переписать займёт почти столько же. Лучше ещё пять минут на локализацию.
• Stress test уже подобрал контртест — отладка по нему 5–10 минут, переписывание дольше.

Куда тратить «лишний» час контеста

Если решили все, что планировали — последний час часто решает позицию в таблице. Не пытаться сразу штурмовать F. Сначала: убедиться, что отправленные задачи действительно AC (проверить лидерборд, если задача с системными тестами). Потом — выбрать одну задачу повыше и работать с ней методично, не прыгая.

---

Профилактика: что снижает количество багов

Отладка — следствие ошибок. Лучший способ ускорить отладку — меньше делать ошибок. Несколько привычек, которые работают:

• Писать псевдокод до кода. 5 минут на бумаге — десятки минут на отладке.
• Именовать переменные осмысленно. next_cheaper, last_seen, pref_sum лучше, чем a, b, c, d. Через час чтения кода это окупается.
• Сразу обработать крайние случаи. $n = 0$, $n = 1$, пустой массив — добавить отдельные if в начале функции, а не «надеяться, что цикл сработает».
• Не копипастить чужой код без понимания. Шаблон BFS, скопированный без понимания, ломается на малейшем отклонении задачи. Лучше написать заново и потратить три лишних минуты.
• Сразу писать с правильными типами. В C++ объявлять long long, как только есть сомнение. В Python типы целых неограничены, но int vs float в делении — частая ловушка (a / b даёт float, a // b целое).
• Не оптимизировать преждевременно. На полосах CF до 1600 чаще нужна аккуратность, а не скорость. Сначала корректное решение, потом — если упёрлось в TL — оптимизация.

---

Когда тренироваться отлаживать целенаправленно

Дайте себе раз в неделю «час отладки»: возьмите задачу полосы CF +200 от вашего рейтинга, попробуйте сразу написать решение без зачёркиваний — и отлаживайте, что получилось. Запишите, сколько потратили времени и какой именно метод дал контртест.

После 5–10 таких сессий вы заметите, что одни и те же ошибки повторяются. Это и есть рабочий чек-лист для пред-отправочной проверки.

---

Итого

• Принцип: отладка — не вдохновение, а протокол. Шаги: воспроизвести → локализовать → проверить чек-лист → отправить.
• Главный инструмент: stress test против brute force. Подходит к 80% багов алгоритмических задач.
• Дисциплина: бюджет на задачу 40–60 минут, переписывание с нуля при «слепленном» коде, чек-лист крайних случаев перед каждой отправкой.
• Профилактика: псевдокод до кода, осмысленные имена, ранняя обработка крайних случаев.

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