ECPC Team Reference Book

Adham

C++17 * Contest Edition

Contents
0. How To Use This Book 4
1. C++ / STL Essentials 5
Fast I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Template header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
set / map / unordered_map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
priority_queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
deque / stack / queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
lower_bound / upper_bound (sorted range required!) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Custom comparator / lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
bitset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Useful one-liners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2. Complexity & Problem Recognition 7

3. Arrays 8
Prex Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2D Prex Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Dierence Array (range update, point query) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Kadane (max subarray sum) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Two Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Sliding Window (xed / variable size) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Coordinate Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4. Binary Search 10
Binary Search on Answer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Finding rst / last valid index with a predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5. Number Theory 11
GCD / LCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Extended GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Sieve of Eratosthenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Smallest Prime Factor (fast factorization) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Prime factorization (no sieve, O(sqrt n)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Modular Arithmetic & Fast Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Euler's Totient phi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Combinations mod p (precompute factorials) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Pascal's Triangle (small n, no mod inverse needed) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Chinese Remainder Theorem (two congruences) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Bit tricks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6. Recursion / Backtracking 14
Subsets (bitmask) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Subsets (recursive) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1
ECPC Team Reference 2

Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Combinations (choose r of n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
N-Queens pattern (placement with constraint sets) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Meet in the Middle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Pruning techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7. Graphs 16
Adjacency List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
DFS (iterative & recursive) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Connected Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Grid BFS/DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Bipartite Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Cycle Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Topological Sort (Kahn's algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
DSU (Disjoint Set Union) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Kruskal's MST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Prim's MST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
0-1 BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Floyd-Warshall (all pairs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Strongly Connected Components (Kosaraju) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Bridges & Articulation Points (Tarjan) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Euler Path / Circuit (Hierholzer) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

8. Trees 21
Tree DFS + Subtree Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Tree Diameter (2 BFS/DFS passes) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
LCA via Binary Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Tree DP (basic, e.g. max independent set) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Rerooting Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

9. Data Structures 23
Fenwick Tree (Binary Indexed Tree)  point update, prex sum . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Segment Tree (point update, range sum) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Lazy Segment Tree (range update, range sum) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Sparse Table (static range min/max/gcd, O(1) query) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Monotonic Stack (next greater element) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Monotonic Queue (sliding window minimum) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

10. Dynamic Programming 26

1D DP (e.g. climbing stairs / house robber style) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2D DP (grid path count / edit distance style) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
0/1 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
LIS (Longest Increasing Subsequence)  O(n log n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
LCS (Longest Common Subsequence) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Grid DP (min path sum) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Bitmask DP (TSP-style) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Digit DP (count numbers with a property up to N) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Tree DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
DP Optimization Patterns (when TLE and n is large) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

11. Strings 28
Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Frequency count . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Palindrome check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
String Hashing (polynomial rolling hash) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
KMP (pattern matching, O(n+m)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
ECPC Team Reference 3

Z-function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Manacher's Algorithm (longest palindromic substring, O(n)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Aho-Corasick (multi-pattern matching) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

12. Greedy 31
Sorting-based Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Interval Scheduling (max non-overlapping intervals) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Activity Selection / Minimum Rooms (interval overlap count) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Exchange Argument (intuition) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Common Min/Max Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

13. Geometry 32
Point / Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Dot Product & Cross Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Line / Segment Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Polygon Area (Shoelace formula) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Convex Hull (Andrew's monotone chain) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

14. Advanced / Emergency Pages 34

Max Flow (Dinic's algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Bipartite Matching (via Dinic, or Kuhn's algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Min-Cost Max-Flow (SPFA / Bellman-Ford based augmenting) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Matrix Exponentiation (linear recurrences in O(log n)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
FFT Overview (polynomial multiplication in O(n log n)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Ternary Search (unimodal function optimization) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Randomization (treaps, random pivots, anti-hash defense) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Game Theory / Sprague-Grundy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

15. Things I ALWAYS Forget 37

16. Formula Sheet 38
17. Common Bugs & Edge Cases Checklist 39
18. Constraint -> Technique Quick Table 40
19. Debug & Contest Workow 41
ECPC Team Reference 4

0. How To Use This Book

This is a lookup manual, not a textbook. During a contest you should be able to:
1. Read a problem, identify constraints (n, time limit).
2. Jump to Section 2 (Complexity & Recognition) to guess the expected approach.
3. Jump straight to the template you need, copy-paste, adapt variable names, done.
Rule of thumb: don't read code you don't need. Every section starts with a one-line when do I use this note.
ECPC Team Reference 5

1. C++ / STL Essentials

Fast I/O
ios_base::sync_with_stdio(false);
[Link](nullptr);
// If you need printf/scanf too, do NOT sync_with_stdio(false)

Template header
#include <bits/stdc++.h>
using namespace std;
#define int long long // careful: changes behavior of int-sized things globally
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all (x) (x).begin(), (x).end()
#define pb push_back
const int MOD = 1e9+7;

vector
vector<int> v = {1,2,3};
v.push_back(4);
v.pop_back();
[Link]([Link]()+1, 99); // insert at index 1
[Link]([Link]()+1); // remove index 1
sort(all(v));
reverse(all(v));
[Link](10, 0);

set / map / unordered_map

set<int> s; // sorted, unique, O(log n)
[Link](5); [Link](5);
auto it = [Link](5); // [Link]() if not found
[Link](5); // 0 or 1

map<int,int> m; // sorted by key

m[5] = 10; // creates if absent!
if ([Link](5)) ... // check without creating

unordered_map<int,int> um; // O(1) avg, no ordering, avoid custom hash issues

Trap: unordered_map can be attacked with anti-hash tests -> use a custom hash or gp_hash_table if TLE on Codeforces.

priority_queue
priority_queue<int> maxheap; // max-heap default
priority_queue<int, vector<int>, greater<int>> minheap; // min-heap
priority_queue<pii, vector<pii>, greater<pii>> pq; // min-heap of pairs (dist, node)

deque / stack / queue

deque<int> dq; dq.push_front(1); dq.push_back(2); dq.pop_front(); dq.pop_back();
stack<int> st; [Link](1); [Link](); [Link]();
queue<int> q; [Link](1); [Link](); [Link]();
ECPC Team Reference 6

lower_bound / upper_bound (sorted range required!)

// lower_bound: first element >= x
// upper_bound: first element > x
auto it = lower_bound(all(v), x);
int idx = it - [Link]();
int count_equal = upper_bound(all(v), x) - lower_bound(all(v), x);
bool exists = binary_search(all(v), x);

Custom comparator / lambda

sort(all(v), [](int a, int b){ return a > b; }); // descending
sort(all(pairs), [](pii a, pii b){
if ([Link] != [Link]) return [Link] < [Link];
return [Link] > [Link];
});

struct Cmp { bool operator()(int a, int b) const { return a > b; } };

priority_queue<int, vector<int>, Cmp> pq2;

bitset
bitset<32> b(13); // 00000000000000000000000000001101
[Link](0); [Link](1); [Link](2);
[Link](); // number of set bits
b.to_ullong();

Useful one-liners
iota(all(v), 0); // fill 0,1,2,...
__builtin_popcount(x); // int popcount
__builtin_popcountll(x); // long long popcount
__builtin_clz(x); __builtin_ctz(x); // leading / trailing zeros
*max_element(all(v)); *min_element(all(v));
accumulate(all(v), 0LL);
unique(all(v)); // removes consecutive dups -> sort first, then [Link](unique(all(v)),
,→ [Link]())
next_permutation(all(v));
__gcd(a,b);
ECPC Team Reference 7

2. Complexity & Problem Recognition

Given n and time limit ~1-2s (about 1e8-1e9 simple ops/sec):

n Expected complexity
<= 10 O(n!) or O(2n * n)
<= 20 O(2n)  bitmask DP/backtracking
<= 500 O(n3)
<= 5,000 O(n2)
<= 1e5 - 2e5 O(n log n)
<= 1e6 - 1e7 O(n) or O(n log n) tight
<= 1e9 O(log n) or O(sqrt n)
huge (1e18) O(1) / O(log n) formula, matrix expo

Pattern triggers: - Values huge but few distinct / few operations -> coordinate compression. - Subarray sum / range
sum, static array -> prex sums. - Range sum, updates too -> Fenwick / segment tree. - Min/max sum of contiguous
subarray -> Kadane. - Count pairs with property, sorted-able -> two pointers or binary search. - Optimal choice,
greedy fails on samples -> probably DP. - n <= 20, subsets -> bitmask DP. - String matching -> KMP / Z-function
/ hashing. - Shortest path -> see table in Section 7. - Connectivity / grouping -> DSU or BFS/DFS. - Min spanning
structure -> Kruskal/Prim (MST) or DSU. - Optimize over a monotonic function of the answer -> binary search on
answer. - Grid problem, small grid -> BFS/DFS/DP on grid. - Interval scheduling -> sort + greedy. - Tree, queries
about ancestor/depth -> LCA / binary lifting. - XOR / independent choices game -> Sprague-Grundy / game theory.
ECPC Team Reference 8

3. Arrays
Prex Sum
vector<long long> pre(n+1, 0);
for (int i = 0; i < n; i++) pre[i+1] = pre[i] + a[i];
// sum of [l, r] inclusive, 0-indexed:
long long rangeSum = pre[r+1] - pre[l];

2D Prex Sum
vector<vector<long long>> pre(n+1, vector<long long>(m+1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
pre[i][j] = a[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
// sum of rectangle (r1,c1)-(r2,c2), 0-indexed inclusive:
long long rect = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];

Dierence Array (range update, point query)

vector<long long> diff(n+1, 0);
// add val to range [l, r]
diff[l] += val; diff[r+1] -= val;
// after all updates, prefix-sum diff to get final array
vector<long long> res(n);
long long cur = 0;
for (int i = 0; i < n; i++) { cur += diff[i]; res[i] = cur; }

Kadane (max subarray sum)

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

Two Pointers
// e.g. count pairs with a[i]+a[j] <= x in sorted array
sort(all(a));
int l = 0, r = n-1; long long cnt = 0;
while (l < r) {
if (a[l] + a[r] <= x) { cnt += r - l; l++; }
else r--;
}

Sliding Window (xed / variable size)

// variable window: smallest window with sum >= target
int l = 0; long long sum = 0; int best = INT_MAX;
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum >= target) { best = min(best, r-l+1); sum -= a[l++]; }
}
ECPC Team Reference 9

Coordinate Compression
vector<int> vals = a;
sort(all(vals)); [Link](unique(all(vals)), [Link]());
auto comp = [&](int x){ return lower_bound(all(vals), x) - [Link](); };
ECPC Team Reference 10

4. Binary Search
// Standard binary search for exact value in sorted array
int lo = 0, hi = n-1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (a[mid] == target) { ans = mid; break; }
else if (a[mid] < target) lo = mid+1;
else hi = mid-1;
}

Binary Search on Answer

Use when the answer space is monotonic: if X works, every value greater/less also works.
auto works = [&](long long x) -> bool {
// custom feasibility check
return true; // placeholder
};
long long lo = LOW, hi = HIGH, ans = HIGH;
while (lo <= hi) {
long long mid = lo + (hi-lo)/2;
if (works(mid)) { ans = mid; hi = mid-1; } // looking for smallest feasible
else lo = mid+1;
}

Finding rst / last valid index with a predicate

// first index where predicate becomes true (predicate is monotonic false...false,true...true)
int lo = 0, hi = n; // hi = n means "not found"
while (lo < hi) {
int mid = lo + (hi-lo)/2;
if (pred(mid)) hi = mid; else lo = mid+1;
}
int firstTrue = lo;

Common predicates: can we nish within time T, is capacity C enough, is answer >= x achievable.
ECPC Team Reference 11

5. Number Theory
GCD / LCM
long long gcd(long long a, long long b) { return b ? gcd(b, a%b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a,b) * b; }
// C++17 has __gcd(a,b) built in

Extended GCD
long long extgcd(long long a, long long b, long long &x, long long &y) {
if (!b) { x = 1; y = 0; return a; }
long long x1, y1;
long long g = extgcd(b, a%b, x1, y1);
x = y1; y = x1 - (a/b)*y1;
return g;
}

Sieve of Eratosthenes
vector<bool> isComposite(N+1, false);
vector<int> primes;
for (int i = 2; i <= N; i++) {
if (!isComposite[i]) primes.push_back(i);
for (int p : primes) {
if ((long long)i*p > N) break;
isComposite[i*p] = true;
if (i % p == 0) break;
}
}

Smallest Prime Factor (fast factorization)

vector<int> spf(N+1);
for (int i = 2; i <= N; i++) {
if (!spf[i]) for (int j = i; j <= N; j += i) if (!spf[j]) spf[j] = i;
}
vector<int> factorize(int x) {
vector<int> f;
while (x > 1) { f.push_back(spf[x]); x /= spf[x]; }
return f;
}

Prime factorization (no sieve, O(sqrt n))

vector<pair<long long,int>> factorize(long long n) {
vector<pair<long long,int>> res;
for (long long p = 2; p*p <= n; p++) {
if (n % p == 0) {
int cnt = 0;
while (n % p == 0) { n /= p; cnt++; }
res.push_back({p, cnt});
}
}
if (n > 1) res.push_back({n, 1});
return res;
}
ECPC Team Reference 12

Divisors
vector<long long> divisors(long long n) {
vector<long long> d;
for (long long i = 1; i*i <= n; i++) {
if (n % i == 0) { d.push_back(i); if (i != n/i) d.push_back(n/i); }
}
return d;
}

Modular Arithmetic & Fast Exponentiation

const long long MOD = 1e9+7;
long long power(long long a, long long b, long long mod=MOD) {
a %= mod; long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
long long modinv(long long a, long long mod=MOD) { return power(a, mod-2, mod); } // mod must be prime

Euler's Totient phi

long long phi(long long n) {
long long result = n;
for (long long p = 2; p*p <= n; p++) {
if (n % p == 0) {
while (n % p == 0) n /= p;
result -= result / p;
}
}
if (n > 1) result -= result / n;
return result;
}

Combinations mod p (precompute factorials)

const int MAXN = 1e6+5;
long long fact[MAXN], inv_fact[MAXN];
void precomputeFact() {
fact[0] = 1;
for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
inv_fact[MAXN-1] = modinv(fact[MAXN-1]);
for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
long long C(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

Pascal's Triangle (small n, no mod inverse needed)

vector<vector<long long>> pascal(int n) {
vector<vector<long long>> C(n+1, vector<long long>(n+1, 0));
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
ECPC Team Reference 13

}
return C;
}

Chinese Remainder Theorem (two congruences)

// x = a1 mod m1, x = a2 mod m2 -> returns {x, lcm} or {-1,-1} if no solution
pair<long long,long long> crt(long long a1, long long m1, long long a2, long long m2) {
long long x, y;
long long g = extgcd(m1, m2, x, y);
if ((a2 - a1) % g != 0) return {-1, -1};
long long lcm_ = m1 / g * m2;
long long res = a1 + m1 * ((x * ((a2-a1)/g)) % (m2/g));
res = ((res % lcm_) + lcm_) % lcm_;
return {res, lcm_};
}

Bit tricks
x & (x-1) // remove lowest set bit
x & (-x) // isolate lowest set bit
x | (x-1) // set all bits below lowest set bit
(x >> k) & 1 // check bit k
x = (1 << k) // toggle bit k
ECPC Team Reference 14

6. Recursion / Backtracking
Subsets (bitmask)
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> subset;
for (int i = 0; i < n; i++) if (mask & (1 << i)) subset.push_back(a[i]);
// process subset
}

Subsets (recursive)
void gen(int i, vector<int>& cur) {
if (i == n) { /* process cur */ return; }
gen(i+1, cur); // exclude a[i]
cur.push_back(a[i]);
gen(i+1, cur); // include a[i]
cur.pop_back();
}

Permutations
vector<int> a = {1,2,3};
sort(all(a));
do {
// process permutation a
} while (next_permutation(all(a)));

// or recursive with a "used" array for custom pruning

void permute(vector<int>& cur, vector<bool>& used) {
if ([Link]() == n) { /* process */ return; }
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true; cur.push_back(a[i]);
permute(cur, used);
cur.pop_back(); used[i] = false;
}
}

Combinations (choose r of n)
void comb(int start, vector<int>& cur, int r) {
if ((int)[Link]() == r) { /* process cur */ return; }
for (int i = start; i < n; i++) {
cur.push_back(a[i]);
comb(i+1, cur, r);
cur.pop_back();
}
}

N-Queens pattern (placement with constraint sets)

vector<bool> cols(n), diag1(2*n), diag2(2*n);
int ways = 0;
void solve(int row) {
if (row == n) { ways++; return; }
for (int c = 0; c < n; c++) {
if (cols[c] || diag1[row+c] || diag2[row-c+n]) continue;
cols[c] = diag1[row+c] = diag2[row-c+n] = true;
ECPC Team Reference 15

solve(row+1);
cols[c] = diag1[row+c] = diag2[row-c+n] = false;
}
}

Meet in the Middle

When n <= ~40 and full 2n is too slow but 2(n/2) is ne (subset-sum style).
// split array into two halves, enumerate all subset sums of each half,
// sort one half's sums, binary search / two-pointer across the other half
vector<long long> sumsOfSubsets(vector<int>& arr) {
int m = [Link]();
vector<long long> res;
for (int mask = 0; mask < (1<<m); mask++) {
long long s = 0;
for (int i = 0; i < m; i++) if (mask & (1<<i)) s += arr[i];
res.push_back(s);
}
return res;
}
// combine: sort half B sums, for each sum in half A binary-search target - sumA in B

Pruning techniques
ˆ Sort input rst so bad branches die early.
ˆ Track a running bound (best-so-far) and cut when it can't beat it.
ˆ Memoize repeated states (turns backtracking into DP).
ˆ Order choices smartest-rst (most constrained variable).
ECPC Team Reference 16

7. Graphs
When do I use which shortest-path algorithm?

Situation Algorithm
Unweighted BFS
Weights are only 0 or 1 0-1 BFS (deque)
Positive weights Dijkstra
Negative edges, no negative cycle Bellman-Ford
All-pairs, small n (<= 500) Floyd-Warshall
DAG DP over topo order

Adjacency List
vector<vector<int>> adj(n); // unweighted
adj[u].push_back(v); adj[v].push_back(u); // undirected

vector<vector<pii>> wadj(n); // weighted: {to, weight}

wadj[u].push_back({v, w});

BFS
vector<int> dist(n, -1);
queue<int> q;
dist[src] = 0; [Link](src);
while (![Link]()) {
int u = [Link](); [Link]();
for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u]+1; [Link](v); }
}

DFS (iterative & recursive)

vector<bool> vis(n, false);
void dfs(int u) {
vis[u] = true;
for (int v : adj[u]) if (!vis[v]) dfs(v);
}
// iterative (avoids stack overflow on deep graphs)
void dfsIter(int src) {
stack<int> st; [Link](src);
while (![Link]()) {
int u = [Link](); [Link]();
if (vis[u]) continue;
vis[u] = true;
for (int v : adj[u]) if (!vis[v]) [Link](v);
}
}

Connected Components
int components = 0;
vector<int> comp(n, -1);
for (int i = 0; i < n; i++) {
if (comp[i] == -1) {
// BFS/DFS from i, label every reached node with `components`
components++;
}
}
ECPC Team Reference 17

Grid BFS/DFS
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
bool inside(int r, int c, int R, int C) { return r>=0 && r<R && c>=0 && c<C; }
// standard BFS but neighbors are (r+dr[k], c+dc[k])

Bipartite Check
vector<int> color(n, -1);
bool isBipartite = true;
for (int s = 0; s < n && isBipartite; s++) {
if (color[s] != -1) continue;
queue<int> q; [Link](s); color[s] = 0;
while (![Link]() && isBipartite) {
int u = [Link](); [Link]();
for (int v : adj[u]) {
if (color[v] == -1) { color[v] = color[u]1; [Link](v); }
else if (color[v] == color[u]) { isBipartite = false; break; }
}
}
}

Cycle Detection
// undirected (DSU is simplest, see Section 9) or DFS with parent tracking
// directed: DFS with 3 colors (white/gray/black)  a back-edge to a GRAY node means a cycle
vector<int> state(n, 0); // 0=white,1=gray,2=black
bool hasCycle = false;
void dfs(int u) {
state[u] = 1;
for (int v : adj[u]) {
if (state[v] == 1) hasCycle = true;
else if (state[v] == 0) dfs(v);
}
state[u] = 2;
}

Topological Sort (Kahn's algorithm)

vector<int> indeg(n, 0);
for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
queue<int> q;
for (int i = 0; i < n; i++) if (indeg[i]==0) [Link](i);
vector<int> order;
while (![Link]()) {
int u = [Link](); [Link](); order.push_back(u);
for (int v : adj[u]) if (--indeg[v]==0) [Link](v);
}
// if [Link]() != n -> cycle exists, no valid topo order

DSU (Disjoint Set Union)

struct DSU {
vector<int> parent, rnk;
DSU(int n) : parent(n), rnk(n,0) { iota(all(parent), 0); }
int find(int x) { return parent[x]==x ? x : parent[x]=find(parent[x]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (rnk[a] < rnk[b]) swap(a,b);
ECPC Team Reference 18

parent[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
return true;
}
};

Kruskal's MST
struct Edge { int u, v; long long w; };
vector<Edge> edges; // fill with all edges
sort(all(edges), [](Edge&a, Edge&b){ return a.w < b.w; });
DSU dsu(n);
long long mstWeight = 0; int used = 0;
for (auto& e : edges) {
if ([Link](e.u, e.v)) { mstWeight += e.w; used++; }
}
// used == n-1 means MST connects everything

Prim's MST
vector<bool> inMST(n, false);
priority_queue<pii, vector<pii>, greater<pii>> pq; // {weight, node}
[Link]({0, 0});
long long mstWeight = 0;
while (![Link]()) {
auto [w, u] = [Link](); [Link]();
if (inMST[u]) continue;
inMST[u] = true; mstWeight += w;
for (auto [v, wt] : wadj[u]) if (!inMST[v]) [Link]({wt, v});
}

Dijkstra
vector<long long> dist(n, LLONG_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq; // {dist, node}
dist[src] = 0; [Link]({0, src});
while (![Link]()) {
auto [d, u] = [Link](); [Link]();
if (d > dist[u]) continue;
for (auto [v, w] : wadj[u]) {
if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; [Link]({dist[v], v}); }
}
}

Trap: Dijkstra fails with negative edges  use Bellman-Ford instead.

0-1 BFS
vector<int> dist(n, INT_MAX);
deque<int> dq;
dist[src] = 0; dq.push_back(src);
while (![Link]()) {
int u = [Link](); dq.pop_front();
for (auto [v, w] : wadj[u]) { // w is 0 or 1
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v); else dq.push_back(v);
}
}
}
ECPC Team Reference 19

Bellman-Ford
vector<long long> dist(n, LLONG_MAX);
dist[src] = 0;
for (int i = 0; i < n-1; i++)
for (auto& e : edges) // e = {u, v, w}
if (dist[e.u] != LLONG_MAX && dist[e.u] + e.w < dist[e.v])
dist[e.v] = dist[e.u] + e.w;
// one more pass: if any edge still relaxes, there's a negative cycle

Floyd-Warshall (all pairs)

vector<vector<long long>> d(n, vector<long long>(n, LLONG_MAX/2));
for (int i = 0; i < n; i++) d[i][i] = 0;
// fill d[u][v] = weight for direct edges
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

Strongly Connected Components (Kosaraju)

vector<vector<int>> adj(n), radj(n); // radj = reverse graph
vector<int> order_, comp(n, -1);
vector<bool> vis(n, false);
void dfs1(int u) {
vis[u] = true;
for (int v : adj[u]) if (!vis[v]) dfs1(v);
order_.push_back(u);
}
void dfs2(int u, int c) {
comp[u] = c;
for (int v : radj[u]) if (comp[v] == -1) dfs2(v, c);
}
// 1) dfs1 on all nodes to fill order_
// 2) reverse(order_); 3) dfs2 in that order, incrementing c each time a fresh node starts

Bridges & Articulation Points (Tarjan)

vector<int> disc(n, -1), low(n, -1);
int timer = 0;
vector<pii> bridges;
void dfs(int u, int parent) {
disc[u] = low[u] = timer++;
for (int v : adj[u]) {
if (v == parent) continue;
if (disc[v] == -1) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) bridges.push_back({u, v}); // bridge
} else low[u] = min(low[u], disc[v]);
}
}
// articulation point: for root, needs >=2 DFS children;
// for non-root, some child v has low[v] >= disc[u]
ECPC Team Reference 20

Euler Path / Circuit (Hierholzer)

// Exists (undirected) iff graph connected (ignoring isolated) and 0 or 2 vertices have odd degree
vector<int> path;
void hierholzer(int u, vector<vector<pii>>& adj /* {to, edgeId} */ , vector<bool>& usedEdge) {
stack<int> st; [Link](u);
vector<int> circuit;
stack<int> curPath; [Link](u);
while (![Link]()) {
int v = [Link]();
if (!adj[v].empty()) {
auto [to, id] = adj[v].back(); adj[v].pop_back();
if (usedEdge[id]) continue;
usedEdge[id] = true;
[Link](to);
} else {
path.push_back(v);
[Link]();
}
}
reverse(all(path));
}
ECPC Team Reference 21

8. Trees
Tree DFS + Subtree Sizes
vector<int> subSize(n, 1);
void dfs(int u, int parent) {
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
subSize[u] += subSize[v];
}
}

Tree Diameter (2 BFS/DFS passes)

pair<int,int> farthest(int src) {
vector<int> dist(n, -1); dist[src] = 0;
queue<int> q; [Link](src);
int far = src;
while (![Link]()) {
int u = [Link](); [Link]();
if (dist[u] > dist[far]) far = u;
for (int v : adj[u]) if (dist[v]==-1) { dist[v]=dist[u]+1; [Link](v); }
}
return {far, dist[far]};
}
// auto [a, _] = farthest(0); auto [b, diameter] = farthest(a);

LCA via Binary Lifting

const int LOG = 20;
vector<vector<int>> up(LOG, vector<int>(n));
vector<int> depth(n);
void dfs(int u, int parent) {
up[0][u] = parent;
for (int k = 1; k < LOG; k++) up[k][u] = up[k-1][ up[k-1][u] ];
for (int v : adj[u]) if (v != parent) { depth[v] = depth[u]+1; dfs(v, u); }
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++) if (diff & (1<<k)) u = up[k][u];
if (u == v) return u;
for (int k = LOG-1; k >= 0; k--)
if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
return up[0][u];
}
// root call: depth[root] = 0; dfs(root, root); up[0][root] = root;

Tree DP (basic, e.g. max independent set)

vector<array<long long,2>> dp(n); // dp[u][0]=exclude u, dp[u][1]=include u
void dfs(int u, int parent) {
dp[u][0] = 0; dp[u][1] = val[u];
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
ECPC Team Reference 22

Rerooting Basics
Idea: do one DFS to compute answers rooted at a xed root, then a second DFS that moves the root to each neighbor
by combining parent's rerooted answer with the current subtree answer (add/remove u's own contribution). Useful when
you need the answer for every node as root in O(n) total.
ECPC Team Reference 23

9. Data Structures
Fenwick Tree (Binary Indexed Tree)  point update, prex sum
struct Fenwick {
vector<long long> bit;
int n;
Fenwick(int n) : n(n), bit(n+1, 0) {}
void update(int i, long long delta) { // 1-indexed
for (; i <= n; i += i & (-i)) bit[i] += delta;
}
long long query(int i) { // prefix sum [1, i]
long long s = 0;
for (; i > 0; i -= i & (-i)) s += bit[i];
return s;
}
long long rangeQuery(int l, int r) { return query(r) - query(l-1); }
};

Segment Tree (point update, range sum)

struct SegTree {
int n; vector<long long> tree;
SegTree(int n) : n(n), tree(4*n, 0) {}
void update(int node, int l, int r, int idx, long long val) {
if (l == r) { tree[node] = val; return; }
int mid = (l+r)/2;
if (idx <= mid) update(2*node, l, mid, idx, val);
else update(2*node+1, mid+1, r, idx, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree[node];
int mid = (l+r)/2;
return query(2*node,l,mid,ql,qr) + query(2*node+1,mid+1,r,ql,qr);
}
};

Lazy Segment Tree (range update, range sum)

struct LazySegTree {
int n; vector<long long> tree, lazy;
LazySegTree(int n) : n(n), tree(4*n,0), lazy(4*n,0) {}
void push(int node, int l, int r) {
if (!lazy[node]) return;
tree[node] += lazy[node] * (r-l+1);
if (l != r) { lazy[2*node] += lazy[node]; lazy[2*node+1] += lazy[node]; }
lazy[node] = 0;
}
void update(int node, int l, int r, int ql, int qr, long long val) {
push(node, l, r);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) { lazy[node] += val; push(node, l, r); return; }
int mid = (l+r)/2;
update(2*node,l,mid,ql,qr,val); update(2*node+1,mid+1,r,ql,qr,val);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long query(int node, int l, int r, int ql, int qr) {
push(node, l, r);
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree[node];
ECPC Team Reference 24

int mid = (l+r)/2;

return query(2*node,l,mid,ql,qr) + query(2*node+1,mid+1,r,ql,qr);
}
};

Sparse Table (static range min/max/gcd, O(1) query)

struct SparseTable {
vector<vector<int>> table;
vector<int> logs;
SparseTable(vector<int>& a) {
int n = [Link](), LOG = 32 - __builtin_clz(n);
[Link](LOG, vector<int>(n));
table[0] = a;
for (int k = 1; k < LOG; k++)
for (int i = 0; i + (1<<k) <= n; i++)
table[k][i] = min(table[k-1][i], table[k-1][i + (1<<(k-1))]);
[Link](n+1, 0);
for (int i = 2; i <= n; i++) logs[i] = logs[i/2] + 1;
}
int query(int l, int r) { // inclusive, 0-indexed
int k = logs[r-l+1];
return min(table[k][l], table[k][r - (1<<k) + 1]);
}
};

Monotonic Stack (next greater element)

vector<int> nextGreater(n, -1);
stack<int> st; // indices
for (int i = 0; i < n; i++) {
while (![Link]() && a[[Link]()] < a[i]) { nextGreater[[Link]()] = a[i]; [Link](); }
[Link](i);
}

Monotonic Queue (sliding window minimum)

deque<int> dq; // indices, values increasing front-to-back
vector<int> windowMin;
for (int i = 0; i < n; i++) {
while (![Link]() && a[[Link]()] >= a[i]) dq.pop_back();
dq.push_back(i);
if ([Link]() <= i - k) dq.pop_front();
if (i >= k-1) windowMin.push_back(a[[Link]()]);
}

Trie
struct Trie {
struct Node { int children[26] = {}; bool isEnd = false; };
vector<Node> nodes;
Trie() { nodes.push_back(Node()); }
void insert(const string& s) {
int cur = 0;
for (char c : s) {
int idx = c - 'a';
if (!nodes[cur].children[idx]) { nodes[cur].children[idx] = [Link](); nodes.push_back(Node()); }
cur = nodes[cur].children[idx];
}
ECPC Team Reference 25

nodes[cur].isEnd = true;
}
bool search(const string& s) {
int cur = 0;
for (char c : s) {
int idx = c - 'a';
if (!nodes[cur].children[idx]) return false;
cur = nodes[cur].children[idx];
}
return nodes[cur].isEnd;
}
};
ECPC Team Reference 26

10. Dynamic Programming

1D DP (e.g. climbing stairs / house robber style)
vector<long long> dp(n+1, 0);
dp[0] = 0; dp[1] = a[0];
for (int i = 2; i <= n; i++) dp[i] = max(dp[i-1], dp[i-2] + a[i-1]);

2D DP (grid path count / edit distance style)

vector<vector<long long>> dp(n+1, vector<long long>(m+1, 0));
dp[0][0] = 1;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++) {
if (i>0) dp[i][j] += dp[i-1][j];
if (j>0) dp[i][j] += dp[i][j-1];
}

0/1 Knapsack
vector<long long> dp(W+1, 0);
for (int i = 0; i < n; i++)
for (int w = W; w >= wt[i]; w--) // reverse to avoid reusing item i
dp[w] = max(dp[w], dp[w-wt[i]] + val[i]);
// unbounded knapsack: loop w forward instead of reverse

LIS (Longest Increasing Subsequence)  O(n log n)

vector<int> tails;
for (int x : a) {
auto it = lower_bound(all(tails), x); // use upper_bound for non-decreasing
if (it == [Link]()) tails.push_back(x);
else *it = x;
}
int lisLength = [Link]();

LCS (Longest Common Subsequence)

vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = (s1[i-1]==s2[j-1]) ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);

Grid DP (min path sum)

vector<vector<long long>> dp(n, vector<long long>(m, 0));
dp[0][0] = grid[0][0];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (i==0 && j==0) continue;
long long best = LLONG_MAX;
if (i>0) best = min(best, dp[i-1][j]);
if (j>0) best = min(best, dp[i][j-1]);
dp[i][j] = best + grid[i][j];
}
ECPC Team Reference 27

Bitmask DP (TSP-style)
vector<vector<long long>> dp(1<<n, vector<long long>(n, LLONG_MAX/2));
dp[1][0] = 0; // start at node 0, only node 0 visited
for (int mask = 1; mask < (1<<n); mask++)
for (int u = 0; u < n; u++) {
if (!(mask & (1<<u)) || dp[mask][u] == LLONG_MAX/2) continue;
for (int v = 0; v < n; v++) {
if (mask & (1<<v)) continue;
int nmask = mask | (1<<v);
dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + cost[u][v]);
}
}

