Quick Reference Card
Time Complexity Limits
| Constraint | Max Complexity | Example Algorithm |
|---|---|---|
| n ≤ 10 | O(n!) | Brute force permutations |
| n ≤ 20 | O(2^n × n) | Bitmask DP |
| n ≤ 100 | O(n³) | Floyd-Warshall |
| n ≤ 500 | O(n³) | Matrix chain DP |
| n ≤ 3,000 | O(n²) | 2D DP, all pairs |
| n ≤ 10⁵ | O(n log n) | Sorting, segment tree |
| n ≤ 10⁶ | O(n) | Linear algorithms |
| n ≤ 10⁸ | O(n) careful | Very simple O(n) |
| n ≤ 10⁹ | O(√n) or O(log n) | Binary search, math |
| n ≤ 10¹⁸ | O(log n) | Binary exponentiation |
Common Constants
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const long long INF = 1e18;
const int IINF = 1e9;
const double EPS = 1e-9;
const double PI = acos(-1.0);
STL Complexity Reference
vector
| Operation | Complexity |
|---|---|
push_back | O(1) amortized |
pop_back | O(1) |
Access [i] | O(1) |
insert at position | O(n) |
erase at position | O(n) |
size | O(1) |
set / map
| Operation | Complexity |
|---|---|
insert | O(log n) |
find | O(log n) |
erase | O(log n) |
lower_bound | O(log n) |
begin / rbegin | O(1) |
unordered_set / unordered_map
| Operation | Complexity |
|---|---|
insert | O(1) avg, O(n) worst |
find | O(1) avg, O(n) worst |
erase | O(1) avg |
priority_queue
| Operation | Complexity |
|---|---|
push | O(log n) |
pop | O(log n) |
top | O(1) |
Binary Search Templates
Lower Bound (First ≥ target)
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] >= target) hi = mid;
else lo = mid + 1;
}
// lo is the answer
Upper Bound (First > target)
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] > target) hi = mid;
else lo = mid + 1;
}
Binary Search on Answer
int lo = MIN_ANS, hi = MAX_ANS;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isPossible(mid)) hi = mid; // Minimize answer
else lo = mid + 1;
}
Graph Templates
DFS
vector<bool> vis(n + 1);
function<void(int)> dfs = [&](int u) {
vis[u] = true;
for (int v : adj[u]) {
if (!vis[v]) dfs(v);
}
};
BFS
vector<int> dist(n + 1, -1);
queue<int> q;
q.push(start);
dist[start] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
Dijkstra
vector<ll> dist(n + 1, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
Number Theory Formulas
GCD / LCM
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } // Prevent overflow
Modular Exponentiation
ll power(ll base, ll exp, ll mod) {
ll res = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) res = res * base % mod;
base = base * base % mod;
exp >>= 1;
}
return res;
}
Modular Inverse (p prime)
ll modinv(ll a, ll p) { return power(a, p - 2, p); }
Combinations (nCr)
ll C(int n, int r) {
if (r > n || r < 0) return 0;
return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}
Check Prime
bool isPrime(ll n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (ll i = 3; i * i <= n; i += 2)
if (n % i == 0) return false;
return true;
}
Bit Manipulation
// Check if i-th bit is set (0-indexed)
(n >> i) & 1
// Set i-th bit
n | (1LL << i)
// Clear i-th bit
n & ~(1LL << i)
// Toggle i-th bit
n ^ (1LL << i)
// Get lowest set bit
n & (-n)
// Clear lowest set bit
n & (n - 1)
// Count set bits
__builtin_popcount(n) // int
__builtin_popcountll(n) // long long
// Check power of 2
n && !(n & (n - 1))
// Iterate all subsets of mask
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { }
String Patterns
String to Int/LL
int x = stoi(s);
ll x = stoll(s);
Int to String
string s = to_string(x);
Split by Delimiter
stringstream ss(s);
string token;
while (getline(ss, token, ',')) {
// process token
}
Check Palindrome
string t = s;
reverse(t.begin(), t.end());
bool isPalin = (s == t);
Direction Arrays
// 4 directions (up, down, left, right)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 8 directions
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// Usage
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// valid cell
}
}
Common Patterns
Coordinate Compression
vector<int> vals = arr;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int& x : arr) {
x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}
Prefix Sum
vector<ll> pre(n + 1);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
// Sum [l, r] = pre[r + 1] - pre[l]
Two Pointers
int l = 0, r = 0;
while (r < n) {
// Expand: add arr[r]
while (/* condition broken */) {
// Contract: remove arr[l]
l++;
}
// Update answer
r++;
}
Output Formatting
// YES/NO
cout << (ans ? "YES" : "NO") << '\n';
// Fixed precision
cout << fixed << setprecision(9) << x << '\n';
// Vector with spaces
for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n-1];
// Multiple values
for (int x : v) cout << x << ' ';
cout << '\n';
Contest Checklist
Before Submitting:
- Integer overflow? Use
long long - Array bounds?
n + 5safety - Division by zero?
- Edge cases? n=0, n=1
- Reset globals between test cases?
- Correct output format?
-
endlvs'\n'?
Back to Overview
Return to the course curriculum.