> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Quick Reference Card

> Essential formulas, complexities, and patterns for quick lookup during contests

# 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

```cpp theme={null}
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)

```cpp theme={null}
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)

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
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)

```cpp theme={null}
ll modinv(ll a, ll p) { return power(a, p - 2, p); }
```

### Combinations (nCr)

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
// 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

```cpp theme={null}
int x = stoi(s);
ll x = stoll(s);
```

### Int to String

```cpp theme={null}
string s = to_string(x);
```

### Split by Delimiter

```cpp theme={null}
stringstream ss(s);
string token;
while (getline(ss, token, ',')) {
    // process token
}
```

### Check Palindrome

```cpp theme={null}
string t = s;
reverse(t.begin(), t.end());
bool isPalin = (s == t);
```

***

## Direction Arrays

```cpp theme={null}
// 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

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
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

```cpp theme={null}
// 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

<Warning>
  **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'`?
</Warning>

***

<Card title="Back to Overview" icon="arrow-left" href="/courses/competitive-programming/00-overview">
  Return to the course curriculum.
</Card>