Algorithmica Notebook

Appearance

Debugging Under Pressure ​

A systematic protocol for finding and fixing bugs during a timed contest, when panic is your worst enemy.

Quick Revisit

  • Use when WA / RE / TLE strikes during a contest and you need a protocol instead of panicked random edits.
  • Core invariant: understand first, change second. Every edit must have a hypothesis behind it.
  • This file's unique value is the pressure protocol — when to debug, when to stress test, when to abandon. For the underlying tooling (stress testing setup, debug builds), see Debugging and Stress Testing in Chapter 0; this file does not re-derive it.

Prerequisites: C++ Tips and Workflow, Common Templates

Contents ​

The Debugging Mindset ​

Two programmers hit WA on problem C at minute 47. One starts randomly changing < to <=, swapping +1 and -1, resubmitting after each change. The other stops, re-reads the problem statement, and traces through the failing case by hand. The second programmer finds the bug in 3 minutes. The first one is still flailing at minute 70.

Random changes are not debugging. They are panic wearing a disguise. Every change you make without understanding why is a coin flip that corrupts your mental model of the code.

The core principle:

+----------------------------------------------------------+
|  UNDERSTAND first.  CHANGE second.  Never the reverse.   |
+----------------------------------------------------------+

Three rules for debugging under time pressure:

  1. Stop typing. Your hands got you into this. Your brain gets you out.
  2. Narrow the search space. Is the logic wrong, or is the implementation wrong? These are completely different problems.
  3. One variable at a time. Change one thing, test, observe. Never change two things simultaneously.

Your emotional state matters. When you feel the adrenaline spike after a WA:

  WA verdict
      |
      v
  +-- STOP --+
  |  Breathe |
  |  10 sec  |
  +----------+
      |
      v
  Re-read problem
  statement (yes,
  the WHOLE thing)
      |
      v
  Check sample
  cases by hand
      |
      v
  Apply debug
  protocol below

Step-by-Step Debug Protocol ​

Follow this in order. Do not skip steps.

Step 1: Re-read the problem statement ​

You misread something. Statistically, this is the most common source of bugs in contests. Look for:

  • Output format (are they asking for the answer modulo 109+7?)
  • 1-indexed vs 0-indexed
  • "strictly less than" vs "less than or equal"
  • Constraints you ignored (negative numbers? zero? strings can be empty?)

Step 2: Verify on sample cases by hand ​

Trace through your code on paper (or in your head) using the provided samples. Not "I think it works" -- actually simulate every loop iteration, every variable update. Write down intermediate values.

Example trace for a prefix sum bug:

Input: n=4, a=[3, 1, 4, 1]

Your code computes:
  i=0: pre[0] = a[0] = 3
  i=1: pre[1] = pre[0] + a[1] = 4
  i=2: pre[2] = pre[1] + a[2] = 8
  i=3: pre[3] = pre[2] + a[3] = 9

Query l=1, r=3: pre[r] - pre[l-1] = pre[3] - pre[0] = 9 - 3 = 6
Expected: a[1]+a[2]+a[3] = 1+4+1 = 6  --> OK

Query l=0, r=0: pre[0] - pre[-1] = ???  --> BUG (l=0 edge case)

Step 3: Check edge cases ​

Before anything else, test these inputs mentally or on paper:

  • n=0 (if the constraint allows it)
  • n=1
  • All elements identical
  • Maximum constraint values (overflow?)
  • Minimum values (negative numbers?)

Step 4: Add assertions ​

Assertions are faster than print debugging for catching impossible states. They crash immediately at the point of corruption, not three functions later.

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

// Contest assertion macro -- strips out with -DNDEBUG or just delete before submit
#ifdef LOCAL
    #define ASSERT(cond, msg) \
        if (!(cond)) { \
            cerr << "ASSERT FAIL: " << msg << " at " << __FILE__ << ":" << __LINE__ << endl; \
            abort(); \
        }