Digit DP (count numbers with a property up to N)

string num; // digits of N as string
long long memo[20][2][/*extra state*/ 200];
bool vis[20][2][200];
long long solve(int pos, int tight, int state) {
if (pos == (int)[Link]()) return /* base case check on state */ 1;
if (vis[pos][tight][state]) return memo[pos][tight][state];
vis[pos][tight][state] = true;
int limit = tight ? num[pos]-'0' : 9;
long long res = 0;
for (int d = 0; d <= limit; d++) {
int nstate = state /* transition based on d */ ;
res += solve(pos+1, tight && (d==limit), nstate);
}
return memo[pos][tight][state] = res;
}

Tree DP
See Section 8 (Trees)  max independent set example.

DP Optimization Patterns (when TLE and n is large)

ˆ Monotonic deque optimization: when transition is dp[i] = min/max over window of (dp[j] + cost).
ˆ Divide and conquer optimization: when the optimal split point is monotonic in i.
ˆ Convex hull trick / Li Chao tree: when transition is dp[i] = min_j (dp[j] + b[j]*a[i] + c[j]) (linear
functions).
ˆ Knuth's optimization: for interval DP where opt[i][j-1] <= opt[i][j] <= opt[i+1][j].
ECPC Team Reference 28

11. Strings
Basics
string s = "hello";
[Link](1, 3); // "ell" (start=1, length=3)
[Link]("ll"); // index or string::npos
reverse(all(s));
s += "world";
to_string(123); stoi("123"); stoll("123456789012");

