Sefism.Competitive programming: Intermediate

Tauseef Fayyaz

Chapter 01

C++ for contests

The language features, STL containers and habits that make C++ the default contest language, plus the table that turns a constraint into the complexity you can afford.

Complexity vs n table

Also called constraints, time limit, operations per second, big-O budget

What: A rule of thumb that maps the input limit n to the slowest complexity that fits a typical one or two second time limit, assuming a judge runs very roughly 10^8 simple operations per second.
Why: The constraints are the biggest hint in the statement. Reading n first tells you which family of solutions to look for before you think about details.

Code

n up to        complexity that usually fits
10 to 11       O(n!)
18 to 22       O(2^n * n)
400 to 500     O(n^3)
2,000 to 5,000 O(n^2)
10^5 to 10^6   O(n log n) or O(n sqrt n)
10^7 to 10^8   O(n) with a small constant
10^9 and above O(log n), O(sqrt n) or a formula

Watch out

Forgetting that a sum over test cases is bounded: when the sum of n over all tests is at most 2 * 10^5, O(n log n) per test is fine.

Contest template

Also called boilerplate, starter code, bits/stdc++.h

What: The short file you start every problem from: one header that pulls in the whole standard library, a long long alias, fast input and output, and a loop over test cases.
Why: Typing the same lines under time pressure wastes minutes and invites typos. A template you know by heart lets you start on the idea straight away.

C++

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t; cin >> t;
  while (t--) {
    // read one test, solve it, print the answer
  }
}

Watch out

Growing the template into pages of macros you do not understand; keep it short enough to type from memory at an ICPC site.

Fast input and output

Also called sync_with_stdio, cin.tie, fast IO, endl vs newline

What: Two lines that stop cin and cout synchronising with C input and output and flushing each other, plus printing a newline character instead of endl, which flushes on every line.
Why: With 10^6 numbers to read or print, slow IO alone can exceed the time limit on a correct solution.

C++

ios::sync_with_stdio(false);
cin.tie(nullptr);
// '\n' does not flush; endl flushes every time
for (int x : answers) cout << x << '\n';

Watch out

Mixing scanf or printf with cin or cout after turning sync off, which can print output in the wrong order.

Compiler flags and sanitizers

Also called g++, -O2, -Wall, -fsanitize, _GLIBCXX_DEBUG

What: Compile with warnings on for normal runs, and with sanitizers and the debug STL while hunting a bug, so out-of-range indexes and overflow stop the program with a message.
Why: Most wrong answers and runtime errors are an index off by one or an overflow. Sanitizers find them in seconds on your own machine instead of costing a penalty.

Shell

g++ -std=c++20 -O2 -Wall -Wextra -o a a.cpp
./a < in.txt

# while debugging
g++ -std=c++20 -g -fsanitize=address,undefined \
  -D_GLIBCXX_DEBUG -o a a.cpp

Watch out

Testing only on the sample input and never on your own edge cases, such as n = 1 or all values equal.

vector, pair and tuple

Also called dynamic array, std::vector, std::pair, structured bindings

What: A vector is a resizable array with O(1) index access and amortised O(1) push_back. A pair or tuple groups values that compare element by element, first by the first value.
Why: Almost every solution stores input in a vector, and pairs let you sort by one key and keep the original index alongside it.

C++

vector<int> a(n);
for (auto& x : a) cin >> x;
vector<pair<int, int>> byValue;
for (int i = 0; i < n; i++) byValue.push_back({a[i], i});
sort(byValue.begin(), byValue.end());
auto [value, index] = byValue[0];  // smallest value

Watch out

Declaring a vector of size n and then calling push_back n times, which leaves n zeros at the front.

Sorting with a comparator

Also called custom sort, lambda comparator, strict weak ordering

What: Passing a function to sort that returns true when the first element must come before the second, usually written as a lambda.
Why: Greedy solutions often start with an unusual order, such as by end time or by a ratio, and the comparator is where that decision lives.

C++

vector<pair<int, int>> v = {{3, 1}, {1, 2}, {3, 0}};
sort(v.begin(), v.end());  // by first, then second
sort(v.begin(), v.end(), [](auto& a, auto& b) {
  return a.second < b.second;
});

Watch out

Writing <= in a comparator: it breaks strict ordering and can crash sort or loop forever.

set, map and multiset

Also called ordered set, std::map, std::set, multiset, balanced BST

What: Sorted containers built on a balanced binary search tree, with O(log n) insert, erase and search, and lower_bound to find the first element not below a value.
Why: They answer "what is the next larger value" or "how often does x occur" while elements are added and removed, which a sorted vector cannot do cheaply.

C++

set<int> s = {5, 1, 9};
auto it = s.lower_bound(4);  // points at 5
map<string, int> cnt;
cnt["abc"]++;                // missing key starts at 0
multiset<int> ms = {3, 3, 7};
ms.erase(ms.find(3));        // removes one 3 only

Watch out

Calling ms.erase(3) on a multiset, which removes every copy of 3, or lower_bound(s.begin(), s.end(), x), which is O(n) on a set.

priority_queue

Also called heap, min-heap, max-heap

What: A heap that always gives the largest element in O(1) and inserts or removes in O(log n). Adding greater turns it into a min-heap.
Why: It drives Dijkstra, scheduling greedies and "always take the best available item" problems.

C++

priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(5);
minHeap.push(2);
int smallest = minHeap.top();  // 2
minHeap.pop();

Watch out

Forgetting that the default is a max-heap, then getting the largest distance first in Dijkstra.

STL algorithms toolkit

Also called unique, accumulate, next_permutation, max_element, iota

What: Ready-made functions in the standard library for sorting, removing duplicates, summing, finding extremes and walking through permutations.
Why: Each one replaces a loop you might get wrong under time pressure, and they are well tested and fast.

C++

sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
ll sum = accumulate(a.begin(), a.end(), 0LL);
int mx = *max_element(a.begin(), a.end());
vector<int> p(n);
iota(p.begin(), p.end(), 0);  // 0, 1, ..., n-1
do {
  // try the order in p
} while (next_permutation(p.begin(), p.end()));

Watch out

Passing 0 instead of 0LL to accumulate, which sums in int and overflows.

Integer overflow and long long

Also called overflow, long long, 64-bit, int limits

What: An int holds values up to about 2.1 * 10^9, and a long long up to about 9.2 * 10^18. Multiplying two int values overflows before the result is stored in a long long.
Why: Sums of 10^5 values up to 10^9, or products of two values up to 10^5, already exceed int. Overflow gives silent wrong answers, not errors.

C++

int a = 100000, b = 100000;
long long bad = a * b;        // overflows first
long long good = 1LL * a * b; // 10000000000

Watch out

Using int for sums and answers "because the input fits in int".

unordered_map and anti-hash tests

Also called hash map, custom hash, splitmix64, anti-hash

What: A hash map with average O(1) operations. With the default hash, people can craft inputs where every key collides, making it O(n) per operation.
Why: On platforms where other contestants can hack or add tests, a plain unordered_map can time out. A randomised hash or a map avoids it.

C++

struct SafeHash {
  size_t operator()(uint64_t x) const {
    static const uint64_t seed =
      chrono::steady_clock::now().time_since_epoch().count();
    x += seed + 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
};
unordered_map<long long, int, SafeHash> cnt;

Watch out

Assuming unordered_map is always faster than map; with small n or hostile tests it can be slower.

Go deeper