SyntaxPilot
Courses/Competitive Programming/Lesson 4
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 4 of 90

Verdicts explained: WA, TLE, MLE, RE and how to debug each

queued

These are the notes for Competitive Programming episode 4. One original problem, Step Streak, is submitted four times and fails four different ways: Wrong Answer, Time Limit Exceeded, Runtime Error and Memory Limit Exceeded. For each one you see the cause, the tool that finds it (cerr, path checking, _GLIBCXX_DEBUG, counting bytes) and the fix, and you finish with a debugging checklist for every verdict. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs and messages below are real.

The problem: Step Streak

Problem D · Step Streak (written for this course). Your phone logged n daily step counts a[1..n]. Find the length of the longest run of consecutive days where the step count strictly increases.

t test cases; 1 ≤ t ≤ 10^4, 1 ≤ n ≤ 2·10^5, sum of n ≤ 2·10^5, 1 ≤ a[i] ≤ 10^9.

Sample input Sample output
3
5
1 2 3 2 5
1
7
4
4 3 2 1
3
1
1

Idea: walk once. If today beats yesterday, the current streak grows; otherwise it restarts at 1. Keep the best. O(n) time, O(1) extra memory.

Submission 1: Wrong Answer (globals leak between tests)

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

int best = 1, cur = 1;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i - 1]) cur++;
        else cur = 1;
        best = max(best, cur);
    }
    cout << best << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Output on the sample: 3 3 3. Expected 3 1 1. Wrong answer on test 1.

Debug tool: print to cerr

Don't stare at the code; make it tell you what it is doing. But cout output is checked by the judge, so print debug information to cerr, the separate error stream (most judges, including Codeforces, ignore it):

    for (auto &x : a) cin >> x;
    cerr << "start: best = " << best << ", cur = " << cur << '\n';

The cerr output (shown under "Runtime errors" in the SyntaxPilot compiler):

start: best = 1, cur = 1
start: best = 3, cur = 2
start: best = 3, cur = 2

Test 2 starts with leftovers from test 1. Global variables (declared outside every function) live for the whole program, so they carry values from one test case to the next.

Fix: declare them inside solve():

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    int best = 1, cur = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i - 1]) cur++;
        else cur = 1;
        best = max(best, cur);
    }
    cout << best << '\n';
}

Output: 3 1 1. Remove the cerr line before submitting (it costs time on big inputs).

Submission 2: Time Limit Exceeded on a tiny input (infinite loop)

    int best = 1, cur = 1;
    int i = 1;
    while (i < n) {
        if (a[i] > a[i - 1]) {
            cur++;
            i++;
        } else cur = 1;
        best = max(best, cur);
    }

Verdict on the sample: Time Limit Exceeded.

Key insight: a tiny input can't be slow because of the algorithm. TLE on a tiny input means an infinite loop. Check every path through the loop body and ask whether it moves the loop forward. Here the else path never increases i, so at the first decrease (3 → 2) the loop checks the same pair forever.

Fix: a for loop, where i++ sits in one place and runs on every path.

Submission 3: Runtime Error (out of bounds), made loud with _GLIBCXX_DEBUG

    for (int i = 0; i < n; i++) {
        if (a[i + 1] > a[i]) cur++;
        else cur = 1;
        best = max(best, cur);
    }

When i = n − 1, a[i + 1] is a[n], one past the end. Reading it is undefined behaviour: anything can happen. In our run the output was:

3
1
2

No crash and no message, just a wrong last answer built from whatever was in memory after the array. On a judge this shows up as a random Wrong Answer or a Runtime Error.

Debug tool: _GLIBCXX_DEBUG

Put this line at the very top of the file (before any include):

#define _GLIBCXX_DEBUG

It switches GCC's standard library into debug mode: every vector[] access is checked. Now the run stops with a precise message (Runtime Error, SIGABRT):

Error: attempt to subscript container with out-of-bounds index 5, but
container only holds 5 elements.

Fix: start at i = 1 and compare a[i] with a[i - 1], so every index stays inside. Remove the define before submitting: the checks make every access slower.

What causes a Runtime Error

