Отладка и стресс-тестирование

Получил WA, но примеры проходят? Стресс-тест автоматически найдёт контрпример, сравнив твоё решение с заведомо верным перебором.

Стресс-тестирование — приём отладки, при котором быстрое (но подозрительное) решение сравнивается с медленным, но заведомо верным эталоном на множестве случайных тестов; первое расхождение и есть контрпример.

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

Самая мучительная ситуация на олимпиаде: решение проходит все примеры из условия, но получает WA на скрытом тесте. Где ошибка — непонятно, тест ты не видишь. Стресс-тестирование решает эту проблему системно: оно само генерирует тысячи случайных тестов и находит тот, на котором твой код врёт. Это, пожалуй, самый ценный навык отладки в спортивном программировании — он превращает «слепой» поиск бага в автоматический. Освоив его, ты перестанешь бояться WA.

Идея «на пальцах»

Допустим, у тебя есть умное быстрое решение fast, в котором ты не уверен, и тупое медленное slow (например, полный перебор), в правильности которого сомнений нет. Тогда:

1. Генерируем случайный маленький тест.
2. Прогоняем на нём оба решения.
3. Если ответы разошлись — нашли контрпример! Печатаем его и разбираемся.
4. Повторяем тысячи раз.

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

Полный стресс-тест в действии

Сравним два решения задачи о максимальной сумме подотрезка. Эталон slow — честный перебор всех подотрезков за O(n^2). Быстрое fast — алгоритм Кадане за O(n). Проверим, согласуются ли они на тысяче случайных тестов.

import random

def slow(a):                        # эталон: перебор всех подотрезков O(n^2)
    best = float("-inf")
    for i in range(len(a)):
        s = 0
        for j in range(i, len(a)):
            s += a[j]
            best = max(best, s)
    return best

def fast(a):                        # алгоритм Кадане O(n)
    best = cur = a[0]
    for x in a[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

random.seed(42)
ok = True
for _ in range(1000):
    n = random.randint(1, 8)        # маленькие тесты!
    a = [random.randint(-5, 5) for _ in range(n)]
    if slow(a) != fast(a):          # расхождение = контрпример
        ok = False
        print("РАСХОЖДЕНИЕ на", a, ":", slow(a), "vs", fast(a))
        break
print("Стресс-тест пройден:" if ok else "Найден баг:", ok)

Структура — каркас любого стресс-теста: генератор случайных данных, два решения, сравнение, остановка на первом расхождении. Здесь оба решения верны, поэтому за 1000 тестов расхождений нет — мы убедились, что Кадане корректен. Если бы в fast была опечатка, тест мгновенно выдал бы конкретный массив, на котором всё ломается.

Вывод:

Стресс-тест пройден: True

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

• Маленькие размеры. n от 1 до 8–10: и эталон успевает, и контрпример читаем.
• Покрывай крайности. Включай отрицательные числа, нули, повторы, одинаковые элементы — там и прячутся баги.
• Фиксируй seed (random.seed(...)), чтобы баг воспроизводился.
• Минимизируй контрпример. Нашёл расхождение на n=8? Попробуй уменьшить до n=2–3 — на маленьком тесте причину видно сразу.

Типичные источники багов

Если эталона нет

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

Подводные камни

• Слишком большие тесты. На больших n медленный эталон зависнет, а контрпример будет нечитаемым — держи размеры крошечными.
• Узкий генератор. Если генерируешь только «удобные» данные, баг на краях не всплывёт; добавляй экстремальные случаи.
• Эталон тоже может врать. Убедись, что медленное решение действительно тривиально-верное (полный перебор), иначе сравниваешь два бага.
• Забыл зафиксировать seed — баг «исчезает» при перезапуске; всегда фиксируй.

Итог

• Стресс-тест сравнивает быстрое решение с заведомо верным медленным эталоном на случайных малых тестах.
• Первое расхождение — это конкретный контрпример, который и показывает баг.
• Генерируй маленькие тесты с крайними случаями, фиксируй seed, минимизируй найденный контрпример.
• Это самый надёжный способ ловить WA без доступа к скрытым тестам.