Skip to main content

Quick Reference Card

Time Complexity Limits

ConstraintMax ComplexityExample Algorithm
n ≤ 10O(n!)Brute force permutations
n ≤ 20O(2^n × n)Bitmask DP
n ≤ 100O(n³)Floyd-Warshall
n ≤ 500O(n³)Matrix chain DP
n ≤ 3,000O(n²)2D DP, all pairs
n ≤ 10⁵O(n log n)Sorting, segment tree
n ≤ 10⁶O(n)Linear algorithms
n ≤ 10⁸O(n) carefulVery 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

OperationComplexity
push_backO(1) amortized
pop_backO(1)
Access [i]O(1)
insert at positionO(n)
erase at positionO(n)
sizeO(1)

set / map

OperationComplexity
insertO(log n)
findO(log n)
eraseO(log n)
lower_boundO(log n)
begin / rbeginO(1)

unordered_set / unordered_map

OperationComplexity
insertO(1) avg, O(n) worst
findO(1) avg, O(n) worst
eraseO(1) avg

priority_queue

OperationComplexity
pushO(log n)
popO(log n)
topO(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 + 5 safety
  • Division by zero?
  • Edge cases? n=0, n=1
  • Reset globals between test cases?
  • Correct output format?
  • endl vs '\n'?

Back to Overview

Return to the course curriculum.