Debugging under time pressure

Why this matters when you build with AI

When a submission gets a wrong answer, the easiest move is to paste the code into an AI assistant and ask "what is wrong". The assistant will return a confident change. Often the change fixes the sample and breaks something else, because the assistant never saw the input that fails. You then have two bugs and less time.

The fix is a routine you run in the same order every time, and a rule that you never ask for help without a failing input. A failing input is a small input where your program's output is different from the correct output. Once you have one, the bug is a question with an answer, not a mystery.

AI tools are useful here. They are good at naming a common bug once you show them the failing input, the expected output and the actual output. They are poor at finding a bug from the verdict alone, and they will often propose a "fix" that they did not test. Your job is to hand them a small failing case and to check any change against it yourself.

The idea: a fixed routine

Debugging under pressure works when you do not decide what to do next from scratch each time. Use this order:

1. Reread the statement. Many bugs are a misread constraint. Is a value allowed to be negative? Is k allowed to be 1? Are indices 1-based?
2. Check limits and types. Write the largest value of each variable and check that the type holds it. Watch for int sums and for % on negative numbers.
3. Hand-test a small case. Make a two- or three-element input, compute the answer on paper, and run the program on it.
4. Stress test against a brute force. Generate many small random inputs, run the program and a brute force on each, and stop at the first mismatch. The brute force must be simple enough to trust.
5. Shrink the failing input. Find the smallest input that still fails. Small inputs are easy to trace by hand.
6. Print the state. At the failing point, print the variables the bug touches, using standard error so the judge output is not changed.
7. Fix, then rerun steps 3 to 5. Rerun the samples and the stress test after every change, not only the test that failed.

Some terms used below. A verdict is the judge's result for a submission, such as "wrong answer on test 7". A generator is a program that prints a random input. A stress test is a loop that runs the program and the brute force on generated inputs and compares the outputs. A minimal failing input is a failing input that no smaller input can beat, in the order you chose (fewest numbers, then smallest values). Standard error (cerr in C++) is a second output stream that the judge usually ignores, so printing to it is a safe way to log state during a test.

Worked example: pairs with the same remainder

The problem

You get n numbers a_1, ..., a_n, which can be negative, and an integer k with 1 <= k <= 10^9. Count the pairs i < j for which a_i - a_j is divisible by k.

Input: the first line holds n and k. The second line holds the n numbers.

The natural solution is to group numbers by their remainder modulo k. Two numbers form a pair when their remainders match. Here is the program a contestant might submit:

// Count pairs i < j with a[i] - a[j] divisible by k.
// Input: n k, then n integers (can be negative).
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
 
    map<long long, long long> cnt;   // remainder -> how many seen so far
    long long ans = 0;
    for (long long x : a) {
        long long r = x % k;         // bug: negative x gives a negative remainder
        ans += cnt[r];
        cnt[r]++;
    }
    cout << ans << "\n";
    return 0;
}

The bug is on the line marked with a comment. The rest of the code is fine. This is the kind of bug a fast reread can miss, because the code looks right.

Step 1 and 2: reread and check the types

The statement says the numbers can be negative. That is the first clue. In C++, the % operator keeps the sign of the left side, so -1 % 3 is -1, not 2. The remainder of -1 and the remainder of 2 are then different keys in the map, even though -1 and 2 differ by 3. So the program never counts that pair.

Step 3: a hand test

Pick a small input with a negative number and compute the answer on paper. Take n = 2, k = 3, and the numbers -1 and 2. The difference is -1 - 2 = -3, which is divisible by 3, so the answer is 1.

Run it:

input: 2 3 / -1 2
wrong=0 correct=1 brute=1

The hand answer is 1, and the wrong program prints 0. That is enough to know there is a bug. It does not tell you the smallest case, so you still need the stress test.

Step 4: a stress test

The brute force checks every pair directly. Python's % always gives a result between 0 and k-1 for k > 0, so this brute force does not share the bug.

import sys
 
# Brute force: check every pair. Python's % is never negative for k > 0.
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
count = 0
for i in range(n):
    for j in range(i + 1, n):
        if (a[i] - a[j]) % k == 0:
            count += 1
print(count)

The generator picks small values, including negative ones, so the stress test can see the bug:

import random
import sys
 
# Usage: python3 gen.py SEED > input.txt
# 1 to 6 numbers, values from -6 to 6, k from 1 to 4.
random.seed(int(sys.argv[1]))
n = random.randint(1, 6)
k = random.randint(1, 4)
print(n, k)
print(*[random.randint(-6, 6) for _ in range(n)])

The stress loop stops at the first mismatch:

#!/usr/bin/env bash
# Stress loop: random tests of wrong against brute, stop at the first mismatch.
cd "$(dirname "$0")" || exit 1
for seed in $(seq 1 1000); do
  python3 gen.py "$seed" > in.txt
  want=$(python3 brute.py < in.txt)
  got=$(./wrong < in.txt)
  if [ "$want" != "$got" ]; then
    echo "first mismatch at seed $seed (after $seed tests)"
    echo "input:"; cat in.txt
    echo "brute=$want wrong=$got"
    exit 0
  fi