Frequency count
vector<int> freq(26, 0);
for (char c : s) freq[c - 'a']++;

Palindrome check
bool isPalindrome(string s) {
int l = 0, r = [Link]()-1;
while (l < r) if (s[l++] != s[r--]) return false;
return true;
}

String Hashing (polynomial rolling hash)

const long long P = 131, MOD_H = 1e9+7;
vector<long long> hashPow, hashPref;
void buildHash(const string& s) {
int n = [Link]();
[Link](n+1, 1); [Link](n+1, 0);
for (int i = 0; i < n; i++) {
hashPow[i+1] = hashPow[i] * P % MOD_H;
hashPref[i+1] = (hashPref[i] * P + s[i]) % MOD_H;
}
}
long long getHash(int l, int r) { // substring [l, r], 0-indexed inclusive
return ((hashPref[r+1] - hashPref[l] * hashPow[r-l+1]) % MOD_H + MOD_H) % MOD_H;
}
// Use TWO different (P, MOD) pairs in real contests to avoid collisions.

KMP (pattern matching, O(n+m))

vector<int> buildPi(const string& p) {
int m = [Link]();
vector<int> pi(m, 0);
for (int i = 1; i < m; i++) {
int j = pi[i-1];
while (j > 0 && p[i] != p[j]) j = pi[j-1];
if (p[i] == p[j]) j++;
pi[i] = j;
}
return pi;
}
vector<int> kmpSearch(const string& text, const string& pattern) {
vector<int> pi = buildPi(pattern), occurrences;
int j = 0;
for (int i = 0; i < (int)[Link](); i++) {
while (j > 0 && text[i] != pattern[j]) j = pi[j-1];
ECPC Team Reference 29

if (text[i] == pattern[j]) j++;

if (j == (int)[Link]()) { occurrences.push_back(i - j + 1); j = pi[j-1]; }
}
return occurrences;
}

