problemSolvingSheet.md

ICPC Contest Problem-Solving Reference Sheet

---

Table of Contents

#	Section	Page
1	General Problem-Solving Strategy	2
2	Last-Minute Contest Checklist	2
3	Input/Output Pitfalls	3
4	Typical Constraints → Algorithm Choice	3
5	Time Complexity Cheat Sheet	4
6	How to Recognize Problem Types	4
7	Algorithm Selection Guide	5
8	Common Data Structures	6
9	Graph Algorithms	8
10	Dynamic Programming Patterns	12
11	Greedy Strategies	15
12	Binary Search Patterns	16
13	Math for Competitive Programming	17
14	Number Theory	18
15	Combinatorics	20
16	Geometry Basics	21
17	String Algorithms	23
18	Bit Manipulation Tricks	25
19	Common Implementation Patterns	26
20	Common ICPC Tricks	27
21	Debugging During Contests	28
22	Edge Case Checklist	29

---

1. General Problem-Solving Strategy

The First 5 Minutes (per problem):

1. Read carefully — underline constraints, output format, special cases
2. Identify the problem type — see §6 Recognition Guide
3. Check constraints — see §4 to pick the right algorithm class
4. Think of the simplest approach first — brute force, then optimize
5. Write on paper before coding — sketch the algorithm, edge cases

During Implementation:

• Code in small testable pieces; compile/test after each function
• Use simple variable names consistently (n, m, adj, dist, dp)
• Don't optimize prematurely — get a correct solution first
• If stuck > 15 min, switch problems

Penalty Minimization:

• Solve easy problems first (read all problems in first 10 min)
• One person codes, others read and think
• Test before submitting — use sample cases + 1 edge case
• Wrong Answer > re-read the problem statement

---

2. Last-Minute Contest Checklist

□ Compiler flags: g++ -O2 -std=c++17 -Wall
□ Template ready (fast I/O, includes, typedefs)
□ Know your judge's stack size (recursion limit)
□ Coordinate roles: coder / thinker / tester
□ Print reference sheets
□ Extra pens, paper, rubber duck

Fast I/O template (C++):

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // ...
}

Fast I/O template (Java):

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

---

3. Input/Output Pitfalls

Pitfall	Fix
Slow I/O (TLE with cin/cout)	ios::sync_with_stdio(false); cin.tie(nullptr);
Mixing scanf/printf with cin/cout	Pick one. Don't mix.
Not reading until EOF	while(cin >> n) or while(scanf("%d",&n)!=EOF)
Trailing whitespace in output	Check judge's exact format
\n vs endl	Use \n — endl flushes and is slow
Multiple test cases — not resetting	Clear all global arrays/vectors between cases
32-bit overflow	Use long long when $n > 10^5$ or products involved
Off-by-one in 0-indexed vs 1-indexed	Decide once, stay consistent
Forgetting to read remaining input	Read full line after nextInt() in Java

---

4. Typical Constraints → Algorithm Choice

Constraint on N	Max Operations ≈	Viable Algorithms
$N \leq 10$	$N!$ ≈ 3.6M	Brute force, permutations, bitmask over all subsets
$N \leq 20$	$2^N$ ≈ 1M	Bitmask DP, meet-in-the-middle ($2^{N/2}$)
$N \leq 25$	$2^N$ ≈ 33M	Bitmask DP (tight), meet-in-the-middle
$N \leq 100$	$N^3$ ≈ 1M	Floyd-Warshall, matrix exponentiation, $O(N^3)$ DP
$N \leq 500$	$N^3$ ≈ 125M	$O(N^3)$ with small constant
$N \leq 5000$	$N^2$ ≈ 25M	$O(N^2)$ DP, pairwise comparisons
$N \leq 10^5$	$N \sqrt{N}$ or $N \log N$	Sorting, binary search, segment trees, BIT
$N \leq 10^6$	$O(N)$ or $O(N \log N)$	Linear scan, hashing, two pointers, suffix array
$N \leq 10^7$	$O(N)$	Sieve, linear DP, prefix sums
$N \leq 10^{18}$	$O(\log N)$ or $O(\sqrt{N})$	Math, binary exponentiation, matrix exponentiation

Rule of thumb: ~$10^8$ simple operations per second in C++.

---

5. Time Complexity Cheat Sheet

Complexity	Name	Typical Use
$O(1)$	Constant	Formula, hash lookup
$O(\log N)$	Logarithmic	Binary search, exponentiation
$O(\sqrt{N})$	Square root	Factorization, block decomposition
$O(N)$	Linear	Single pass, counting
$O(N \log N)$	Linearithmic	Sorting, merge sort, segment tree queries
$O(N^2)$	Quadratic	Nested loops, simple DP
$O(N^2 \log N)$		Sorting + quadratic
$O(N^3)$	Cubic	Floyd-Warshall, matrix multiply
$O(2^N)$	Exponential	Subsets, bitmask DP
$O(N!)$	Factorial	Permutations

Master Theorem (for $T(n)=aT(n/b)+O(n^d)$):

• If $d < \log_b a$: $O(n^{\log_b a})$
• If $d = \log_b a$: $O(n^d \log n)$
• If $d > \log_b a$: $O(n^d)$

---

6. How to Recognize Problem Types

