Appendix F: Debugging Guide — Common Bugs & How to Fix Them

💡 Why This Appendix? Even correct algorithmic thinking fails when bugs slip through. This guide is a systematic catalogue of the most common bugs in competitive programming C++ code, organized by category. Bookmark it and check here first when your solution gives WA (Wrong Answer), TLE (Time Limit Exceeded), RE (Runtime Error), or MLE (Memory Limit Exceeded).

F.1 Integer Overflow

The most common source of Wrong Answer in C++.

Problem: int is Too Small

int holds values up to ~2.1 × 10⁹ (≈ 2 × 10⁹). Many problems exceed this.

// ❌ WRONG: n*n can overflow when n = 10^5
int n = 100000;
int result = n * n;  // = 10^10 → overflows int (max ~2×10^9)!

// ✅ CORRECT: cast to long long before multiplication
long long result = (long long)n * n;  // = 10^10, fits in long long
// OR:
long long n_ll = n;
long long result2 = n_ll * n_ll;

When to Use long long

Dangerous Operations

// ❌ Overflow examples:
int a = 1e9, b = 1e9;
cout << a + b;     // overflow (answer > INT_MAX)
cout << a * 2;     // overflow
cout << a * a;     // catastrophic overflow

// ❌ Comparison overflow:
if (a * b > 1e18) ...  // a*b itself may have overflowed!

// ✅ Safe versions:
cout << (long long)a + b;
cout << (long long)a * 2;
cout << (long long)a * a;
if ((long long)a * b > (long long)1e18) ...  // compare as long long

INF Value Choice

// ❌ WRONG: Using INT_MAX as infinity in Dijkstra
const int INF = INT_MAX;
if (dist[u] + w < dist[v]) ...  // dist[u] + w OVERFLOWS if dist[u]=INT_MAX!

// ✅ CORRECT: Use a safe sentinel
const long long INF = 1e18;   // for long long distances
const int INF_INT = 1e9;       // for int distances (leave headroom for addition)

F.2 Off-By-One Errors

The second most common source of WA.

Array Indexing

// ❌ WRONG: Array out of bounds (accessing index n)
int A[n];
for (int i = 0; i <= n; i++) cout << A[i];  // A[n] is undefined!

// ✅ CORRECT
for (int i = 0; i < n; i++) cout << A[i];   // indices 0..n-1
// OR (1-indexed):
for (int i = 1; i <= n; i++) cout << A[i];  // indices 1..n

Prefix Sum Formula

// ❌ WRONG: Off-by-one in range sum
// sum(L, R) should be P[R] - P[L-1], NOT P[R] - P[L]
cout << P[R] - P[L];    // missing element A[L]!

// ✅ CORRECT
cout << P[R] - P[L-1];  // P[0]=0 handles the L=1 case correctly

Binary Search Boundaries

// Finding first index where A[i] >= target (lower_bound behavior):

// ❌ WRONG: Common binary search mistakes
int lo = 0, hi = n - 1;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (A[mid] < target) lo = mid;      // BUG: should be lo = mid + 1
    else hi = mid - 1;                   // BUG: should be hi = mid
}

// ✅ CORRECT: Standard lower_bound template
int lo = 0, hi = n;  // hi = n (not n-1!) to allow "not found" answer
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (A[mid] < target) lo = mid + 1;  // target is in [mid+1, hi]
    else hi = mid;                       // target is in [lo, mid]
}
// lo = hi = first index with A[i] >= target; lo=n means not found

Loop Bounds

// ❌ Common mistake: loop runs one too few or many times
for (int i = 1; i < n; i++) ...    // misses i=n if you meant i=0 to n-1
for (int i = 0; i <= n-1; i++) ... // OK but confusing; prefer i < n

// DP table filling: check if the recurrence accesses i-1
// ❌ If dp[i] uses dp[i-1], and i starts at 0, then dp[-1] is undefined!
for (int i = 0; i <= n; i++) {
    dp[i] = dp[i-1] + ...;  // BUG when i=0: dp[-1]!
}

// ✅ Start at i=1, or initialize dp[0] as base case separately
dp[0] = BASE_CASE;
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i-1] + ...;  // safe: dp[i-1] always valid
}

F.3 Uninitialized Variables

// ❌ WRONG: dp array not initialized
int dp[1005][1005];  // contains garbage values in C++!
// dp[i][j] might be non-zero from previous test cases or OS memory

// ✅ CORRECT options:
// Option 1: memset (fills bytes, use 0 or 0x3f for near-infinity)
memset(dp, 0, sizeof(dp));          // fills with 0
memset(dp, 0x3f, sizeof(dp));       // fills with ~1.06e9 (useful as "infinity" for int)