#else
    #define ASSERT(cond, msg) ((void)0)
#endif

int main() {
    int n; cin >> n;
    ASSERT(n >= 1, "n must be positive");

    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // ... later in code ...
    int idx = /* some computation */;
    ASSERT(0 <= idx && idx < n, "index out of bounds");

    return 0;
}

Compile locally with: g++ -std=c++20 -DLOCAL -O2 -o sol sol.cpp

Step 5: Print debugging (see section below) ​

Step 6: Stress test (see section below) ​

Step 7: If all else fails -- rewrite from scratch ​

Sometimes the code is so tangled that patching is slower than rewriting. If you have been debugging for 15+ minutes with no progress, consider a clean rewrite. A second implementation takes less time because your understanding is sharper.

Common Bug Categories ​

Know your enemy. These are the bugs that kill you in contests, ordered roughly by frequency.

Off-by-one errors ​

The single most common competitive programming bug.

Symptom: WA on some cases, often small ones.
Locations: loop bounds, array indexing, binary search boundaries.

Wrong:  for (int i = 0; i <= n; i++)   // iterates n+1 times
Right:  for (int i = 0; i < n; i++)    // iterates n times

Wrong:  int lo = 0, hi = n;            // might miss answer at n
Right:  int lo = 0, hi = n + 1;        // depends on search space

Wrong:  pre[r] - pre[l]               // excludes index l
Right:  pre[r] - pre[l - 1]           // includes index l (1-indexed)

Integer overflow ​

Symptom: WA or wrong answers on large inputs. Correct on samples.
Trigger: n up to 2*10^5, values up to 10^9. Product exceeds 2^31-1.

Wrong:  int ans = a[i] * a[j];         // overflows if a[i],a[j] ~ 10^9
Right:  long long ans = (long long)a[i] * a[j];

Wrong:  int sum = 0; for (...) sum += a[i];  // sum of 2*10^5 values ~ 10^14
Right:  long long sum = 0;

Cheat sheet:
  int       -->  up to ~2.1 * 10^9
  long long -->  up to ~9.2 * 10^18

Rule of thumb: if n×max(ai)>2×109, use long long.

Uninitialized variables ​

Symptom: AC locally, WA on judge (or inconsistent results).
Cause: local compiler may zero-initialize, judge's may not.

Wrong:  int dp[MAXN];          // garbage values
Right:  int dp[MAXN] = {};     // zero-initialized (C-style array)
Right:  memset(dp, 0, sizeof dp);
Right:  vector<int> dp(MAXN, 0);

Wrong data type ​

Symptom: WA on large inputs.

Wrong:  int mid = (lo + hi) / 2;       // overflows if lo+hi > 2*10^9
Right:  int mid = lo + (hi - lo) / 2;

Wrong:  double ans = ...;               // precision loss
Right:  long long ans = ...;            // use integers when possible

Array bounds / out of range ​

Symptom: RE (runtime error) or garbage output.

Wrong:  int a[100001];  // but n can be 2*10^5
Right:  int a[200001];

Wrong:  a[n] = x;       // 0-indexed array, valid indices are 0..n-1

Forgetting to reset between test cases ​

This one is a contest killer. Multi-test problems (t test cases) need a clean slate.

cpp
// WRONG -- adj and visited persist across test cases
vector<int> adj[MAXN];
bool visited[MAXN];

void solve() {
    int n, m;
    cin >> n >> m;
    // forgot to clear adj and visited!
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // ...
}

// RIGHT -- explicit reset
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        visited[i] = false;
    }
    // ...
}

Better pattern: declare everything inside solve() using local vectors. If performance allows it, this eliminates the bug entirely.

cpp
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<bool> visited(n + 1, false);
    // ...
}

Quick reference ​