If you see...	Think about...
"Minimum/maximum of something"	DP, greedy, binary search on answer
"Count the number of ways"	DP, combinatorics, math
"Shortest path"	BFS (unweighted), Dijkstra, Bellman-Ford
"Connected components"	DFS/BFS, Union-Find
"Can you do X in at most K?"	Binary search on answer
"Lexicographically smallest"	Greedy (take smallest valid choice)
"Subsequence"	DP (LIS, LCS), two pointers
"Substring / pattern matching"	KMP, Z-function, hashing
"All pairs of …"	Floyd-Warshall, BFS from each node
"Tree + queries"	LCA, Euler tour, HLD
"Interval/range queries"	Segment tree, BIT, sparse table
"Grid with obstacles"	BFS, DP on grid
"Matching / assignment"	Bipartite matching, Hungarian
"Flow / cut"	Max-flow (Dinic's)
"Modular arithmetic, large N"	Matrix exponentiation, Fermat's little theorem
"XOR of elements"	Trie on bits, linear basis
"GCD / LCM"	Euclidean algorithm, prime factorization
"Geometry: intersections"	Cross product, sweep line
"Game theory, winning/losing"	Sprague-Grundy, Nim
"String periodicity"	KMP failure function, Z-array
"$N \leq 20$, minimize over subsets"	Bitmask DP
"Online queries, dynamic updates"	Segment tree with lazy, BIT

---

7. Algorithm Selection Guide

Given a problem category, pick the technique:

Searching

Scenario	Algorithm	Complexity
Sorted array, find element	Binary search	$O(\log N)$
Unsorted, find element	Linear scan or hash set	$O(N)$ / $O(1)$
Find kth smallest	Quickselect / nth_element	$O(N)$ avg
Answer is monotonic	Binary search on answer	$O(\log V \cdot \text{check})$

Sorting

Scenario	Algorithm	Complexity
General sort	std::sort (introsort)	$O(N \log N)$
Stable sort needed	std::stable_sort	$O(N \log N)$
Integers in range [0, K]	Counting sort	$O(N + K)$
Custom ordering / events	Sort by key + sweep	$O(N \log N)$

Shortest Path

Scenario	Algorithm	Complexity
Unweighted graph	BFS	$O(V + E)$
Non-negative weights	Dijkstra (priority queue)	$O((V+E) \log V)$
Negative weights, no neg cycle	Bellman-Ford	$O(VE)$
All-pairs, $V \leq 500$	Floyd-Warshall	$O(V^3)$
DAG	Topological sort + relaxation	$O(V + E)$
0-1 weights	0-1 BFS (deque)	$O(V + E)$

Minimum Spanning Tree

Scenario	Algorithm	Complexity
Dense graph	Prim's	$O(V^2)$ or $O(E \log V)$
Sparse graph	Kruskal's (sort + DSU)	$O(E \log E)$

---

8. Common Data Structures

8.1 Disjoint Set Union (Union-Find)

• When: Connected components, Kruskal's MST, dynamic connectivity
• Complexity: $O(\alpha(N))$ per operation (nearly constant)
• Key idea: Path compression + union by rank

int par[MAXN], rnk[MAXN];
void init(int n){ iota(par,par+n,0); fill(rnk,rnk+n,0); }
int find(int x){ return par[x]==x ? x : par[x]=find(par[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);
    par[b]=a; if(rnk[a]==rnk[b]) rnk[a]++;
    return true;
}

• Mistakes: Forgetting to call find() before comparing; not initializing parent array.

---

8.2 Binary Indexed Tree (Fenwick Tree / BIT)

• When: Prefix sum queries + point updates; count inversions
• Complexity: $O(\log N)$ per query/update
• Key idea: Each index stores partial sum based on lowest set bit

int bit[MAXN];
void update(int i, int delta, int n){
    for(; i<=n; i+=i&(-i)) bit[i]+=delta;
}
int query(int i){
    int s=0; for(; i>0; i-=i&(-i)) s+=bit[i]; return s;
}
int query(int l, int r){ return query(r)-query(l-1); } // 1-indexed

• Mistakes: Using 0-indexed (BIT is 1-indexed); forgetting to clear between test cases.

---

8.3 Segment Tree

• When: Range queries + range/point updates (sum, min, max, GCD)
• Complexity: $O(\log N)$ per operation; $O(N)$ build
• Key idea: Divide-and-conquer on intervals, store answers in nodes

int tree[4*MAXN], lazy[4*MAXN];
void build(int v, int tl, int tr, int a[]){
    if(tl==tr){ tree[v]=a[tl]; return; }
    int tm=(tl+tr)/2;
    build(2*v,tl,tm,a); build(2*v+1,tm+1,tr,a);
    tree[v]=tree[2*v]+tree[2*v+1];
}
void push(int v){
    if(lazy[v]){
        tree[2*v]+=lazy[v]; lazy[2*v]+=lazy[v];
        tree[2*v+1]+=lazy[v]; lazy[2*v+1]+=lazy[v];
        lazy[v]=0;
    }
}
void update(int v, int tl, int tr, int l, int r, int val){
    if(l>tr||r<tl) return;
    if(l<=tl&&tr<=r){ tree[v]+=val; lazy[v]+=val; return; }
    push(v); int tm=(tl+tr)/2;
    update(2*v,tl,tm,l,r,val); update(2*v+1,tm+1,tr,l,r,val);
    tree[v]=tree[2*v]+tree[2*v+1];
}
int query(int v, int tl, int tr, int l, int r){
    if(l>tr||r<tl) return 0;
    if(l<=tl&&tr<=r) return tree[v];
    push(v); int tm=(tl+tr)/2;
    return query(2*v,tl,tm,l,r)+query(2*v+1,tm+1,tr,l,r);
}

• Mistakes: Array size 4*N not 2*N; forgetting lazy propagation push; wrong merge function.

---

8.4 Sparse Table

• When: Static range minimum/maximum queries (no updates)
• Complexity: $O(N \log N)$ build, $O(1)$ query
• Key idea: Precompute answers for every power-of-2 length interval

int sp[MAXN][LOG], lg[MAXN];
void build(int a[], int n){
    lg[1]=0; for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for(int i=0;i<n;i++) sp[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=0;i+(1<<j)-1<n;i++)
            sp[i][j]=min(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
}
int query(int l, int r){
    int k=lg[r-l+1];
    return min(sp[l][k], sp[r-(1<<k)+1][k]);
}

---

8.5 Other Key Structures (Quick Reference)

Structure	Use Case	Complexity
priority_queue	Dijkstra, greedy, K largest	$O(\log N)$ push/pop
set / multiset	Ordered elements, lower_bound	$O(\log N)$
unordered_map	Fast lookups (hash)	$O(1)$ avg
deque	0-1 BFS, sliding window	$O(1)$ push/pop
Trie	Prefix queries, XOR max	$O(L)$ per word
Monotone stack	Next greater element, histogram	$O(N)$
Monotone deque	Sliding window min/max	$O(N)$

---

9. Graph Algorithms

9.1 BFS / DFS

BFS — unweighted shortest path, level-order traversal

vector<int> dist(n, -1);
queue<int> q;
dist[s]=0; q.push(s);
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);
    }
}