Z-function
vector<int> zFunction(const string& s) {
int n = [Link]();
vector<int> z(n, 0);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i < r) z[i] = min(r-i, z[i-l]);
while (i+z[i] < n && s[z[i]] == s[i+z[i]]) z[i]++;
if (i+z[i] > r) { l = i; r = i+z[i]; }
}
return z;
}
// z[i] = length of longest common prefix of s and s[i:]
// pattern matching: run on pattern + '#' + text, look for z[i] == [Link]()

Manacher's Algorithm (longest palindromic substring, O(n))

string preprocess(const string& s) {
string t = "";
for (char c : s) { t += "#"; t += c; }
t += "#$";
return t;
}
vector<int> manacher(const string& s) {
string t = preprocess(s);
int n = [Link]();
vector<int> p(n, 0);
int center = 0, right = 0;
for (int i = 1; i < n-1; i++) {
if (i < right) p[i] = min(right - i, p[2*center - i]);
while (t[i+p[i]+1] == t[i-p[i]-1]) p[i]++;
if (i + p[i] > right) { center = i; right = i + p[i]; }
}
return p; // p[i] = radius of palindrome centered at t[i]
}

Aho-Corasick (multi-pattern matching)

struct AhoCorasick {
struct Node {
map<char,int> next;
int fail = 0;
bool isEnd = false;
};
vector<Node> trie;
AhoCorasick() { trie.push_back(Node()); }
void insert(const string& s) {
int cur = 0;
for (char c : s) {
if (!trie[cur].[Link](c)) { trie[cur].next[c] = [Link](); trie.push_back(Node()); }
cur = trie[cur].next[c];
}
trie[cur].isEnd = true;
ECPC Team Reference 30

}
void buildFail() {
queue<int> q;
for (auto& [c, v] : trie[0].next) { trie[v].fail = 0; [Link](v); }
while (![Link]()) {
int u = [Link](); [Link]();
for (auto& [c, v] : trie[u].next) {
trie[v].fail = trie[trie[u].fail].[Link](c) ? trie[trie[u].fail].next[c] : 0;
[Link](v);
}
}
}
};
ECPC Team Reference 31

