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
ndaily step countsa[1..n]. Find the length of the longest run of consecutive days where the step count strictly increases.
ttest 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 |
|---|---|
351 2 3 2 51744 3 2 1 |
311 |
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
-
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`. -
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). -
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. -
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
- 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.)
- Why print debug output to
cerrinstead ofcout? (It's a separate stream that judges don't compare.) - How do you detect out-of-bounds access in C++? (
_GLIBCXX_DEBUG,.at(), or sanitizers like-fsanitize=address,undefined.) - 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 throwsbad_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.