These are the notes for Competitive Programming episode 2. You will build the C++ template, the ready-made starting file you copy for every contest problem, and understand every line of it: #include <bits/stdc++.h>, using ll = long long, multiple test cases with solve() and while (t--), and the two fast I/O lines. You will also measure, live, how much faster input gets with fast I/O, why endl is slow, and a printing-order trap that appears once fast I/O is on. Every example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler). Timings are from one run on the recording machine; your numbers will differ, but the ratios hold.
The problem: a compilation error at minute 7
An easy contest problem needs a list of numbers (vector, a resizable array) and sorting (sort). Typing fast, you start with the include you always use:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
cout << a[0] << " " << a[n - 1] << endl;
return 0;
}
Compilation Error:
main.cpp:7:5: error: 'vector' was not declared in this scope
main.cpp:9:5: error: 'sort' was not declared in this scope; did you mean 'short'?
Each part of the C++ standard library lives in its own header (<vector>, <algorithm>, <string>, <map> ...), and we forgot two of them.
The fix: one header for everything
#include <bits/stdc++.h>
With input 4 / 7 2 9 4 the program now prints 2 9. bits/stdc++.h includes the entire standard library at once.
| Separate headers | bits/stdc++.h |
|---|---|
| Fetch each tool from the shelf | Carry the whole toolbox |
| Fast to compile | Slightly slower to compile (fine in contests) |
| Standard C++, works everywhere | GCC only: not in MSVC (Visual Studio), not in Apple clang on a Mac by default |
| Use in real projects | Use in contests (judges use GCC) |
Multiple test cases
Most Codeforces-style problems put many small tests in one input file.
Problem B · Score Spread (written for this course). The input has
ttest cases. Each hasnand thennscores. For each test case, print the largest score minus the smallest score.Constraints:
1 ≤ t ≤ 10^4,1 ≤ n ≤ 2·10^5,1 ≤ a[i] ≤ 10^9, and the sum of n over all test cases is at most 2·10^5.
| Sample input | Sample output |
|---|---|
335 1 417410 10 2 8 |
408 |
What "sum of n over all test cases ≤ 2·10^5" means: t × max n would be 2 · 10^9, but the whole file contains at most 2 · 10^5 scores in total, however they are split. So an O(n) or O(n log n) solution per test is fast overall. Without this line, you would have to assume the worst case for every test.
The structure is like a teacher checking a stack of answer sheets:
| Exam checking | Code |
|---|---|
| The top sheet says how many papers | cin >> t; |
| Same steps for each paper; marks never leak between students | void solve() with its own fresh variables |
| Repeat until the stack is empty | while (t--) solve(); |
t-- tests the current value of t, then decreases it, so the loop body runs exactly t times (and t ends at -1).
The template, line by line
#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;
ll mx = *max_element(a.begin(), a.end());
ll mn = *min_element(a.begin(), a.end());
cout << mx - mn << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Output on the sample: 4, 0, 8.
| Line | Why it is there |
|---|---|
#include <bits/stdc++.h> |
The whole standard library |
using namespace std; |
Write vector instead of std::vector |
using ll = long long; |
A short name (a type alias) for a type you type constantly |
void solve() |
Handles exactly one test case; only this part changes per problem |
for (auto &x : a) cin >> x; |
x is a reference to each element (the element itself, not a copy), so cin fills the real vector |
*max_element(...) |
max_element returns an iterator (a position in the container); * reads the value there |
'\n' |
A newline without flushing (see below) |
ios::sync_with_stdio(false); + cin.tie(nullptr); |
Fast I/O |
while (t--) solve(); |
Run solve once per test case |
Fast input, measured
Some problems have millions of numbers in the input. By default cin:
- stays synchronised with C's
scanf/printf(they share one buffer so you can mix them safely), and - is tied to
cout: before every read it flushescout(pushes any waiting output to the screen).
Contest programs need neither. The measuring program writes 2,000,000 numbers to a file, points cin at it with freopen, and times only the reading with the chrono stopwatch:
#include <bits/stdc++.h>
using namespace std;
int main() {
// (the two fast I/O lines go here in the second run)
{
ofstream f("in.txt");
for (int i = 0; i < 2000000; i++) f << i << ' ';
}
if (!freopen("in.txt", "r", stdin)) return 1;
auto start = chrono::steady_clock::now();
long long sum = 0, x;
while (cin >> x) sum += x;
auto end = chrono::steady_clock::now();
cout << "sum = " << sum << endl;
cout << "read in " << (end - start) / 1ms << " ms" << endl;
return 0;
}
| Version | Output (one run) |
|---|---|
Plain cin |
sum = 1999999000000 / read in 450 ms |
With ios::sync_with_stdio(false); cin.tie(nullptr); |
sum = 1999999000000 / read in 90 ms |
About 5× faster, with no change to the algorithm. A buffer is a waiting area where text collects before it moves in one big chunk; turning sync off gives cin/cout their own fast buffer.
Rules for the two lines:
- Put them at the very top of
main, before any input or output. - After
sync_with_stdio(false), never mixcin/coutwithscanf/printf/puts. cin.tie(nullptr)is unsafe only for interactive problems (where the judge answers your output): there you must flush after each query (cout << ... << endlorcout.flush()).
endl vs '\n', measured
endl prints a newline and flushes. '\n' only prints the newline; the buffer is sent in big chunks.
#include <bits/stdc++.h>
using namespace std;
int main() {
auto t0 = chrono::steady_clock::now();
ofstream a("a.txt");
for (int i = 0; i < 1000000; i++) a << i << endl;
auto t1 = chrono::steady_clock::now();
ofstream b("b.txt");
for (int i = 0; i < 1000000; i++) b << i << '\n';
auto t2 = chrono::steady_clock::now();
cout << "endl: " << (t1 - t0) / 1ms << " ms" << endl;
cout << "\\n: " << (t2 - t1) / 1ms << " ms" << endl;
return 0;
}
One run printed endl: 398 ms and \n: 33 ms, about 10× slower for the same text. Like walking to the post office after every letter instead of filling the bag first. Use '\n' in every loop.
The printf trap
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << "1. cout\n";
printf("2. printf\n");
cout << "3. cout\n";
return 0;
}
Output:
1. cout
3. cout
2. printf
With sync off, cout and printf have separate buffers, and each empties whenever it likes. On a judge this is a Wrong Answer. Pick one system and stick to it.
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Only #include <iostream>, then vector/sort |
error: 'vector' was not declared in this scope |
Each tool needs its header | #include <bits/stdc++.h> |
Sync off, then printf |
Lines out of order (no error) | Two separate buffers | Use only cin/cout |
endl in a loop of 10^6 lines |
Time limit exceeded | endl flushes every line |
'\n' |
| A global vector reused across tests | Wrong answer on test 2 | Old values leak into the next test | Declare inside solve() |
Fast I/O lines after the first cin |
Little or no speed-up | They must come before any I/O | First lines of main |
bits/stdc++.h on a Mac |
fatal error: 'bits/stdc++.h' file not found |
Apple clang doesn't ship it | Install GCC, or use the online compiler |
Score Spread: brute force vs optimal
| Approach | Time | Memory |
|---|---|---|
| Sort each test, take last − first | O(n log n) per test | O(n) |
One pass with max_element / min_element |
O(n) per test, O(sum of n) overall | O(n) (O(1) if you don't store the array) |
Solution in C++, Java and Python
C++ — the template above.
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int t = nextInt(in);
StringBuilder out = new StringBuilder();
while (t-- > 0) {
int n = nextInt(in);
long mx = Long.MIN_VALUE, mn = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
long x = nextInt(in);
mx = Math.max(mx, x);
mn = Math.min(mn, x);
}
out.append(mx - mn).append('\n');
}
System.out.print(out);
}
static int nextInt(DataInputStream in) throws IOException {
int ret = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { ret = ret * 10 + (b - '0'); b = in.read(); }
return ret;
}
}
(Java's equivalent of fast I/O: read bytes through a buffer, and collect output in a StringBuilder instead of printing line by line. This nextInt handles the non-negative numbers of this problem.)
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 = data[pos:pos + n]; pos += n
nums = list(map(int, a))
out.append(max(nums) - min(nums))
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
(Python's fast I/O: read the whole input at once with sys.stdin.buffer.read() and write once at the end.)
Mini project: your personal template file
Create template.cpp with the code above, but with an empty solve():
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t; // delete this line when a problem has a single test
while (t--) solve();
return 0;
}
Copy it at the start of every problem. Many contestants also add const ll MOD = 1e9 + 7; (you will need it from episode 21). Keep the template short: every line should have a reason.
Practice
-
Rewrite Chai Batches from episode 1 using the template (single test: set
t = 1and removecin >> t).Solution
```cpp void solve() { ll n, k; cin >> n >> k; ll sum = 0; for (int i = 0; i < n; i++) { ll a; cin >> a; sum += a; } cout << (sum + k - 1) / k << '\n'; } ``` -
Score Spread, but print the second largest distinct score, or
-1if there isn't one.Solution
Sort, remove duplicates (`a.erase(unique(a.begin(), a.end()), a.end());`), then print `a[a.size() - 2]` if `a.size() >= 2`, else `-1`. -
Time
endlvs'\n'for 10^5 and 10^7 lines. Is the ratio roughly constant?Solution
Yes: both grow linearly, and `endl` stays several times slower because every line costs a flush (a system call).
Quick quiz
int t = 3;
while (t--) solve();
How many times does solve() run, and what is t afterwards?
A) 3, t = 0 B) 3, t = -1 C) 2, t = 0 D) 4, t = -1
Answer
B. The loop tests 3, 2, 1 (true, so solve runs 3 times), then tests 0 (false) and stops, but that last test still decreases t to -1.
Interview questions
- What does
ios::sync_with_stdio(false)do, and what is the risk? (Unsyncs C++ streams from C stdio for speed; mixingprintf/scanfwithcout/cinthen gives out-of-order or wrong I/O.) - Why is
endlslower than'\n'? (It flushes the stream every time.) - Why shouldn't you use
bits/stdc++.hin production code? (Not standard, GCC only, slower compiles, hides real dependencies.) - When must you flush output explicitly? (Interactive problems, and before a program might crash if you need the output.)
Glossary
| Term | Meaning | Example |
|---|---|---|
| Template | A ready-made starting file you copy for every problem | The file above |
| Header | A file that declares a part of the library | <vector>, <algorithm> |
bits/stdc++.h |
GCC's header that includes the whole standard library | #include <bits/stdc++.h> |
vector |
A resizable array | vector<ll> a(n); |
| Type alias | A new name for an existing type | using ll = long long; |
| Test case | One independent problem instance inside the input | one block of Score Spread |
| Sum of n constraint | A bound on the total size of all test cases together | sum of n ≤ 2·10^5 |
solve() |
The function that handles one test case | void solve() { ... } |
Reference (&) |
Another name for the same variable, not a copy | for (auto &x : a) |
| Iterator | A position inside a container | a.begin(), max_element(...) |
| Stream | A flow of characters in or out of a program | cin, cout, cerr |
| Buffer | A waiting area where output collects before being sent | the cout buffer |
| Flush | Push everything waiting in the buffer out now | endl, cout.flush() |
| Fast I/O | Turning off sync and tie so cin/cout run at full speed |
the two lines in main |
freopen |
Redirects stdin/stdout to a file |
freopen("in.txt", "r", stdin) |
chrono |
The C++ time library, used here as a stopwatch | chrono::steady_clock::now() |
| Interactive problem | A problem where the judge replies to your output | guess-the-number problems |
Summary
#include <bits/stdc++.h>brings the whole standard library (GCC only; fine for contests).- Multiple test cases:
cin >> t; while (t--) solve();with all per-test variables insidesolve(). - "Sum of n over all test cases" bounds the total work.
ios::sync_with_stdio(false); cin.tie(nullptr);makes input several times faster. Put them first inmain.- Use
'\n', notendl, in loops. - With sync off, never mix
printf/scanfwithcout/cin.
Next episode: reading constraints, from n to the complexity you need.