DFS — cycle detection, topological sort, connected components

vector<bool> vis(n, false);
void dfs(int u){
    vis[u]=true;
    for(int v : adj[u]) if(!vis[v]) dfs(v);
}

• Mistakes: Stack overflow on deep DFS → use iterative; not marking visited before pushing in BFS (causes duplicates).

---

9.2 Dijkstra's Algorithm

• When: Single-source shortest path, non-negative weights
• Complexity: $O((V+E) \log V)$

vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[s]=0; pq.push({0, s});
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});
        }
}

• Mistakes: Using int when weights can overflow; not skipping stale entries; negative edges.

---

9.3 Bellman-Ford

• When: Negative weights, detect negative cycles
• Complexity: $O(VE)$

vector<long long> dist(n, LLONG_MAX);
dist[s]=0;
for(int i=0; i<n-1; i++)
    for(auto& [u,v,w] : edges)
        if(dist[u]!=LLONG_MAX && dist[u]+w<dist[v])
            dist[v]=dist[u]+w;
// Check for negative cycle:
for(auto& [u,v,w] : edges)
    if(dist[u]!=LLONG_MAX && dist[u]+w<dist[v])
        // negative cycle reachable

---

9.4 Floyd-Warshall

• When: All-pairs shortest path, $V \leq 500$
• Complexity: $O(V^3)$

// dist[i][j] initialized to edge weights, INF if no edge, 0 on diagonal
for(int k=0;k<n;k++)
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);

• Mistakes: Wrong loop order (k must be outermost); overflow when adding INF+INF.

---

9.5 Topological Sort (Kahn's Algorithm)

• When: DAG ordering, prerequisite scheduling, DP on DAG
• Complexity: $O(V+E)$

vector<int> indeg(n, 0), order;
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) q.push(i);
while(!q.empty()){
    int u=q.front(); q.pop(); order.push_back(u);
    for(int v:adj[u]) if(--indeg[v]==0) q.push(v);
}
// if order.size() < n → cycle exists

---

9.6 Strongly Connected Components (Tarjan's)

• When: Directed graph decomposition, 2-SAT
• Complexity: $O(V+E)$

int idx=0, scc_cnt=0, stk_top=0;
int disc[MAXN], low[MAXN], comp[MAXN], stk[MAXN];
bool on_stk[MAXN];
void tarjan(int u){
    disc[u]=low[u]=idx++;
    stk[stk_top++]=u; on_stk[u]=true;
    for(int v:adj[u]){
        if(disc[v]==-1){ tarjan(v); low[u]=min(low[u],low[v]); }
        else if(on_stk[v]) low[u]=min(low[u],disc[v]);
    }
    if(low[u]==disc[u]){
        while(true){
            int v=stk[--stk_top]; on_stk[v]=false;
            comp[v]=scc_cnt;
            if(v==u) break;
        }
        scc_cnt++;
    }
}

---

9.7 Bridges & Articulation Points

• When: Find critical edges/nodes in an undirected graph
• Complexity: $O(V+E)$

int timer=0, tin[MAXN], low[MAXN];
bool vis[MAXN];
void dfs(int u, int parent){
    vis[u]=true; tin[u]=low[u]=timer++;
    for(int v:adj[u]){
        if(v==parent) continue;
        if(vis[v]) low[u]=min(low[u],tin[v]);
        else{
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>tin[u]) // (u,v) is a bridge
            if(low[v]>=tin[u]) // u is an articulation point (+ root check)
        }
    }
}

---

9.8 Lowest Common Ancestor (LCA)

• When: Tree path queries, distance between tree nodes
• Complexity: $O(N \log N)$ preprocess, $O(\log N)$ query

int up[MAXN][LOG], depth[MAXN];
void dfs(int u, int p){
    up[u][0]=p;
    for(int i=1;i<LOG;i++) up[u][i]=up[up[u][i-1]][i-1];
    for(int v:adj[u]) if(v!=p){ 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 i=0;i<LOG;i++) if((diff>>i)&1) u=up[u][i];
    if(u==v) return u;
    for(int i=LOG-1;i>=0;i--)
        if(up[u][i]!=up[v][i]){ u=up[u][i]; v=up[v][i]; }
    return up[u][0];
}

• Tree distance: dist(u,v) = depth[u] + depth[v] - 2*depth[lca(u,v)]

---