+-------------------------+----------------------------+-------------------+
| Bug Category            | Typical Symptom            | Quick Fix         |
+-------------------------+----------------------------+-------------------+
| Off-by-one              | WA on small cases          | Check loop bounds |
| Integer overflow         | WA on large inputs         | Use long long     |
| Uninitialized vars      | Inconsistent WA/AC         | = {} or memset    |
| Wrong data type         | WA on large inputs         | Cast before mult  |
| Array out of bounds     | RE or garbage              | Check MAXN        |
| Not resetting           | WA on test 2+             | Clear globals     |
| Wrong comparator        | RE (strict weak ordering)  | Use < not <=      |
| Reading input wrong     | WA everywhere              | Re-read format    |
+-------------------------+----------------------------+-------------------+

Cerr is your friend. Cout is the judge's friend. Never mix them up.

The debug macro ​

This macro prints variable names alongside their values. It is the single most useful piece of debugging infrastructure you can have.

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

#ifdef LOCAL
    #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: ", _dbg(__VA_ARGS__)
#else
    #define dbg(...) ((void)0)
#endif

void _dbg() { cerr << endl; }

template <typename T, typename... U>
void _dbg(T t, U... u) {
    cerr << t;
    if constexpr (sizeof...(u)) cerr << ", ";
    _dbg(u...);
}

// Pretty-print containers
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}

int main() {
    int n = 5;
    vector<int> a = {3, 1, 4, 1, 5};
    int x = 42;

    dbg(n, x);          // [n, x]: 5, 42
    dbg(a);             // [a]: [3, 1, 4, 1, 5]
    dbg(a[2], n - 1);   // [a[2], n - 1]: 4, 4

    return 0;
}

Compile with -DLOCAL for debug output. Without it, all dbg() calls compile to nothing -- zero overhead on the judge.

g++ -std=c++20 -DLOCAL -O2 -o sol sol.cpp      # debug build
g++ -std=c++20 -O2 -o sol sol.cpp               # submit build (dbg stripped)

Advanced: debug 2D vectors and sets ​

cpp
#ifdef LOCAL

template <typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
    os << "{";
    bool first = true;
    for (auto& x : s) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator<<(ostream& os, const map<K, V>& m) {
    os << "{";
    bool first = true;
    for (auto& [k, v] : m) {
        if (!first) os << ", ";
        first = false;
        os << k << ": " << v;
    }
    return os << "}";
}

#endif

Targeted debug output ​

When debugging a specific loop iteration or condition:

cpp
for (int i = 0; i < n; i++) {
    // only print when something interesting happens
    if (dp[i] < 0) dbg(i, dp[i]);  // "why is dp negative here?"
}

Stress Testing ​

When you get WA and cannot find the bug by reading code, stress testing is the nuclear option. It always works (given enough time).

Cross-reference. Debugging and Stress Testing covers the full setup, debug build flags, and sanitizers. This section is the abbreviated version focused on contest reuse — keep both files in sync if you change one.

The idea:

+----------+     +----------+     +-----------+
|  gen.cpp |---->| random   |---->|  sol.cpp  |----> output1
| (random  |     | test     |---->| brute.cpp |----> output2
|  input)  |     | case     |     +-----------+
+----------+     +----------+           |
                                        v
                                  output1 == output2 ?
                                  YES: next test
                                  NO:  print failing case, STOP

You need four files:

gen.cpp -- random test generator ​

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

int main(int argc, char* argv[]) {
    mt19937 rng(atoi(argv[1]));  // seed from command line

    int n = rng() % 10 + 1;     // n in [1, 10] (small for brute force)
    cout << n << "\n";

    for (int i = 0; i < n; i++) {
        cout << (int)(rng() % 21) - 10;  // values in [-10, 10]
        if (i + 1 < n) cout << " ";
    }
    cout << "\n";

    return 0;
}

Adapt the generator to match the problem's input format. Keep n small so brute.cpp can handle it.

brute.cpp -- obviously correct brute force ​

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // O(n^2) or O(n^3) brute force -- correctness over speed
    long long ans = /* naive computation */;
    cout << ans << "\n";

    return 0;
}