// Option 2: vector with explicit initialization
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

// Option 3: fill
fill(dp, dp + n, 0);

// ⚠️ WARNING: memset(dp, -1, sizeof(dp)) fills each BYTE with 0xFF
// For int: 0xFFFFFFFF = -1 (works for "unvisited" marker)
// For long long: 0xFFFFFFFFFFFFFFFF = -1 (also works)
// But memset(dp, 1, sizeof(dp)) gives 0x01010101 = 16843009, not 1!

Global vs Local Arrays

// Global arrays are zero-initialized by default in C++
// Local (stack) arrays are NOT initialized

int globalArr[100005];     // ✅ initialized to 0
int globalDP[1005][1005];  // ✅ initialized to 0

int main() {
    int localArr[1000];    // ❌ NOT initialized (garbage values)
    int localDP[100][100]; // ❌ NOT initialized
    
    // Tip: Declare large arrays globally to avoid stack overflow AND ensure init
}

F.4 Stack Overflow (Recursion Too Deep)

// C++ default stack size is typically 1-8 MB
// Deep recursion can exceed this → Runtime Error (segfault)

// ❌ Dangerous: DFS/recursion on tree of depth 10^5
void dfs(int u) { dfs(children[u]); }  // stack overflow for long chains!

// ✅ FIX 1: Convert to iterative using explicit stack
void dfs_iterative(int start) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        for (int v : children[u]) st.push(v);
    }
}

// ✅ FIX 2: Increase stack size (platform-specific, contest judges often allow this)
// On Linux, compile and run with: ulimit -s unlimited && ./sol

// Rule of thumb:
// Recursion depth up to ~10^4: usually safe
// Recursion depth up to ~10^5: risky, consider iterative
// Recursion depth up to ~10^6: almost certainly stack overflow → use iterative

F.5 Modular Arithmetic Bugs

// When the problem asks for answer mod 10^9+7:
const int MOD = 1e9 + 7;

// ❌ WRONG: Forgot to mod, result overflows long long
long long dp = 1;
for (int i = 0; i < n; i++) dp *= A[i];  // overflows after ~18 large multiplications!

// ❌ WRONG: Subtraction underflow (result is negative mod)
long long ans = (a - b) % MOD;  // if a < b, result is negative in C++!

// ✅ CORRECT: Add MOD before taking mod of a subtraction
long long ans = ((a - b) % MOD + MOD) % MOD;  // guaranteed non-negative

// ❌ WRONG: Forgetting to mod intermediate values in DP
dp[i][j] = dp[i-1][j] + dp[i][j-1];  // can overflow if iterations are many

// ✅ CORRECT: Mod every addition
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;

// ✅ CORRECT modular exponentiation:
long long modpow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // ← mod after each multiply!
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

F.6 Graph / BFS / DFS Bugs

// ❌ BFS: Forgetting to mark visited BEFORE entering queue
// This causes nodes to be processed multiple times!
queue<int> q;
q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    visited[u] = true;  // ❌ Marking AFTER dequeue → same node pushed multiple times
    for (int v : adj[u]) if (!visited[v]) q.push(v);
}

// ✅ CORRECT: Mark visited when ADDING to queue
visited[src] = true;
queue<int> q;
q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;  // ✅ Mark BEFORE pushing
            q.push(v);
        }
    }
}

// ❌ DFS: Forgetting to reset visited between test cases
// In problems with multiple test cases, reinitialize visited[]!
memset(visited, false, sizeof(visited));

// ❌ Dijkstra: Using int instead of long long for distances
int dist[MAXN];  // ❌ if edge weights can be up to 10^9, sum overflows!
long long dist[MAXN];  // ✅

F.7 I/O Bugs

// ❌ WRONG: Missing ios_base::sync_with_stdio(false) for large I/O
// Without this, cin/cout are synced with C stdio → very slow!
// For N = 10^6 inputs, this can be the difference between AC and TLE.

// ✅ ALWAYS add at start of main() for competitive programming:
ios_base::sync_with_stdio(false);
cin.tie(NULL);

// ❌ WRONG: Using endl (flushes buffer every line → slow)
for (int i = 0; i < n; i++) cout << ans[i] << endl;  // slow!

// ✅ CORRECT: Use "\n" instead
for (int i = 0; i < n; i++) cout << ans[i] << "\n";  // fast

// ❌ WRONG: Mixing cin and scanf/printf after disabling sync
ios_base::sync_with_stdio(false);
scanf("%d", &n);  // BUG: mixing C and C++ I/O after desync!