9.9 Maximum Flow (Dinic's Algorithm)

• When: Max-flow / min-cut, bipartite matching, edge-disjoint paths
• Complexity: $O(V^2 E)$, but $O(E\sqrt{V})$ for unit-capacity

struct Edge{ int to, rev; long long cap; };
vector<Edge> graph[MAXN];
int level[MAXN], iter[MAXN];

void add_edge(int from, int to, long long cap){
    graph[from].push_back({to,(int)graph[to].size(),cap});
    graph[to].push_back({from,(int)graph[from].size()-1,0});
}
bool bfs(int s, int t, int n){
    fill(level,level+n,-1); level[s]=0;
    queue<int> q; q.push(s);
    while(!q.empty()){
        int v=q.front(); q.pop();
        for(auto& e:graph[v]) if(e.cap>0 && level[e.to]<0){
            level[e.to]=level[v]+1; q.push(e.to);
        }
    }
    return level[t]>=0;
}
long long dfs(int v, int t, long long f){
    if(v==t) return f;
    for(int& i=iter[v]; i<(int)graph[v].size(); i++){
        Edge& e=graph[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            long long d=dfs(e.to,t,min(f,e.cap));
            if(d>0){ e.cap-=d; graph[e.to][e.rev].cap+=d; return d; }
        }
    }
    return 0;
}
long long max_flow(int s, int t, int n){
    long long flow=0;
    while(bfs(s,t,n)){
        fill(iter,iter+n,0);
        long long d;
        while((d=dfs(s,t,LLONG_MAX))>0) flow+=d;
    }
    return flow;
}

---

9.10 Bipartite Matching (Kuhn's / Hopcroft-Karp)

• When: Maximum matching in bipartite graph
• Kuhn's: $O(VE)$ — simpler to code
• Hopcroft-Karp: $O(E\sqrt{V})$ — faster

Kuhn's (simple):

int match_to[MAXN]; // match_to[v] = u or -1
bool used[MAXN];
bool dfs(int u){
    for(int v : adj[u]) if(!used[v]){
        used[v]=true;
        if(match_to[v]==-1 || dfs(match_to[v])){
            match_to[v]=u; return true;
        }
    }
    return false;
}
// Call: for each u in left side, reset used[], if dfs(u) → matching++

---

10. Dynamic Programming Patterns

10.1 Classical DP Templates

↓ Pattern: Linear DP

• dp[i] = answer using first i elements
• Examples: LIS, coin change, house robber

↓ Pattern: 2D DP

• dp[i][j] = answer for subproblem (i, j)
• Examples: LCS, edit distance, matrix chain multiplication, knapsack

↓ Pattern: Interval DP

• dp[i][j] = answer for the range [i, j]
• Examples: Matrix chain, burst balloons, palindrome partitioning
• Enumerate over split point k in [i, j]

↓ Pattern: Bitmask DP

• dp[mask] or dp[mask][i] where mask is a bitmask of visited/chosen set
• Examples: TSP, assignment problem, Hamiltonian path
• $N \leq 20$ (sometimes 24 with optimizations)

↓ Pattern: Digit DP

• Count numbers in [L, R] with some digit property
• State: dp[pos][tight][leading_zero][...]
• Process digit by digit from MSB to LSB

↓ Pattern: DP on Trees

• DFS-based, compute dp for subtrees bottom-up
• dp[v] depends on dp[children]
• Often used with rerooting technique for "answer for each node as root"

↓ Pattern: DP on DAG

• Topological sort, then process in order
• Shortest/longest path on DAG

---

10.2 Longest Increasing Subsequence (LIS)

• Complexity: $O(N \log N)$
• Key idea: Maintain array tails[] where tails[i] = smallest tail element for IS of length i+1

vector<int> tails;
for(int x : a){
    auto it = lower_bound(tails.begin(), tails.end(), x);
    if(it == tails.end()) tails.push_back(x);
    else *it = x;
}
int lis_length = tails.size();

• For non-decreasing: use upper_bound instead of lower_bound.

---

10.3 Knapsack

0/1 Knapsack ($N$ items, capacity $W$): $O(NW)$

int dp[MAXW+1] = {};
for(int i=0; i<n; i++)
    for(int w=W; w>=weight[i]; w--)
        dp[w] = max(dp[w], dp[w-weight[i]] + value[i]);

Unbounded Knapsack:

for(int i=0; i<n; i++)
    for(int w=weight[i]; w<=W; w++)
        dp[w] = max(dp[w], dp[w-weight[i]] + value[i]);

• Mistakes: Loop direction matters (0/1 = reverse; unbounded = forward).

---

10.4 Edit Distance (Levenshtein)

• Complexity: $O(NM)$

// dp[i][j] = edit distance of a[0..i-1] and b[0..j-1]
for(int i=0;i<=n;i++) dp[i][0]=i;
for(int j=0;j<=m;j++) dp[0][j]=j;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        dp[i][j] = (a[i-1]==b[j-1]) ? dp[i-1][j-1]
            : 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});

---

10.5 Bitmask DP — TSP Example

• When: $N \leq 20$, visit all nodes exactly once, minimize cost
• Complexity: $O(2^N \cdot N^2)$

// dp[mask][i] = min cost to visit nodes in mask, ending at i
memset(dp, 0x3f, sizeof dp);
dp[1<<start][start] = 0;
for(int mask=1; mask<(1<<n); mask++)
    for(int u=0; u<n; u++) if(mask>>u&1)
        for(int v=0; v<n; v++) if(!(mask>>v&1))
            dp[mask|(1<<v)][v] = min(dp[mask|(1<<v)][v], dp[mask][u]+cost[u][v]);

---

10.6 Matrix Exponentiation for Linear Recurrences

• When: Compute $F(N)$ where $F$ follows a linear recurrence and $N \leq 10^{18}$
• Complexity: $O(K^3 \log N)$ where $K$ = recurrence order

typedef vector<vector<long long>> Matrix;
Matrix mult(const Matrix& A, const Matrix& B, long long mod){
    int n=A.size();
    Matrix C(n, vector<long long>(n, 0));
    for(int i=0;i<n;i++) for(int k=0;k<n;k++) if(A[i][k])
        for(int j=0;j<n;j++)
            C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;
    return C;
}
Matrix mat_pow(Matrix A, long long p, long long mod){
    int n=A.size();
    Matrix R(n, vector<long long>(n, 0));
    for(int i=0;i<n;i++) R[i][i]=1; // identity
    for(; p>0; p>>=1){ if(p&1) R=mult(R,A,mod); A=mult(A,A,mod); }
    return R;
}