12. Greedy
Sorting-based Greedy
Sort by a key that makes the locally-best choice also globally optimal, then sweep once. Always sanity-check against samples
 greedy is wrong more often than it looks right.

Interval Scheduling (max non-overlapping intervals)

sort(all(intervals), [](auto&a, auto&b){ return [Link] < [Link]; }); // sort by end time
int count = 0; long long lastEnd = LLONG_MIN;
for (auto& [s, e] : intervals) if (s >= lastEnd) { count++; lastEnd = e; }

Activity Selection / Minimum Rooms (interval overlap count)

vector<pair<int,int>> events; // {time, +1 start / -1 end}
for (auto& [s, e] : intervals) { events.push_back({s, 1}); events.push_back({e, -1}); }
sort(all(events)); // ties: process -1 before +1 if intervals are [s, e)
int cur = 0, maxOverlap = 0;
for (auto& [t, delta] : events) { cur += delta; maxOverlap = max(maxOverlap, cur); }

Exchange Argument (intuition)

To prove a greedy correct: assume an optimal solution that does NOT follow the greedy rule, show you can swap two
adjacent elements to make it follow the rule without making the answer worse. If that's always possible, greedy is optimal.

Common Min/Max Patterns

ˆ Minimize max value -> binary search on answer + greedy feasibility check.
ˆ Maximize count of selections -> sort by cost or nish time and take greedily.
ˆ Fractional assignment -> sort by ratio (e.g. fractional knapsack: value/weight).
ECPC Team Reference 32