Cause Typical signal
Index out of bounds (a[n], a[-1]) SIGSEGV (segmentation fault), or silent garbage
Division or % by zero SIGFPE
Recursion too deep (stack overflow) SIGSEGV
Uncaught exception (bad_alloc, out_of_range from .at()) SIGABRT
main returning non-zero NZEC ("non-zero exit code")

The stack is the memory area that holds function calls; every recursive call uses a little of it, and very deep recursion (around 10^5 to 10^6 levels, depending on the judge) can overflow it.

Submission 4: Memory Limit Exceeded (count memory like time)

Someone wants to store the streak for every pair of days in an n × n table:

    int n;
    cin >> n;
    vector<int> table((ll)n * n);  // streak[i][j]

With n = 200000: 4·10^10 cells × 4 bytes = 160 GB, against a limit of 256 MB. Locally the request is refused outright:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

(bad_alloc = the memory request was refused.) The compiler shows a Runtime Error (SIGABRT); a judge, which measures memory, usually reports Memory Limit Exceeded.

Type Bytes 256 MB holds about
char / bool 1 2.5·10^8
int 4 6·10^7
long long / double 8 3·10^7

An n × n array of ints fits only for n up to about 5000–8000. Other memory eaters: very deep recursion, vectors of vectors, maps with millions of keys. Our real solution needs three variables beyond the input: O(1) extra memory.

The accepted solution and edge cases

Edge cases are inputs at the extremes of the rules:

Input Output Why
1 / 1000000000 1 a single day is a streak of 1
4 / 5 5 5 5 1 equal is not strictly increasing
6 / 1 2 3 4 5 6 6 the whole array

Solution in C++, Java and Python

C++

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

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    int best = 1, cur = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i - 1]) cur++;
        else cur = 1;
        best = max(best, cur);
    }
    cout << best << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        st.nextToken();
        int t = (int) st.nval;
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            st.nextToken();
            int n = (int) st.nval;
            long prev = -1;
            int best = 1, cur = 1;
            for (int i = 0; i < n; i++) {
                st.nextToken();
                long x = (long) st.nval;
                if (i > 0) {
                    if (x > prev) cur++;
                    else cur = 1;
                    best = Math.max(best, cur);
                }
                prev = x;
            }
            out.append(best).append('\n');
        }
        System.out.print(out);
    }
}

(StreamTokenizer reads numbers as double; that is exact for values up to 2^53, so 10^9 is safe.)

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0]); pos = 1
    out = []
    for _ in range(t):
        n = int(data[pos]); pos += 1
        a = list(map(int, data[pos:pos + n])); pos += n
        best = cur = 1
        for i in range(1, n):
            cur = cur + 1 if a[i] > a[i - 1] else 1
            best = max(best, cur)
        out.append(best)
    print("\n".join(map(str, out)))

main()

Brute force vs optimal

Approach Time Extra memory
For every start i, extend while increasing O(n²) worst case (all increasing) O(1)
n × n table of streaks O(n²) O(n²): MLE
One pass with cur and best O(n) O(1)

The debugging checklist

Verdict Check
WA overflow (long long)? variables reset per test? exact output format? edge cases: n = 1, all equal, max values?
TLE tiny input → infinite loop; otherwise compare complexity with the constraints; endl and fast I/O
RE _GLIBCXX_DEBUG for indexes; division/modulo by zero; recursion depth; uncaught exceptions
MLE count the bytes of every big array; drop tables you don't need
Still stuck stress test against a brute force (next episode)

Common mistakes (and the real messages)

Mistake What you see Why Fix
cout << "debug: " << x; Wrong answer on test 1 Debug text goes into the checked output cerr << "debug: " << x;
Globals in a multi-test problem Wrong answer on test 2 (3 3 3) Values leak between tests Declare inside solve()
a[i + 1] with i < n Random WA, or with the debug define: attempt to subscript container with out-of-bounds index 5, but container only holds 5 elements. a[n] is out of bounds Loop i = 1..n−1 with a[i - 1]
A loop path that doesn't move i Time limit exceeded on the sample Infinite loop Put i++ where every path runs it
vector<int> table((ll)n * n) with n = 2·10^5 terminate called after throwing an instance of 'std::bad_alloc' 160 GB requested Store only what you need
Submitting with #define _GLIBCXX_DEBUG Time limit exceeded Checked containers are slower Remove it before submitting