The brute force must be trivially correct. If you are not 100% sure the brute force is right, the stress test is useless.

sol.cpp -- your actual solution ​

Your contest solution, unchanged.

run.sh -- the stress test driver ​

bash
#!/bin/bash
set -e

g++ -std=c++20 -O2 -o gen gen.cpp
g++ -std=c++20 -O2 -o brute brute.cpp
g++ -std=c++20 -O2 -o sol sol.cpp

for i in $(seq 1 10000); do
    ./gen $i > input.txt
    ./brute < input.txt > out_brute.txt
    ./sol   < input.txt > out_sol.txt

    if ! diff -q out_brute.txt out_sol.txt > /dev/null 2>&1; then
        echo "MISMATCH on seed $i"
        echo "--- Input ---"
        cat input.txt
        echo "--- Brute ---"
        cat out_brute.txt
        echo "--- Sol ---"
        cat out_sol.txt
        exit 1
    fi

    if (( i % 100 == 0 )); then
        echo "Passed $i tests..."
    fi
done

echo "All tests passed."
chmod +x run.sh
./run.sh

Stress testing tips ​

  • Keep n small (5-15). The brute force needs to finish instantly and you want to find bugs fast, not prove correctness on huge inputs.
  • Seed from the loop counter so failures are reproducible. Seed 4817 fails? Run ./gen 4817 > input.txt and debug that specific case.
  • Match the problem constraints. If the problem says ai≥1, do not generate negative values.
  • For interactive / special judge problems, stress testing is harder. Consider writing a checker instead of using diff.

Minimal inline stress test ​

If setting up four files feels too slow mid-contest, embed a stress test in your solution:

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

long long brute(vector<int>& a) {
    // O(n^2) brute force
    long long ans = 0;
    int n = a.size();
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            ans = max(ans, /* ... */);
    return ans;
}

long long solve(vector<int>& a) {
    // your O(n log n) solution
    // ...
    return 0;
}

void stress() {
    mt19937 rng(42);
    for (int t = 0; t < 100000; t++) {
        int n = rng() % 10 + 1;
        vector<int> a(n);
        for (auto& x : a) x = rng() % 21 - 10;

        long long r1 = brute(a);
        long long r2 = solve(a);
        if (r1 != r2) {
            cerr << "FAIL: n=" << n << " a=";
            for (int x : a) cerr << x << " ";
            cerr << "\nbrute=" << r1 << " sol=" << r2 << endl;
            abort();
        }
    }
    cerr << "Stress test passed." << endl;
}

int main() {
#ifdef LOCAL
    stress();
    return 0;
#endif
    // normal solution I/O
    int n; cin >> n;
    // ...
}

Edge Case Checklist ​

Before submitting, mentally test these. If any apply to the problem and you have not considered them, you probably have a bug.

+----+-------------------------------+-------------------------------+
| #  | Edge Case                     | Why It Breaks Code            |
+----+-------------------------------+-------------------------------+
|  1 | n = 0                         | Empty loops, empty vectors,   |
|    |                               | division by zero in averages  |
+----+-------------------------------+-------------------------------+
|  2 | n = 1                         | Loops that assume n >= 2,     |
|    |                               | accessing a[i-1] at i=0       |
+----+-------------------------------+-------------------------------+
|  3 | All elements identical        | Algorithms that assume         |
|    |                               | distinct values, wrong         |
|    |                               | binary search behavior        |
+----+-------------------------------+-------------------------------+
|  4 | Maximum values (a_i = 10^9,   | Integer overflow in products  |
|    | n = 2*10^5)                   | or sums                       |
+----+-------------------------------+-------------------------------+
|  5 | Negative numbers              | Wrong behavior in modular     |
|    |                               | arithmetic, abs() on INT_MIN  |
+----+-------------------------------+-------------------------------+
|  6 | n = max constraint            | TLE from O(n^2) sneaking in,  |
|    |                               | MLE from large allocations    |
+----+-------------------------------+-------------------------------+
|  7 | Answer is 0 or empty          | Printing nothing vs "0" vs    |
|    |                               | "-1", uninitialized answer    |
+----+-------------------------------+-------------------------------+
|  8 | Strings: empty string, single | s.size()-1 underflows when    |
|    | character, all same character | size() is 0 (unsigned!)       |
+----+-------------------------------+-------------------------------+
|  9 | Graph: disconnected, self-    | BFS/DFS misses components,    |
|    | loops, multiple edges         | double-counting edges         |
+----+-------------------------------+-------------------------------+
| 10 | Tree: star graph, chain       | Recursion depth for chain     |
|    | (path graph)                  | --> stack overflow on DFS     |
+----+-------------------------------+-------------------------------+