13. Geometry
Point / Vector
struct Point { double x, y; };
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
Point operator+(Point a, Point b) { return {a.x+b.x, a.y+b.y}; }

Dot Product & Cross Product

double dot(Point a, Point b) { return a.x*b.x + a.y*b.y; }
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }
// cross(b-a, c-a) > 0 -> c is to the left of ab (counter-clockwise turn)
// cross == 0 -> collinear ; cross < 0 -> clockwise turn

Orientation
int orientation(Point a, Point b, Point c) {
double val = cross({b.x-a.x, b.y-a.y}, {c.x-a.x, c.y-a.y});
if (val > 1e-9) return 1; // counter-clockwise
if (val < -1e-9) return -1; // clockwise
return 0; // collinear
}

Distance
double dist(Point a, Point b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); }

Line / Segment Intersection

bool onSegment(Point p, Point q, Point r) { // q on segment pr, assuming collinear
return min(p.x,r.x)<=q.x && q.x<=max(p.x,r.x) && min(p.y,r.y)<=q.y && q.y<=max(p.y,r.y);
}
bool segmentsIntersect(Point p1, Point q1, Point p2, Point q2) {
int o1 = orientation(p1,q1,p2), o2 = orientation(p1,q1,q2);
int o3 = orientation(p2,q2,p1), o4 = orientation(p2,q2,q1);
if (o1 != o2 && o3 != o4) return true;
if (o1==0 && onSegment(p1,p2,q1)) return true;
if (o2==0 && onSegment(p1,q2,q1)) return true;
if (o3==0 && onSegment(p2,p1,q2)) return true;
if (o4==0 && onSegment(p2,q1,q2)) return true;
return false;
}