// ✅ CORRECT: Pick ONE and stick with it
// Either use cin/cout exclusively, or scanf/printf exclusively

// USACO file I/O (when required):
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
// After these lines, cin/cout work with files automatically

F.8 2D Array Bounds and Directions

// Grid BFS: off-by-one in boundary checking
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// ❌ WRONG: Bounds check is wrong (allows -1 index)
for (int d = 0; d < 4; d++) {
    int nx = x + dx[d], ny = y + dy[d];
    if (nx >= 0 && ny >= 0 && nx < n && ny < m) // ✅ This is actually correct!
    // Just make sure you check ALL FOUR conditions
}

// ❌ WRONG: Wrong dimensions (swapping rows and columns)
// If grid is N rows × M columns:
// A[row][col]: row goes 0..N-1, col goes 0..M-1
// Bounds: row < N, col < M  (NOT row < M!)

// ❌ WRONG: Visiting same cell multiple times (forgetting dist check)
// In multi-source BFS for distance:
if (!visited[nx][ny]) {  // ✅ Only visit unvisited cells
    visited[nx][ny] = true;
    dist[nx][ny] = dist[x][y] + 1;
    q.push({nx, ny});
}

F.9 DP-Specific Bugs

// ❌ WRONG: 0/1 Knapsack inner loop direction
// Must iterate capacity from HIGH to LOW to prevent reusing items!
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {  // ✅ HIGH to LOW
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
// If you iterate j from LOW to HIGH:
for (int j = weight[i]; j <= W; j++) {  // ❌ LOW to HIGH = unbounded knapsack!
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}

// ❌ WRONG: LIS with binary search — using upper_bound vs lower_bound
// For STRICTLY increasing LIS: use lower_bound (find first >= x, replace)
// For NON-DECREASING LIS: use upper_bound (find first > x, replace)
auto it = lower_bound(tails.begin(), tails.end(), x);  // strictly increasing
auto it = upper_bound(tails.begin(), tails.end(), x);  // non-decreasing

// ❌ WRONG: Forgetting base cases
// dp[0] or dp[i][0] or dp[0][j] MUST be explicitly set before the main loop
dp[0][0] = 0;  // always initialize base cases!

F.10 Memory Limit Exceeded (MLE)

// Common causes of MLE:

// ❌ Array too large for the problem
int dp[10005][10005];  // = 10^8 ints = 400MB → exceeds typical 256MB limit!

// Calculate: N*M*sizeof(type) bytes
// int: 4 bytes, long long: 8 bytes
// 256MB = 256 × 10^6 bytes
// Max int array: 64 × 10^6 elements
// Max long long array: 32 × 10^6 elements

// ✅ Space optimization for 1D DP:
// If dp[i] only depends on dp[i-1], use rolling array:
vector<long long> dp(2, 0);  // dp[cur] and dp[prev]
for (int i = 0; i < n; i++) {
    dp[1 - cur] = f(dp[cur]);  // alternate between 0 and 1
    cur = 1 - cur;
}

// ✅ Space optimization for 2D DP (knapsack-style):
// If dp[i][j] only depends on dp[i-1][...], keep only two rows
vector<int> prev_row(W+1, 0), curr_row(W+1, 0);

Quick Diagnosis Checklist

When you get WA/RE/TLE, go through this checklist:

Wrong Answer (WA):

• Integer overflow? (Add long long casts or change types)
• Off-by-one in array bounds, loop bounds, range sum formula?
• Uninitialized array? (Add memset or use vector with init)
• Wrong DP transition direction? (0/1 knapsack: high-to-low)
• Wrong binary search template? (Verify on [1,2,3] for target 2)
• Edge cases: empty input, N=0, N=1, all equal elements?

Runtime Error (RE):

• Array out of bounds? (Add bounds checks or use vector)
• Stack overflow from deep recursion? (Convert to iterative)
• Null/invalid pointer dereference?
• Division by zero?

Time Limit Exceeded (TLE):

• Missing ios_base::sync_with_stdio(false); cin.tie(NULL);?
• O(N²) algorithm when N=10⁵ needs O(N log N)?
• Unnecessary recomputation in DP? (Need memoization)
• BFS visiting nodes multiple times? (Mark visited before pushing)

Memory Limit Exceeded (MLE):

• 2D array too large? (Calculate N×M×sizeof bytes)
• Recursive DFS with implicit call stack too deep?
• Dynamic memory allocation in tight loop?

💡 Pro Tip: Print your intermediate values! cerr << "DEBUG: dp[3] = " << dp[3] << "\n"; cerr goes to stderr (not stdout), so it won't affect your output in competitive programming judges. Remove all cerr lines before final submission.