Fibonacci: $\begin{pmatrix} F_{n+1} \ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \ 0 \end{pmatrix}$

---

10.7 SOS DP (Sum over Subsets)

• When: For each mask, compute sum over all submasks
• Complexity: $O(N \cdot 2^N)$

for(int i=0; i<n; i++)
    for(int mask=0; mask<(1<<n); mask++)
        if(mask >> i & 1)
            dp[mask] += dp[mask ^ (1<<i)];

---

11. Greedy Strategies

When Greedy Works

• Exchange argument: Swapping any two elements in the optimal solution doesn't improve it
• Greedy stays ahead: The greedy choice is at least as good as any other at every step
• Matroid structure: Independence system (e.g., MST)

Classic Greedy Problems

Problem	Strategy
Activity selection	Sort by end time, pick non-overlapping
Fractional knapsack	Sort by value/weight ratio
Huffman coding	Merge two smallest frequencies
Interval cover	Sort by start, extend greedily
Job scheduling with deadlines	Sort by deadline, use priority queue
Minimum platforms	Events sorted, track overlaps
Task assignment	Sort both arrays, pair greedily

Greedy + Sorting Pattern

Sort by some criteria
Iterate and greedily pick/assign:
    if current element is valid:
        take it, update state
    else:
        skip or adjust

• Mistakes: Assuming greedy works without proof; wrong sorting criterion; not handling ties.

---

12. Binary Search Patterns

Pattern 1: Search in Sorted Array

int lo=0, hi=n-1, ans=-1;
while(lo<=hi){
    int mid=(lo+hi)/2;
    if(a[mid]>=target){ ans=mid; hi=mid-1; } // first >= target
    else lo=mid+1;
}

Pattern 2: Binary Search on Answer

• When: "What is the minimum X such that check(X) is true?"
• Monotonicity: if check(x) → check(x+1) (or vice versa)

long long lo=MIN_ANS, hi=MAX_ANS, ans=hi;
while(lo<=hi){
    long long mid=(lo+hi)/2;
    if(check(mid)){ ans=mid; hi=mid-1; } // minimize
    else lo=mid+1;
}

Pattern 3: Binary Search on Real Numbers

double lo=0, hi=1e18;
for(int iter=0; iter<100; iter++){  // ~100 iterations for precision
    double mid=(lo+hi)/2;
    if(check(mid)) hi=mid;
    else lo=mid;
}

Common Binary Search Applications

Problem	Binary Search On
Min max distance	The distance value
Max min value	The value threshold
Can partition into K groups?	The max group sum
Kth smallest element	The value

• Mistakes: Integer overflow in (lo+hi)/2 → use lo+(hi-lo)/2; wrong boundary update (infinite loop); off-by-one in lo/hi initialization.

---

13. Math for Competitive Programming

Modular Arithmetic

(a + b) % m = ((a%m) + (b%m)) % m
(a * b) % m = ((a%m) * (b%m)) % m
(a - b) % m = ((a%m) - (b%m) + m) % m   // note: +m to avoid negative
(a / b) % m = (a * b^{-1}) % m           // b^{-1} = modular inverse

Modular exponentiation (fast power):

long long power(long long base, long long exp, long long mod){
    long long result=1; base%=mod;
    for(; exp>0; exp>>=1){
        if(exp&1) result=result*base%mod;
        base=base*base%mod;
    }
    return result;
}