done
echo "no mismatch in 1000 tests"

Real output on my machine:

first mismatch at seed 3 (after 3 tests)
input:
2 2
-1 3
brute=1 wrong=0

Here the input is n = 2, k = 2, numbers -1 and 3. The two numbers differ by 4, which is divisible by 2. The brute force says 1, the program says 0.

The stress test found this input on the third try. Keep the generator's seed in your notes so you can regenerate the same input later.

Step 5: shrink the input

A failing input with 6 numbers is hard to trace. Search small inputs, smallest first. Order the candidates by the number of numbers, then by the total size of the numbers, then by k.

import itertools
import subprocess
 
# Try every tiny input (n <= 2, k <= 4, values -3..3), smallest first:
# fewer numbers, then smaller total size of the numbers, then smaller k.
def run(cmd, text):
    return subprocess.run(cmd, input=text, capture_output=True, text=True).stdout.strip()
 
cases = []
for n in range(1, 3):
    for k in range(1, 5):
        for vals in itertools.product(range(-3, 4), repeat=n):
            cases.append((n, sum(abs(v) for v in vals), k, vals))
cases.sort()
 
for n, _, k, vals in cases:
    text = f"{n} {k}\n{' '.join(map(str, vals))}\n"
    want = run(["python3", "brute.py"], text)
    got = run(["./wrong"], text)
    if want != got:
        print("smallest failing input:")
        print(text, end="")
        print("brute =", want, " wrong =", got)
        break

Real output:

smallest failing input:
2 2
-1 1
brute = 1  wrong = 0

The input -1 and 1 with k = 2 is the same bug as before. The shrink step gave you a case you can check by hand in one line: -1 - 1 = -2, which is divisible by 2.

Step 6: print the state

When the hand test is not enough to see why, print the variables that the bug touches. Print to cerr, so the program output stays the same:

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long k = 3;
    for (long long x : {-1LL, 2LL}) {
        cerr << "x=" << x << " x%k=" << x % k << " fixed=" << ((x % k) + k) % k << "\n";
    }
    return 0;
}

Real output:

x=-1 x%k=-1 fixed=2
x=2 x%k=2 fixed=2

The state shows the problem. The two numbers have the same true remainder, 2, but the program stores them under the keys -1 and 2. Once you see that, the fix is clear.

Step 7: fix and retest

The fix is to shift the remainder into the range 0 to k-1:

long long r = ((x % k) + k) % k;  // always 0..k-1

The rest of the program does not change. Run the hand test again: the fixed program prints 1 on 2 3 / -1 2, which matches the brute force. Then run the full stress loop on the fixed program:

no mismatch in 1000 tests

Note that this run uses a freshly compiled binary. Compile with g++ -O2 -std=c++17 -Wall -Wextra -o correct correct.cpp and point the stress script at that binary.

Complexity

The map version runs in O(n log n). A version with an array of size k would run in O(n + k), but only when k is small. Remember that k can be up to 10^9 in the statement, so an array of size k is not always an option.

A common variant uses vector<int> cnt(k) indexed by the remainder. With a negative remainder, that index is negative. In C++ that is undefined behaviour. I did not run that variant, so I cannot tell you its output. It may crash, print a wrong number, or print the right number, and the outcome may change with the compiler. The fix is the same: make the remainder non-negative first.

Common mistakes

Editing at random. The symptom is a submission that changes its wrong answer to a different wrong answer after each edit. Stop, and go back to step 3: write down one small failing input and its expected output before you change any code.

Trusting the samples. The samples often do not contain a negative number, a k of 1, or a sum that overflows. A program can pass every sample and still fail. Always run the stress loop.

A generator that is too narrow. If the generator only makes positive numbers, the pair-counting bug above never shows. This is worth checking when a stress test is silent but the verdict says wrong answer. Print a few generated inputs and ask whether they contain the case the statement allows.

A brute force that shares the bug. If the brute force computes the remainder with the same % expression as the program, both can be wrong in the same way. Use the simplest form of the check you can, such as a direct comparison of differences, and check it on a hand-computed case.

Printing debug output to stdout. The symptom is a wrong answer on a test that the program passed locally, because the extra line of debug text is in the output. Print debug state to cerr, and delete the lines before you submit.

Forgetting to recompile. The symptom is a fixed program that prints the old answer during the stress test. Rebuild the binary after each change, or the stress loop runs the old file.

Off-by-one with indices. The symptom is an answer that is off by one, or a crash near the end of the array. Check whether the statement's indices start at 1 or 0, and write the loop bounds on paper.

Hands-on exercise

Use the programs and scripts in this lesson. Create a folder for the exercise, and put the generator, the brute force and the stress loop from the worked example in it. Then do the following.