The string size trap deserves special attention:

cpp
string s;
cin >> s;

// WRONG: s.size() is unsigned. If s is empty, s.size()-1 wraps to 2^64-1
for (int i = 0; i < s.size() - 1; i++) { ... }

// RIGHT: cast to int
for (int i = 0; i < (int)s.size() - 1; i++) { ... }

// Also RIGHT: use ssize() in C++20
for (int i = 0; i + 1 < ssize(s); i++) { ... }

When to Abandon ​

Not every WA is an implementation bug. Sometimes your approach is wrong. Knowing the difference saves contest time.

Signs your approach is wrong ​

  • You cannot prove correctness, even informally. ("I think greedy works here" is not a proof.)
  • You found a counterexample to your algorithm (not your code).
  • The expected complexity does not match the constraints. (n=106 but your approach is O(nn)... suspicious.)
  • You have been debugging for 20+ minutes and every fix reveals a new problem. This is a symptom of a fundamentally flawed approach, not bad typing.

Signs it is an implementation bug ​

  • Your algorithm is correct on paper / for small cases but WA on the judge.
  • The stress test finds a failing case and you can see why the code diverges from the brute force.
  • The bug is in a specific section (e.g., "the binary search finds the wrong boundary").

The decision flowchart ​

  Been debugging > 15 min?
      |
      +-- NO --> Keep debugging, follow the protocol.
      |
      +-- YES
           |
           Can you construct a counterexample
           to your ALGORITHM (not code)?
               |
               +-- YES --> Abandon approach. Think of new algorithm.
               |
               +-- NO
                    |
                    Does stress test find a failure?
                        |
                        +-- YES --> Bug is in code. Trace the failing case.
                        |           Consider rewrite if code is tangled.
                        |
                        +-- NO (passes thousands of small tests)
                             |
                             Likely an edge case or overflow on large inputs.
                             Check: long long? n=0? reset between test cases?

Time allocation rule of thumb ​

+--------------------------------------------+
|  Contest time remaining    Action           |
+--------------------------------------------+
|  > 60 min                 Debug patiently   |
|  30-60 min                Stress test or    |
|                           rewrite, not both |
|  < 30 min                 Try another       |
|                           problem instead   |
+--------------------------------------------+

The hardest skill in competitive programming is not solving problems. It is knowing when to stop solving one.

What the Code Won't Teach You ​

Insights drawn from reflection notes

The debugging protocol matters more than the techniques. The right order: (1) form a hypothesis about what's wrong, (2) design a test to confirm or deny it, (3) apply the smallest fix that addresses the confirmed hypothesis. Jumping to step 3 without 1 and 2 is the "random-change" pattern in disguise.

When to scrap and restart. Sometimes the code is too tangled to debug efficiently. Rewriting from scratch -- keeping the algorithm but starting from a clean template -- feels like losing time but often saves it. Signal: 20+ minutes debugging with no hypothesis about the root cause.