Polygon Area (Shoelace formula)

double polygonArea(vector<Point>& poly) {
double area = 0;
int n = [Link]();
for (int i = 0; i < n; i++) {
int j = (i+1) % n;
area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
}
return fabs(area) / 2.0;
}
ECPC Team Reference 33

Convex Hull (Andrew's monotone chain)

vector<Point> convexHull(vector<Point> pts) {
int n = [Link](), k = 0;
if (n < 3) return pts;
sort([Link](), [Link](), [](Point a, Point b){ return a.x<b.x || (a.x==b.x && a.y<b.y); });
vector<Point> hull(2*n);
for (int i = 0; i < n; i++) { // lower hull
while (k>=2 && orientation(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
hull[k++] = pts[i];
}
for (int i = n-2, t = k+1; i >= 0; i--) { // upper hull
while (k>=t && orientation(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
hull[k++] = pts[i];
}
[Link](k-1);
return hull;
}
ECPC Team Reference 34

14. Advanced / Emergency Pages

Max Flow (Dinic's algorithm)
struct Dinic {
struct Edge { int to; long long cap, flow; };
vector<Edge> edges;
vector<vector<int>> g;
vector<int> level, it;
int n, s, t;
Dinic(int n) : n(n), g(n), level(n), it(n) {}
void addEdge(int u, int v, long long cap) {
g[u].push_back([Link]()); edges.push_back({v, cap, 0});
g[v].push_back([Link]()); edges.push_back({u, 0, 0});
}
bool bfs() {
fill(all(level), -1); queue<int> q; level[s]=0; [Link](s);
while (![Link]()) {
int u = [Link](); [Link]();
for (int id : g[u]) {
auto& e = edges[id];
if ([Link] - [Link] > 0 && level[[Link]] < 0) { level[[Link]] = level[u]+1; [Link]([Link]); }
}
}
return level[t] >= 0;
}
long long dfs(int u, long long pushed) {
if (u == t || pushed == 0) return pushed;
for (int& i = it[u]; i < (int)g[u].size(); i++) {
int id = g[u][i]; auto& e = edges[id];
if (level[u]+1 != level[[Link]] || [Link] - [Link] <= 0) continue;
long long d = dfs([Link], min(pushed, [Link] - [Link]));
if (d > 0) { [Link] += d; edges[id1].flow -= d; return d; }
}
return 0;
}
long long maxflow(int s_, int t_) {
s = s_; t = t_; long long flow = 0;
while (bfs()) {
fill(all(it), 0);
long long pushed;
while ((pushed = dfs(s, LLONG_MAX))) flow += pushed;
}
return flow;
}
};
// Min cut = max flow value; edges on the min cut are saturated edges reachable from s after last bfs

Bipartite Matching (via Dinic, or Kuhn's algorithm)

// Kuhn's algorithm  simple, O(V*E)
vector<vector<int>> adj; // left side adjacency to right side indices
vector<int> matchR; // matchR[v] = which left node matches right node v, -1 if none
vector<bool> used;
bool tryKuhn(int u) {
for (int v : adj[u]) {
if (used[v]) continue;
used[v] = true;
if (matchR[v] == -1 || tryKuhn(matchR[v])) { matchR[v] = u; return true; }
}
return false;
}
// for each left node u: fill(all(used), false); if (tryKuhn(u)) matching++;
ECPC Team Reference 35

Min-Cost Max-Flow (SPFA / Bellman-Ford based augmenting)

Same structure as Dinic but each edge also has a cost; instead of BFS by levels, nd the shortest (min-cost) augmenting
path with SPFA/Bellman-Ford (or Dijkstra + potentials for non-negative costs), then push ow along it and repeat.

Matrix Exponentiation (linear recurrences in O(log n))

typedef vector<vector<long long>> Matrix;
Matrix multiply(Matrix& A, Matrix& B) {
int n = [Link](), m = B[0].size(), k = [Link]();
Matrix C(n, vector<long long>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int l = 0; l < k; l++)
C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % MOD;
return C;
}
Matrix matpow(Matrix A, long long p) {
int n = [Link]();
Matrix res(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) res[i][i] = 1; // identity
while (p > 0) {
if (p & 1) res = multiply(res, A);
A = multiply(A, A);
p >>= 1;
}
return res;
}
// e.g. Fibonacci: [[1,1],[1,0]]n gives F(n+1), F(n)

FFT Overview (polynomial multiplication in O(n log n))

Convert both polynomials to point-value form via FFT, multiply pointwise, then inverse-FFT back to coecient form. In
contests, prefer a tested library implementation (NTT with a prime like 998244353 for modular results, avoids oating-point
error). Don't hand-roll FFT under time pressure unless you have it memorized cold.

Ternary Search (unimodal function optimization)

double ternarySearch(double lo, double hi, function<double(double)> f) {
for (int i = 0; i < 100; i++) {
double m1 = lo + (hi-lo)/3, m2 = hi - (hi-lo)/3;
if (f(m1) < f(m2)) lo = m1; else hi = m2; // for finding minimum
}
return lo;
}

Randomization (treaps, random pivots, anti-hash defense)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randInt(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
// use for: randomized pivot in quickselect, treap priorities, shuffling to avoid worst-case inputs

Game Theory / Sprague-Grundy

// Grundy number of a position = mex (minimum excludant) of grundy values of all reachable positions
int grundy(int state) {
if (/* terminal / losing position */ false) return 0;
set<int> reachable;
// for each move, [Link](grundy(nextState));
int mex = 0;
ECPC Team Reference 36

while ([Link](mex)) mex++;

return mex;
}
// Combined game (Sprague-Grundy theorem): XOR the grundy numbers of independent sub-games.
// grundy != 0 -> first player wins (for normal play convention).
ECPC Team Reference 37

15. Things I ALWAYS Forget

ˆ lower_bound(v) -> rst element >= x. upper_bound(v) -> rst element > x.
ˆ gcd(a,b) works ne with long long  but casting matters, watch for overow before calling it.
ˆ priority_queue<int, vector<int>, greater<int>> = min-heap. Default priority_queue<int> = max-heap.
ˆ iota([Link](), [Link](), 0) lls 0,1,2,3,. . .
ˆ __builtin_popcountll(x) for long long popcount; plain __builtin_popcount(x) is int-only.
ˆ Don't use int for multiplication if values can overow  cast to long long before multiplying, not after.
ˆ mid = l + (r-l)/2  never (l+r)/2, it can overow.
ˆ Dijkstra + negative edge weight = wrong answer, not just slow. Use Bellman-Ford.
ˆ BFS gives shortest path only when all edges have equal weight (or use 0-1 BFS / Dijkstra otherwise).
ˆ Reset global arrays / adjacency lists between test cases in multi-test problems  this is the #1 cause of
mystery WA.
ˆ memset only works correctly for 0 and -1 on int arrays (byte-wise ll)  not for arbitrary values.
ˆ Recursive DFS on a graph with up to ~1e5+ nodes can stack overow  prefer iterative or raise stack size / use
#pragma tricks if allowed.
ˆ Reading input faster: ios_base::sync_with_stdio(false); [Link](nullptr);  but then never mix cin/cout
with scanf/printf.
ˆ set::erase(iterator) invalidates that iterator  don't use it after erasing.
ˆ Modulo with negative numbers in C++ can be negative: ((a % m) + m) % m to normalize.
ˆ Array size o-by-one: if n up to 2e5, declare arrays with size 2e5 + 5, not exactly 2e5.
ˆ sort + unique needs the sort rst  unique only removes consecutive duplicates.
ˆ Always double-check whether the problem is 0-indexed or 1-indexed before coding.
ECPC Team Reference 38

16. Formula Sheet

Combinatorics - Permutations of n: n! - k-permutations of n: n! / (n-k)! - Combinations: C(n,k) = n! /
(k!(n-k)!) - Stars and bars (non-negative solutions to x1+. . . +xk = n): C(n+k-1, k-1) - Catalan number: C(2n,n) /
(n+1)
Sums - 1 + 2 + ... + n = n(n+1)/2 - 12 + 22 + ... + n2 = n(n+1)(2n+1)/6 - Geometric series: a + ar + ar2
+ ... + ar(n-1) = a(rn - 1)/(r - 1) (r != 1)
Number Theory - Number of divisors of n = p1a1 * p2a2 * ... is (a1+1)(a2+1)... - Sum of divisors: prod
(p_i(a_i+1) - 1)/(p_i - 1) - Euler's theorem: if gcd(a,m)=1, then aphi(m) === 1 (mod m) - Fermat's little theorem
(m prime): a(m-1) === 1 (mod m)
Geometry - Triangle area (Heron's): sqrt(s(s-a)(s-b)(s-c)), s = (a+b+c)/2 - Circle: area = pir2, circumference =
2pir - Distance point to line ax+by+c=0: |ax0+by0+c| / sqrt(a2+b2)
ECPC Team Reference 39

17. Common Bugs & Edge Cases Checklist

Before submitting, check:
□ Integer overow  did any product/sum exceed int range (~2.1e9)? Use long long.
□ Empty input / n = 0 / n = 1 handled?
□ Multiple test cases  are all global arrays/variables reset each case?
□ Array bounds  indices exactly at n or 0?
□ Negative numbers in modulo arithmetic normalized?
□ Read the constraints again  did you assume a smaller n than the real limit?
□ Time limit  will your complexity actually t within it for the maximum n?
□ Did you print exactly the required output format (spaces, newlines, precision)?
□ For oating point output, did you set the right precision (cout << fixed << setprecision(k))?
□ Self-loops / duplicate edges in graph problems?
□ Disconnected graph  does your solution assume connectivity?
□ O-by-one in binary search bounds (<= vs <)?
ECPC Team Reference 40

18. Constraint -> Technique Quick Table

Clue in problem statement Likely technique
n <= 20 Bitmask DP / brute force
with pruning
n <= 500, O(n3) ts Floyd-Warshall, simple 3D
DP
n <= 2000-5000 O(n2) DP or two pointers
n <= 2e5, sum of subarray Prex sums / Fenwick
n <= 2e5, range update range query Lazy segment tree
n <= 2e5, shortest path, weighted Dijkstra
n <= 1e5, tree, ancestor / distance between nodes LCA + binary lifting
n <= 1e6, string matching KMP / Z-function / hashing
min possible maximum / max possible minimum Binary search on answer
count subsets with property Bitmask DP or standard
subset DP
values up to 1e9 but only ~n distinct used Coordinate compression
game, two players, optimal play Game theory / Grundy /
simple DP
graph connectivity, oine queries DSU
Grid, n,m <= ~1000 BFS/DFS or grid DP
ECPC Team Reference 41

19. Debug & Contest Workow

1. Read the whole problem twice before coding  note constraints explicitly.
2. Write a brute force rst if the smart solution isn't obvious; use it to stress-test.
3. Code the template, not from scratch  copy from this book, then adapt.
4. Test on samples exactly as given before anything else.
5. Consider edge cases: n=0, n=1, all equal elements, all same sign, maximum n.
6. If WA and samples pass: check overow, reset-between-testcases, o-by-one, output format.
7. If TLE: re-check the complexity table (Section 2) against actual n.
8. If stuck > 20-30 min on one approach with no progress, step back and re-read constraints  you may be missing the
intended technique.

End of reference. Good luck at ECPC.