Modular inverse (when mod is prime): $a^{-1} \equiv a^{p-2} \pmod{p}$ (Fermat's Little Theorem)

long long modinv(long long a, long long mod){ return power(a, mod-2, mod); }

Common Modular Pitfalls

• Multiplying two long long values → overflow! Use __int128 or modular multiply.
• Negative results from subtraction: always add mod before taking %.
• MOD = 1e9+7 → write as 1000000007LL.

---

14. Number Theory

14.1 GCD / LCM

long long gcd(long long a, long long b){ return b==0 ? a : gcd(b, a%b); }
long long lcm(long long a, long long b){ return a/gcd(a,b)*b; } // divide first to avoid overflow

14.2 Extended Euclidean Algorithm

• Finds $x, y$ such that $ax + by = \gcd(a, b)$

long long extgcd(long long a, long long b, long long &x, long long &y){
    if(b==0){ 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;
}

14.3 Sieve of Eratosthenes

• Complexity: $O(N \log \log N)$

vector<bool> is_prime(N+1, true);
is_prime[0]=is_prime[1]=false;
for(int i=2; i*i<=N; i++)
    if(is_prime[i])
        for(int j=i*i; j<=N; j+=i)
            is_prime[j]=false;

Linear sieve (with smallest prime factor):

int spf[MAXN]; // smallest prime factor
vector<int> primes;
void sieve(int n){
    fill(spf, spf+n+1, 0);
    for(int i=2; i<=n; i++){
        if(spf[i]==0){ spf[i]=i; primes.push_back(i); }
        for(int p : primes){
            if(p > spf[i] || (long long)i*p > n) break;
            spf[i*p]=p;
        }
    }
}

14.4 Prime Factorization

// Using smallest prime factor (after linear sieve):
map<int,int> factorize(int n){
    map<int,int> f;
    while(n>1){ f[spf[n]]++; n/=spf[n]; }
    return f;
}
// Without sieve (O(sqrt(n))):
map<int,int> factorize(int n){
    map<int,int> f;
    for(int d=2; (long long)d*d<=n; d++)
        while(n%d==0){ f[d]++; n/=d; }
    if(n>1) f[n]++;
    return f;
}

14.5 Euler's Totient Function

$\phi(n) = n \prod_{p | n} \left(1 - \frac{1}{p}\right)$

int phi(int n){
    int result=n;
    for(int p=2; (long long)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;
}

14.6 Chinese Remainder Theorem (CRT)

Given $x \equiv a_i \pmod{m_i}$ with pairwise coprime moduli:

// Returns (x, M) where x is the solution mod M = product of moduli
pair<long long,long long> crt(vector<long long>& a, vector<long long>& m){
    long long M=1, x=0;
    for(auto mi : m) M*=mi;
    for(int i=0; i<(int)a.size(); i++){
        long long Mi=M/m[i], yi, dummy;
        extgcd(Mi, m[i], yi, dummy);
        x=(x + a[i]%M * Mi%M * yi%M + M*3) % M;
    }
    return {x, M};
}

14.7 Key Number Theory Facts

• $n$ has at most $O(\sqrt[3]{n})$ distinct prime factors (loose), practically ≤ 15 for $n \leq 10^{18}$
• Number of divisors of $n$: $d(n)$ is at most ~1500 for $n \leq 10^9$
• $\sum_{i=1}^{N} \lfloor N/i \rfloor = O(N \log N)$
• Wilson's theorem: $(p-1)! \equiv -1 \pmod{p}$
• Fermat's little theorem: $a^{p-1} \equiv 1 \pmod{p}$ for prime $p$, $\gcd(a,p)=1$

---

15. Combinatorics

Binomial Coefficients

Precomputation with modular inverse:

long long fac[MAXN], inv_fac[MAXN];
void precompute(int n, long long mod){
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    inv_fac[n]=power(fac[n], mod-2, mod);
    for(int i=n-1;i>=0;i--) inv_fac[i]=inv_fac[i+1]*(i+1)%mod;
}
long long C(int n, int r, long long mod){
    if(r<0||r>n) return 0;
    return fac[n]%mod*inv_fac[r]%mod*inv_fac[n-r]%mod;
}

Key Combinatorial Identities

Identity	Formula
Pascal's	$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
Vandermonde	$\binom{m+n}{r} = \sum_k \binom{m}{k}\binom{n}{r-k}$
Hockey stick	$\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$
Stars & bars	Distribute $n$ identical items into $k$ bins: $\binom{n+k-1}{k-1}$
Derangements	$D_n = (n-1)(D_{n-1}+D_{n-2})$, $D_0=1, D_1=0$
Catalan	$C_n = \frac{1}{n+1}\binom{2n}{n}$

Inclusion-Exclusion Principle

$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots$

Useful for: counting multiples, derangements, surjections, chromatic polynomials.

Catalan Numbers

$C_n$: 1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

Counts: balanced parentheses, binary trees, triangulations, non-crossing partitions, Dyck paths.

Burnside's Lemma

Count distinct objects under group of symmetries $G$: $\text{distinct} = \frac{1}{|G|} \sum_{g \in G} |X^g|$ where $X^g$ = elements fixed by $g$.

---

16. Geometry Basics

16.1 Core Operations

Cross Product (2D): $\vec{a} \times \vec{b} = a_x b_y - a_y b_x$

• > 0: b is counter-clockwise from a
• = 0: collinear
• < 0: b is clockwise from a

typedef long long ll;
struct P { ll x, y; };
ll cross(P O, P A, P B){ return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x); }
ll dot(P A, P B, P O={(0,0)}){ return (A.x-O.x)*(B.x-O.x)+(A.y-O.y)*(B.y-O.y); }
double dist(P A, P B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); }

16.2 Convex Hull (Andrew's Monotone Chain)

• Complexity: $O(N \log N)$

vector<P> convex_hull(vector<P> pts){
    int n=pts.size(), k=0;
    if(n<3) return pts;
    sort(pts.begin(), pts.end(), [](P a, P b){ return a.x<b.x||(a.x==b.x&&a.y<b.y); });
    vector<P> H(2*n);
    for(int i=0;i<n;i++){
        while(k>=2 && cross(H[k-2],H[k-1],pts[i])<=0) k--;
        H[k++]=pts[i];
    }
    for(int i=n-2,t=k+1;i>=0;i--){
        while(k>=t && cross(H[k-2],H[k-1],pts[i])<=0) k--;
        H[k++]=pts[i];
    }
    H.resize(k-1);
    return H;
}

16.3 Line Intersection

Two lines $p_1 + t \cdot d_1$ and $p_2 + s \cdot d_2$:

// Returns true if segments (a,b) and (c,d) intersect
bool segments_intersect(P a, P b, P c, P d){
    ll d1=cross(c,d,a), d2=cross(c,d,b);
    ll d3=cross(a,b,c), d4=cross(a,b,d);
    if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0))) return true;
    // Check collinear cases with on-segment test if needed
    return false;
}

16.4 Point in Polygon

• Ray casting: Count intersections of horizontal ray with polygon edges
• Winding number: More robust for complex polygons

16.5 Area of Polygon (Shoelace Formula)

$$A = \frac{1}{2} \left| \sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i) \right|$$

double polygon_area(vector<P>& p){
    double area=0; int n=p.size();
    for(int i=0;i<n;i++){
        int j=(i+1)%n;
        area += (double)p[i].x*p[j].y - (double)p[j].x*p[i].y;
    }
    return abs(area)/2.0;
}

16.6 Geometry Tips

• Use integer arithmetic (cross products with long long) to avoid floating point errors.
• When double is needed, use EPS = 1e-9 for comparisons.
• Pick's theorem: $A = I + B/2 - 1$ (lattice polygon: $I$ = interior points, $B$ = boundary points).
• Angle comparison → use cross product (avoid atan2 when possible).

---

17. String Algorithms

17.1 KMP (Knuth-Morris-Pratt)

• When: Find all occurrences of pattern P in text T
• Complexity: $O(N + M)$

Failure function:

vector<int> kmp_table(const string& p){
    int m=p.size();
    vector<int> fail(m, 0);
    for(int i=1, j=0; i<m; i++){
        while(j>0 && p[i]!=p[j]) j=fail[j-1];
        if(p[i]==p[j]) j++;
        fail[i]=j;
    }
    return fail;
}

Search:

vector<int> kmp_search(const string& t, const string& p){
    auto fail=kmp_table(p);
    vector<int> occ;
    for(int i=0, j=0; i<(int)t.size(); i++){
        while(j>0 && t[i]!=p[j]) j=fail[j-1];
        if(t[i]==p[j]) j++;
        if(j==(int)p.size()){ occ.push_back(i-j+1); j=fail[j-1]; }
    }
    return occ;
}

• Key insight: fail[i] = length of longest proper prefix of p[0..i] that is also a suffix.
• Period of string: n - fail[n-1]

---

17.2 Z-Function

• z[i] = length of longest substring starting at i that matches a prefix of s
• Complexity: $O(N)$

vector<int> z_function(const string& s){
    int n=s.size();
    vector<int> z(n, 0);
    for(int i=1, l=0, r=0; 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;
}

• Pattern matching: Compute Z-function of P + "$" + T. Match at position i if z[i] >= |P|.

---

17.3 String Hashing (Rabin-Karp)

• When: Fast substring comparison, detecting duplicates
• Complexity: $O(N)$ preprocess, $O(1)$ per query

const long long MOD1=1e9+7, MOD2=1e9+9, BASE1=131, BASE2=137;
long long h1[MAXN], h2[MAXN], pw1[MAXN], pw2[MAXN];

void build_hash(const string& s){
    int n=s.size();
    pw1[0]=pw2[0]=1; h1[0]=h2[0]=0;
    for(int i=0;i<n;i++){
        h1[i+1]=(h1[i]*BASE1+s[i])%MOD1;
        h2[i+1]=(h2[i]*BASE2+s[i])%MOD2;
        pw1[i+1]=pw1[i]*BASE1%MOD1;
        pw2[i+1]=pw2[i]*BASE2%MOD2;
    }
}
pair<long long,long long> get_hash(int l, int r){ // [l, r] 0-indexed
    return {(h1[r+1]-h1[l]*pw1[r-l+1]%MOD1+MOD1*2)%MOD1,
            (h2[r+1]-h2[l]*pw2[r-l+1]%MOD2+MOD2*2)%MOD2};
}

• Use double hashing to minimize collision probability.
• Mistakes: Single hash collisions; wrong power computation; off-by-one in range.

---

17.4 Trie

• When: Prefix queries, autocomplete, XOR maximization
• Complexity: $O(L)$ per insertion/query, $L$ = string length

int trie[MAXNODES][26], cnt=0;
bool is_end[MAXNODES];
void insert(const string& s){
    int u=0;
    for(char c:s){
        int ch=c-'a';
        if(!trie[u][ch]) trie[u][ch]=++cnt;
        u=trie[u][ch];
    }
    is_end[u]=true;
}

---

17.5 Suffix Array (O(N log N) with Radix Sort)

• When: Substring searches, LCP queries, number of distinct substrings
• Complexity: $O(N \log N)$ build, queries vary

vector<int> suffix_array(const string& s){
    int n=s.size();
    vector<int> sa(n), rank_(n), tmp(n);
    iota(sa.begin(), sa.end(), 0);
    for(int i=0;i<n;i++) rank_[i]=s[i];
    for(int k=1;k<n;k<<=1){
        auto cmp=[&](int a, int b){
            if(rank_[a]!=rank_[b]) return rank_[a]<rank_[b];
            int ra=a+k<n?rank_[a+k]:-1, rb=b+k<n?rank_[b+k]:-1;
            return ra<rb;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]]=0;
        for(int i=1;i<n;i++) tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);
        rank_=tmp;
        if(rank_[sa[n-1]]==n-1) break;
    }
    return sa;
}