Mini project: a debug macro

Many contestants keep a debug macro that prints a variable's name and value to cerr, and switches off automatically on the judge:

#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << (x) << '\n'
#else
#define dbg(x)
#endif

Compile locally with g++ -DLOCAL ... and dbg(best); prints best = 3; on the judge (no -DLOCAL) the line disappears. Add it to your template from episode 2.

Practice

  1. Find the bug: for (int i = n; i >= 0; i--) sum += a[i];

    Solution It starts at `a[n]`, one past the end. Start at `i = n - 1`.

  2. A recursive DFS on a path of 10^6 nodes gets Runtime Error. Why, and what can you do?

    Solution Stack overflow from 10^6 nested calls. Rewrite it iteratively with your own stack (a `vector` used as a stack).

  3. Change Step Streak to the longest non-decreasing run.

    Solution Change `a[i] > a[i - 1]` to `a[i] >= a[i - 1]`. Then `5 5 5 5` gives 4.

  4. Your code gets RE on test 1 only when n = 1. What do you check first?

    Solution Any access like `a[1]` or `a[i + 1]` that assumes at least two elements, and any division by `n − 1`.

Quick quiz

Your code gets Time limit exceeded on test 1 (the sample, n = 3). What is the most likely cause?

A) O(n²) is too slow B) An infinite loop C) Integer overflow D) Using endl

Answer

B. With n = 3 even O(n³) is instant, and endl costs nothing on three lines. A program that never finishes on a tiny input is stuck in a loop that never ends.

Interview questions

  1. What is undefined behaviour in C++, and why is it dangerous? (Behaviour the standard doesn't define, like reading out of bounds; the program may crash, give garbage, or seem to work and fail elsewhere.)
  2. Why print debug output to cerr instead of cout? (It's a separate stream that judges don't compare.)
  3. How do you detect out-of-bounds access in C++? (_GLIBCXX_DEBUG, .at(), or sanitizers like -fsanitize=address,undefined.)
  4. What's the difference between a stack overflow and a heap allocation failure? (Stack overflow: too many nested calls; heap failure: a too-large new/vector request, which throws bad_alloc.)

Glossary

Term Meaning Example
Verdict The judge's result for a submission WA, TLE, RE, MLE
Debugging Finding and fixing the cause of wrong behaviour printing variables with cerr
cerr The standard error stream; judges ignore it cerr << x << '\n';
Global variable A variable declared outside every function; lives for the whole program int best = 1; at the top
Infinite loop A loop whose condition never becomes false a path that never does i++
Out of bounds Accessing an index outside 0..size−1 a[5] in a 5-element vector
Undefined behaviour Code whose result C++ does not define reading a[n]
_GLIBCXX_DEBUG Turns on GCC's checked standard library #define _GLIBCXX_DEBUG
Segmentation fault (SIGSEGV) A crash from touching memory you don't own bad pointer, huge index, stack overflow
SIGFPE A crash from arithmetic errors division by zero
SIGABRT The program aborted itself uncaught bad_alloc
Stack / stack overflow Memory for function calls / running out of it very deep recursion
bad_alloc Exception thrown when a memory request is refused vector<int>(4e10)
Memory Limit Exceeded (MLE) The program used more memory than allowed a 160 GB table
Edge case An input at the extremes of the rules n = 1, all equal

Summary

  • WA: make the program talk with cerr; check overflow, per-test resets, output format and edge cases.
  • TLE on a tiny input is an infinite loop; otherwise it's the complexity.
  • RE: bad indexes (catch them with _GLIBCXX_DEBUG), division by zero, deep recursion, exceptions.
  • MLE: count bytes: 256 MB ≈ 6·10^7 ints.
  • Test the extremes before you submit, and remove debug code.

Next episode: stress testing: a brute force, a random generator and a checker that find the failing test for you.