Mental state directly affects debugging performance. Tilt makes you miss bugs you'd catch immediately when calm. Explicit protocol: stop coding, re-read problem statement, take a breath, only then return to debugging.

  THE CORRECT DEBUGGING LOOP:

  WA / RE / TLE
       │
       ▼
  Reproduce: what input causes the failure?
  (stress test or minimize manually)
       │
       ▼
  Observe: what output do you get vs expect?
       │
       ▼
  Hypothesize: what code path produces
  this SPECIFIC wrong output?
       │
       ▼
  Verify: add cerr, trace through hypothesis
       │
       ▼
  Fix: ONE targeted change for verified cause
       │
       ▼
  Test: does fix work? Does it break other cases?
       │
       ▼
  ┌── Still wrong? ──► back to Reproduce
  │
  └── Fixed ──► Submit
  BUG TRIAGE BY VERDICT:

  ┌──────────┬──────────────────────────────────────┐
  │ Verdict  │ Most likely cause + action            │
  ├──────────┼──────────────────────────────────────┤
  │ RE       │ Array OOB, recursion depth, bad ptr   │
  │          │ -> check indices, add bounds assertions │
  ├──────────┼──────────────────────────────────────┤
  │ TLE      │ Wrong complexity, infinite loop,      │
  │          │ wrong n, heavy constant               │
  │          │ -> count operations, check loop bounds  │
  ├──────────┼──────────────────────────────────────┤
  │ WA pre 1 │ Misread problem statement             │
  │          │ -> re-read the FULL statement          │
  ├──────────┼──────────────────────────────────────┤
  │ WA pre5+ │ Edge case (n=1, overflow, all same)   │
  │          │ -> test edge cases manually            │
  ├──────────┼──────────────────────────────────────┤
  │ WA judge │ Rare bug, only on adversarial input   │
  │ (not     │ -> stress test is the only reliable    │
  │ samples) │   method                              │
  └──────────┴──────────────────────────────────────┘

Mental Traps ​

Integrated from reflection notes

Trap: "I'll just look more carefully."

Staring has diminishing returns after the first few minutes. Your brain forms a mental model of the code -- and that model is what's wrong. The fix is to test the code against examples, not stare at it harder.

Trap: "This bug must be in the tricky part."

Bugs are often in the boring parts: off-by-one in loop bounds, wrong variable reuse, wrong input reading order. Experienced debuggers check the boring parts first.

Trap: "Stress testing takes too long to set up."

5-10 minutes setup vs 30-60 minutes manual debugging. The time investment in a stress test is always positive for non-trivial bugs.

Trap: "I'll fix this bug, then I can stop."

Often there are two bugs. Fixing one reveals another. This is normal -- not a reason to assume your approach is wrong.

Trap: "The bug is in the code, not the problem statement."

Educational Round 142, problem D. WA on test 5. You spend 12 minutes adding debug output, re-reading code, changing nothing. Then you re-read the problem statement and discover you missed "the array is 1-indexed." One line fix: change a[i] to a[i+1]. Always re-read the problem before debugging the code. The first hypothesis to check, every time, is that you misunderstood the problem -- not that your implementation is broken.

Self-Test ​

Drawn from reflection notes

  • [ ] Recall your last 3 contest bugs. For each: was it found by random change, careful reading, print statements, or stress test? Which method was fastest? Calibrate your default debugging approach accordingly.

  • [ ] Practice hypothesis formation. Take a wrong solution to a previous problem. Before adding debug output, write: "I believe the bug is X because Y." Verify. How often is your first hypothesis correct?

  • [ ] Time yourself setting up a minimal stress test from scratch (brute + gen + run.sh). Target: under 7 minutes. If slower, practice until automatic.

  • [ ] Identify your tilt tells. What do you do when frustrated that degrades debugging? (Common: random code changes, re-reading same code, skipping test cases.) Name it so you can catch it happening.

  • [ ] Smallest failing input drill. Take any WA solution and -- without looking at the code -- construct the smallest input that reproduces the wrong answer. Practice until this is reflexive.

Built for the climb from Codeforces 1100 to 2100.

Algorithmica Notebook