Exercise 1: find the minimal failing input for a second bug

The program below counts subarrays (contiguous runs of numbers) whose sum is divisible by k. It has a bug. The generator and brute force for this exercise use only positive numbers, so the negative-remainder bug from the worked example cannot appear.

// Practice program: count subarrays whose sum is divisible by k.
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; long long k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    map<long long, long long> seen;   // remainder of prefix sum -> count
    long long pref = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        pref = (pref + a[i]) % k;
        ans += seen[pref];
        seen[pref]++;
    }
    cout << ans << "\n";
    return 0;
}

Write the generator and the brute force for it, run the stress loop, and find the smallest failing input by hand or with a shrink step. Then predict the program's output on that input before you run it.

The generator and brute force for the exercise:

import random
import sys
 
# Usage: python3 gen_sub.py SEED > input.txt
# 1 to 6 positive numbers, values 1 to 5, k from 1 to 4.
random.seed(int(sys.argv[1]))
n = random.randint(1, 6)
k = random.randint(1, 4)
print(n, k)
print(*[random.randint(1, 5) for _ in range(n)])

import sys
 
# Brute force: check every subarray, sum it directly.
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
count = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        if sum(a[i:j]) % k == 0:
            count += 1
print(count)

Show the answer

The first failing seed in the loop is 2 1 / 3 1: n = 2, k = 1, numbers 3 and 1. The brute force prints 3 (every subarray has a sum divisible by 1), and the program prints 1.

The smallest failing input is 1 1 / 1: one number, k = 1. The brute force prints 1. The program prints 0.

The bug is that the map starts empty. The empty prefix (sum 0, before any number) is never counted, so a subarray that starts at the first number is never counted when its prefix remainder is 0. The fix is one line before the loop:

seen[0] = 1;   // the empty prefix has remainder 0

With the fix, the program prints 1 on 1 1 / 1, 6 on 3 3 / 3 3 3 (brute force also gives 6), and 3 on 3 3 / 1 2 3 (brute force also gives 3). The stress loop on the fixed program prints no mismatch in 1000 tests.

Exercise 2: write an edge-case generator

The random generator above rarely produces the largest values or the smallest n. Write a second generator that prints a random input with n equal to 1 with probability one half, and k equal to 1 with probability one half. Explain in one sentence which of the two bugs in this lesson each choice is meant to expose.

Show the answer

One good version:

import random
import sys
 
random.seed(int(sys.argv[1]))
n = 1 if random.random() < 0.5 else random.randint(1, 6)
k = 1 if random.random() < 0.5 else random.randint(2, 4)
print(n, k)
print(*[random.randint(-6, 6) for _ in range(n)])

Setting n = 1 exposes the empty-prefix bug in exercise 1, because a single number is the smallest subarray. Setting k = 1 exposes the same bug, since every sum is divisible by 1. The negative values stay in the generator so the first worked example still runs.

Exercise 3: why stdout breaks the judge

A program prints cout << "debug: " << x << "\n"; inside its main loop, and passes all local tests when you run it by hand. On the judge it gets wrong answer on test 1. Give the most likely cause and the fix.

Show the answer

The judge compares the whole output with the expected output, so the extra debug: lines make the output wrong. The fix is to print debug state to cerr, or to remove the line before submitting. If the program has to run through a stress loop that reads stdout, use cerr for the debug lines.

Exercise 4: write a bug report for an AI assistant

Write a short prompt you could paste into an AI assistant after a wrong answer. It must include the failing input, the expected output and the actual output, and it must not ask the assistant to rewrite everything.

My program prints the wrong answer on this input:
<paste the failing input here, one line per row>
Expected output: <expected>
My output: <actual>
Here is the code:
<paste the code>
Find the line that causes this, explain why in two sentences, and change only that line.
Do not change the input format or the output format.

Show the answer

A good prompt has the three parts (input, expected output, actual output), and it asks for one change. A good reply names the line, says why the value is wrong for this input, and proposes a change you can test against the same input. Check the reply the same way you check any change: rerun the hand test, then the stress loop. A reply that changes several lines, or that does not explain the failing input, is not safe to submit.

Checklist

• Start from a failing input, not from the verdict.
• Reread the statement and list every value that can be negative, zero, or at its limit.
• Write the largest value each variable can reach and check its type.
• Hand-compute the answer for a small input before you run the program.
• Run a stress test against a brute force written in the simplest form you trust.
• Shrink the failing input to the smallest case you can trace by hand.
• Print the state that the bug touches, to cerr, and remove the prints before you submit.
• Recompile, then rerun the samples, the hand test and the stress loop after every change.

Summary

A failing submission is a small question with a small answer, once you have a failing input. The routine is the same each time: reread, check types, hand-test, stress test, shrink, print state, fix and retest. The pair-counting bug shows how a negative number turns a correct-looking % into a wrong key, and the stress loop finds it in three tries.