Стресс-тестирование

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

Правильный ход здесь не «думать сильнее», а найти конкретный тест, на котором ломается. Делается это механически.

Нужны три вещи:

1. Быстрое решение — то, которое не работает.
2. Медленное решение — заведомо верное, пусть даже за $O(n!)$.
3. Генератор маленьких случайных тестов.

Дальше в цикле: сгенерировали тест, прогнали оба решения, сравнили. Разошлись — вот он, тест.

flowchart LR
    G["генератор<br/>маленький тест"] --> F["быстрое<br/>решение"]
    G --> S["медленное<br/>решение"]
    F --> C{"равны?"}
    S --> C
    C -->|да| G
    C -->|нет| P["печатаем тест<br/>и останавливаемся"]

Всё в одной программе

Самый простой способ — оформить оба решения функциями и сравнивать прямо в main. Никаких файлов и скриптов.

#include <bits/stdc++.h>
using namespace std;

vector<int> fast(vector<int> a) { /* ваше решение */ }
vector<int> slow(vector<int> a) { /* заведомо верное */ }

int main() {
    mt19937 rng(12345);
    for (int test = 1; test <= 100000; test++) {
        int n = rng() % 8 + 1;
        vector<int> a(n);
        for (int& value : a) value = rng() % 10;

        vector<int> got = fast(a), want = slow(a);
        if (got != want) {
            cout << "тест " << test << " провален\n" << n << "\n";
            for (int value : a) cout << value << ' ';
            cout << "\nполучено:  "; for (int value : got)  cout << value << ' ';
            cout << "\nожидалось: "; for (int value : want) cout << value << ' ';
            return 0;
        }
        if (test % 20000 == 0) cerr << "пройдено " << test << '\n';
    }
    cout << "расхождений не найдено\n";
}

На реальной ошибке — пузырьковая сортировка, у которой внешний цикл на одну итерацию короче, — этот стресс находит тест на третьей итерации:

тест 3 провален
6
5 6 5 7 6 3
получено:  5 3 5 6 6 7
ожидалось: 3 5 5 6 6 7

Шесть чисел, и по ним сразу видно, что тройка не доехала до начала. Час размышлений над кодом такого не даёт.

Почему тесты должны быть маленькими

Соблазн генерировать $n = 1000$ понятен: «там больше шансов поймать». Это ошибка.

Во-первых, ловится всё равно и на $n = 5$: почти любая ошибка проявляется на крошечных данных. Во-вторых, на большом тесте вы не увидите что именно пошло не так — придётся ещё уменьшать его вручную.

Практическое правило: $n$ до 8, значения до 10. Если за сто тысяч тестов ничего не нашлось — тогда увеличивайте.

То же и про значения. Если в задаче есть равные элементы, генератор со значениями до $10^9$ их почти никогда не создаст. Маленький диапазон значений даёт коллизии, дубликаты, вырожденные случаи — именно то, на чём решения и падают.

Фиксированный сид

mt19937 rng(12345) — сид задан явно и намеренно. Это значит, что при повторном запуске получится та же последовательность тестов.

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

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

Отдельно: rand() для этого не годится. Он даёт мало разных значений, плохо перемешан, и на некоторых компиляторах RAND_MAX равен 32767. mt19937 есть в <random> и лучше во всём.

Медленное решение, которого нет

Частое возражение: «а если я не знаю, как решать задачу правильно?»

Обычно знаете. Медленное решение — это полный перебор: все перестановки, все подмножества, рекурсия без отсечений. Оно пишется за пять минут и на $n = 8$ работает мгновенно.

sort(a.begin(), a.end());
do {
    // проверяем эту перестановку
} while (next_permutation(a.begin(), a.end()));

next_permutation перебирает перестановки в лексикографическом порядке и возвращает false, когда возвращается к началу, — поэтому массив надо предварительно отсортировать, иначе часть перестановок не переберётся.

Перебор подмножеств — через битовые маски:

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++)
        if (mask >> i & 1) { /* i-й элемент взят */ }
}

Когда медленного решения действительно нет

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

Примеры проверок, которые не требуют второго решения:

• ответ — перестановка? проверьте, что все числа от 1 до $n$ на месте;
• ответ — расстановка? проверьте, что она удовлетворяет всем ограничениям условия;
• задача про максимум? проверьте, что найденное значение достижимо, и отдельно — что $+1$ недостижимо;
• решение просто падает? стресса против чего-либо вообще не нужно, достаточно найти вход, на котором оно упало.

Это называется проверкой чекером, и обычно она пишется даже проще, чем перебор.

Ловля превышения времени

Для «слишком долго» второе решение не нужно вовсе. Нужен генератор максимального теста и замер.

clock_t start = clock();
solve(a);
double ms = 1000.0 * (clock() - start) / CLOCKS_PER_SEC;
cerr << ms << " мс\n";

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

И помните про запас: если локально решение работает секунду при лимите в секунду, на сервере оно не пройдёт. Ориентируйтесь на половину лимита.

Через отдельные процессы

Когда решения нельзя оформить функциями — например, они на разных языках или сильно завязаны на ввод-вывод, — стресс делают скриптом.

for i in $(seq 1 10000); do
  python3 gen.py $i > test.txt
  ./fast < test.txt > out_fast.txt
  ./slow < test.txt > out_slow.txt
  if ! diff -q out_fast.txt out_slow.txt > /dev/null; then
    echo "провал на тесте $i"; cat test.txt; break
  fi
done

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

Способ универсальнее, но медленнее: запуск процесса стоит миллисекунды, и десять тысяч итераций займут минуту вместо секунды. Начинайте с варианта «всё в одной программе».

Что стресс не найдёт

Честная оговорка. Стресс сравнивает два ваших решения. Если оба построены на одной неверной идее, они согласятся друг с другом, и стресс скажет «расхождений не найдено».

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