LCP Array (Kasai's, $O(N)$):

vector<int> lcp_array(const string& s, const vector<int>& sa){
    int n=s.size(), k=0;
    vector<int> rank_(n), lcp(n-1);
    for(int i=0;i<n;i++) rank_[sa[i]]=i;
    for(int i=0;i<n;i++,k?k--:0){
        if(rank_[i]==n-1){k=0;continue;}
        int j=sa[rank_[i]+1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) k++;
        lcp[rank_[i]]=k;
    }
    return lcp;
}

• Distinct substrings = $\frac{n(n+1)}{2} - \sum \text{LCP}[i]$

---

18. Bit Manipulation Tricks

Essential Operations

Operation	Code	Description
Check bit i	(n >> i) & 1	Is bit i set?
Set bit i	n | (1 << i)	Turn on bit i
Clear bit i	n & ~(1 << i)	Turn off bit i
Toggle bit i	n ^ (1 << i)	Flip bit i
Lowest set bit	n & (-n)	Isolate lowest 1
Clear lowest set bit	n & (n-1)	Turn off lowest 1
Count set bits	__builtin_popcount(n)	Number of 1s
Leading zeros	__builtin_clz(n)	(32-bit)
Trailing zeros	__builtin_ctz(n)	Position of lowest 1
All bits set up to i	(1 << (i+1)) - 1	Mask of bits [0..i]
Is power of 2	n > 0 && (n & (n-1)) == 0
Next higher with same popcount	(see below)

Iterating Over Submasks

// All submasks of mask (including 0)
for(int sub = mask; sub > 0; sub = (sub-1) & mask)
    // process sub
// Don't forget sub = 0 case if needed

Total iterations over all masks: $O(3^N)$

Iterating Over All Masks with k Bits Set

int mask = (1<<k)-1;
while(mask < (1<<n)){
    // process mask
    int c = mask & (-mask), r = mask + c;
    mask = (((r^mask)>>2)/c) | r;
}

XOR Properties

• $a \oplus a = 0$, $a \oplus 0 = a$
• XOR is associative and commutative
• Finding the element that appears once: XOR all elements
• Maximum XOR pair: use a trie on bit representation

Caution with Bit Shifts

• Use 1LL << i for i >= 31 to avoid undefined behavior
• __builtin_popcountll() for long long

---

19. Common Implementation Patterns

Two Pointers

// Pattern: Find subarray with property (e.g., sum >= target)
int l=0, best=INT_MAX;
long long sum=0;
for(int r=0; r<n; r++){
    sum += a[r];
    while(sum >= target){
        best = min(best, r-l+1);
        sum -= a[l++];
    }
}

Sliding Window

// Fixed window of size k
for(int i=0; i<n; i++){
    // Add a[i] to window
    if(i >= k){
        // Remove a[i-k] from window
    }
    if(i >= k-1){
        // Window [i-k+1 .. i] is complete, process it
    }
}

Coordinate Compression

vector<int> vals(a, a+n);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for(int i=0; i<n; i++)
    a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();

Prefix Sums (1D and 2D)

1D:

prefix[0]=0;
for(int i=0;i<n;i++) prefix[i+1]=prefix[i]+a[i];
// sum(l,r) = prefix[r+1]-prefix[l]  (0-indexed)

2D:

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
// sum(r1,c1,r2,c2) = pre[r2][c2]-pre[r1-1][c2]-pre[r2][c1-1]+pre[r1-1][c1-1]

Meet in the Middle

• Split set into two halves, enumerate both ($2^{N/2}$ each), combine
• Often used with sorting + binary search on one half

Square Root Decomposition

• Split array into $\sqrt{N}$ blocks of size $\sqrt{N}$
• Query: $O(\sqrt{N})$, Update: $O(\sqrt{N})$ or $O(1)$
• Simpler alternative to segment tree for some problems

---

20. Common ICPC Tricks

1. Fast I/O is mandatory — always include ios::sync_with_stdio(false).
2. Use long long by default when constraints are unclear or products can overflow.
3. Precompute factorials and inverses up to max $N$ at start.
4. const int INF = 0x3f3f3f3f — works with memset(arr, 0x3f, sizeof arr) for int.
5. For long long INF: use 0x3f3f3f3f3f3f3f3fLL with memset.
6. __gcd(a,b) is built-in in C++ (also std::gcd in C++17).
7. __builtin_popcount — counts set bits in constant time.
8. Avoid endl — use '\n'.
9. Multitest problems: Double-check all globals and data structures are reset.
10. Adjacency list > matrix for sparse graphs.
11. pair<int,int> sorts lexicographically — useful for event-based problems.
12. Lambda comparators for custom sorting in priority queues.
13. nth_element for $O(N)$ kth smallest without full sort.
14. Use assert() for debugging invariants, remove before submitting.
15. If TLE: Check for accidental $O(N^2)$ in string concatenation or vector copying.
16. Declare large arrays globally (stack overflow prevention).
17. For graph problems: always check if the graph is 0-indexed or 1-indexed.
18. Random shuffle for randomized algorithms: use mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

---

21. Debugging During Contests

Systematic Debugging (max 5 minutes per attempt)

1. Re-read the problem — 50% of WA comes from misunderstanding
2. Check sample cases by hand — trace your algorithm step by step
3. Print intermediate values — use stderr: cerr << "x=" << x << endl;
4. Generate small random tests:

# gen.py — random test generator
import random
n = random.randint(1, 10)
print(n)
print(*[random.randint(1, 100) for _ in range(n)])

# stress.sh — compare brute force vs optimized
while true; do
    python3 gen.py > in.txt
    ./brute < in.txt > out1.txt
    ./sol < in.txt > out2.txt
    if ! diff -q out1.txt out2.txt > /dev/null; then
        echo "DIFF FOUND"; cat in.txt; break
    fi
done

Common Bug Checklist

Bug	How to Spot
Array out of bounds	MAXN too small, 0/1 indexing confusion
Integer overflow	Products of values > $10^4$, sum of values > $2 \times 10^9$
Uninitialized variables	dp array not zeroed, dist not set to INF
Wrong data type	int instead of long long
Off-by-one	< vs <=, n-1 vs n
Not resetting between test cases	Global arrays, visited flags, DSU
Wrong sort comparator	Not a strict weak ordering → UB
Infinite loop	Binary search boundaries, while conditions
Copy-paste errors	Variable names from duplicated blocks

---

22. Edge Case Checklist

Always test these before submitting:

• N = 0 or N = 1 (minimum input)
• All elements the same
• Already sorted / reverse sorted
• Maximum values (stress-test overflow)
• Negative numbers (if allowed)
• Empty graph (no edges)
• Disconnected graph
• Tree is a line (worst case depth)
• Self-loops and parallel edges (if not explicitly excluded)
• Large prime inputs (for modular problems)
• Answer is 0 or answer is 1
• Exact boundary cases: $N = \text{max}$, weights = 0
• Single test case vs. multi-test — did you read T?
• Floating point: values very close together, degenerate geometry

---

Quick Reference Card

C++ STL Cheat Sheet

sort(a, a+n)                  // O(N log N)
lower_bound(a, a+n, x)        // first >= x
upper_bound(a, a+n, x)        // first > x
unique(a, a+n)                 // remove consecutive duplicates
next_permutation(a, a+n)       // next lexicographic permutation
__gcd(a, b)                    // GCD
accumulate(a, a+n, 0LL)       // sum (use 0LL for long long!)
*max_element(a, a+n)           // max value
*min_element(a, a+n)           // min value

Useful Constants

const int INF = 0x3f3f3f3f;            // ~1.06e9
const long long LINF = 0x3f3f3f3f3f3f3f3fLL; // ~4.56e18
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = 1e-9;

Common Includes Template

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t; cin >> t;
    while(t--){
        // solve
    }
}

---

End of ICPC Contest Reference Sheet

---

Page Count Estimate: ~28 pages when printed in compact format (10pt font, narrow margins)

Version: March 2026 | Compile: g++ -O2 -std=c++17 -Wall -Wextra