[1] Imports & Fast I/O

●​ When: Always include for contests.​

●​ read_int(), read_ints() save typing + are faster for big input.

import sys, math, bisect, heapq, itertools, collections, functools, random

from collections import deque, Counter, defaultdict

from math import gcd, sqrt, ceil, floor, factorial, log2

from bisect import bisect_left, bisect_right

# Fast Input / Output

input = sys.stdin.readline

def read_int(): return int(input())

def read_ints(): return list(map(int, input().split()))

def read_str(): return input().strip()

def read_strs(): return input().split()

# Printing in contests

def print_flush(*args):

sys.stdout.write(" ".join(map(str,args)) + "\n")

sys.stdout.flush()

[2] Constants & Helpers

●​ When: For problems with large values (define INF, MOD).

●​ lower_bound, upper_bound: Useful for binary search on sorted arrays.

INF = float('inf')

MOD = 10**9 + 7

MOD2 = 998244353 # second useful modulus

def lcm(a, b): return a * b // gcd(a, b)

1
# Binary search helpers

def lower_bound(arr, x): return bisect_left(arr, x)

def upper_bound(arr, x): return bisect_right(arr, x)

[3] Number Theory (basic + advanced)

●​ modpow / modinv → Modular arithmetic problems (nCr mod, modular equations).

●​ extgcd / crt → Diophantine equations, solving multiple modular congruences.
●​ Miller–Rabin / sieve → Prime checking, factorization.
●​ Typical use case: "Given N up to 10^12, check if prime." → Use is_prime.

# Modular exponentiation

def modpow(a, b, mod=MOD):

res = 1

a %= mod

while b:

if b & 1: res = (res * a) % mod

a = (a*a) % mod

b >>= 1

return res

# Modular inverse (using Fermat's Little Theorem)

def modinv(a, mod=MOD):

return modpow(a, mod-2, mod)

# Extended Euclidean Algorithm

def extgcd(a, b):

if b == 0: return (1, 0, a)

x1, y1, g = extgcd(b, a % b)

2
 return (y1, x1 - (a // b) * y1, g)

# Chinese Remainder Theorem (pairwise coprime mods)

def crt(a1, m1, a2, m2):

x, y, g = extgcd(m1, m2)

if (a2 - a1) % g != 0: return None

lcm_val = m1 // g * m2

x = (a1 + (a2 - a1)//g * x % (m2//g) * m1) % lcm_val

return (x, lcm_val)

# Miller-Rabin primality test (deterministic for 64-bit)

def is_prime(n):

if n < 2: return False

for p in [2,3,5,7,11,13,17,19,23,29]:

if n % p == 0: return n == p

d, s = n-1, 0

while d % 2 == 0:

d//=2; s+=1

for a in [2,325,9375,28178,450775,9780504,1795265022]:

if a % n == 0: continue

x = pow(a,d,n)

if x == 1 or x == n-1: continue

for _ in range(s-1):

x = (x*x) % n

if x == n-1: break

3
 else:

return False

return True

# Sieve of Eratosthenes (linear time)

def sieve(n):

spf = list(range(n+1))

primes = []

for i in range(2,n+1):

if spf[i]==i: primes.append(i)

for p in primes:

if p*i>n or p>spf[i]: break

spf[p*i]=p

return primes, spf

[4] Combinatorics

●​ Precompute factorials, nCr, nPr → Problems with counting arrangements, binomial coefficients
mod M.​

●​ Typical use case: "How many ways to choose K items mod 1e9+7."

# Precompute factorials and inverse factorials (for nCr mod)

MAXN = 2*10**5 + 5

fact = [1]*MAXN

invfact = [1]*MAXN

def precompute_factorials(mod=MOD):

for i in range(1,MAXN):

4
 fact[i] = (fact[i-1]*i) % mod

invfact[MAXN-1] = pow(fact[MAXN-1], mod-2, mod)

for i in range(MAXN-2,-1,-1):

invfact[i] = (invfact[i+1]*(i+1)) % mod

def nCr(n, r, mod=MOD):

if r < 0 or r > n: return 0

return fact[n]*invfact[r] % mod * invfact[n-r] % mod

def nPr(n, r, mod=MOD):

if r < 0 or r > n: return 0

return fact[n]*invfact[n-r] % mod

[5] Graph Algorithms

●​ BFS/DFS → Unweighted shortest path, connected components, cycle detection.

●​ Dijkstra → Weighted graphs (non-negative weights).
●​ Bellman-Ford → Graphs with negative edges (but not negative cycles).
●​ Floyd–Warshall → All-pairs shortest path (small N ≤ 400).
●​ Prim/Kruskal → Minimum Spanning Tree.

# BFS

def bfs(graph, start):

n = len(graph)

dist = [-1]*n

dist[start] = 0

q = deque([start])

while q:

u = q.popleft()

for v in graph[u]:

if dist[v]==-1:

5
 dist[v] = dist[u]+1

q.append(v)

return dist

# DFS

def dfs(graph, u, visited=None):

if visited is None: visited=set()

visited.add(u)

for v in graph[u]:

if v not in visited:

dfs(graph,v,visited)

return visited

# Dijkstra

def dijkstra(n, adj, start):

dist = [INF]*n

dist[start]=0

pq=[(0,start)]

while pq:

d,u=heapq.heappop(pq)

if d!=dist[u]: continue

for v,w in adj[u]:

if dist[v]>d+w:

dist[v]=d+w

heapq.heappush(pq,(dist[v],v))

return dist

6
# Bellman-Ford

def bellman_ford(n, edges, src):

dist=[INF]*n

dist[src]=0

for _ in range(n-1):

changed=False

for u,v,w in edges:

if dist[u]+w<dist[v]:

dist[v]=dist[u]+w

changed=True

if not changed: break

return dist

# Floyd-Warshall

def floyd_warshall(n, mat):

dist=[[INF]*n for _ in range(n)]

for u in range(n): dist[u][u]=0

for u in range(n):

for v,w in mat[u]:

dist[u][v]=min(dist[u][v],w)

for k in range(n):

for i in range(n):

for j in range(n):

if dist[i][k]+dist[k][j]<dist[i][j]:

dist[i][j]=dist[i][k]+dist[k][j]

7
 return dist

# Prim’s MST

def prim(n, adj):

inMST=[False]*n

pq=[(0,0)]

total=0

while pq:

w,u=heapq.heappop(pq)

if inMST[u]: continue

inMST[u]=True

total+=w

for v,c in adj[u]:

if not inMST[v]:

heapq.heappush(pq,(c,v))

return total

# Kruskal’s MST

def kruskal(n, edges):

dsu=DSU(n)

total=0

edges.sort(key=lambda x:x[2])

for u,v,w in edges:

if dsu.union(u,v):

total+=w

return total

8
[6] Disjoint Set Union (DSU)

●​ When: Union-Find is perfect for connectivity problems.​

●​ Typical use case: "How many connected components after adding/removing edges."

class DSU:

def __init__(self, n):

self.parent=list(range(n))

self.rank=[0]*n

def find(self,x):

if self.parent[x]!=x:

self.parent[x]=self.find(self.parent[x])

return self.parent[x]

def union(self,x,y):

xr,yr=self.find(x),self.find(y)

if xr==yr: return False

if self.rank[xr]<self.rank[yr]:

self.parent[xr]=yr

elif self.rank[xr]>self.rank[yr]:

self.parent[yr]=xr

else:

self.parent[yr]=xr

self.rank[xr]+=1

return True

9
[7] Trees — LCA (Binary Lifting) & Centroid Decomposition

●​ LCA (binary lifting) → Path queries, distance between two nodes in tree.
●​ Centroid Decomposition → Tree problems requiring divide-and-conquer on nodes (rare, but
ICPC-level).

# [7.1] Lowest Common Ancestor (binary lifting)

class LCA:

def __init__(self, n, root=0, adj=None):

self.n = n

self.LOG = max(1, (n).bit_length())

self.up = [[-1]*n for _ in range(self.LOG)] # up[k][v] = 2^k-th

ancestor of v

self.depth = [0]*n

if adj is not None:

self.build(root, adj)

def build(self, root, adj):

sys.setrecursionlimit(10**6)

def dfs(u, p):

self.up[0][u] = p

for v in adj[u]:

if v == p: continue

self.depth[v] = self.depth[u] + 1

dfs(v, u)

dfs(root, -1)

for k in range(1, self.LOG):

for v in range(self.n):

10
 if self.up[k-1][v] < 0:

self.up[k][v] = -1

else:

self.up[k][v] = self.up[k-1][self.up[k-1][v]]

def query(self, a, b):

if self.depth[a] < self.depth[b]: a, b = b, a

diff = self.depth[a] - self.depth[b]

k = 0

while diff:

if diff & 1:

a = self.up[k][a]

diff >>= 1; k += 1

if a == b: return a

for k in range(self.LOG-1, -1, -1):

if self.up[k][a] != self.up[k][b]:

a = self.up[k][a]

b = self.up[k][b]

return self.up[0][a]

# [7.2] Centroid Decomposition (build parent array)

def centroid_decomposition(adj):

n = len(adj)

removed = [False]*n

parent = [-1]*n

11
size = [0]*n

def dfs_size(u, p):

size[u] = 1

for v in adj[u]:

if v == p or removed[v]: continue

dfs_size(v, u)

size[u] += size[v]

def dfs_centroid(u, p, tot):

for v in adj[u]:

if v != p and not removed[v] and size[v] > tot//2:

return dfs_centroid(v, u, tot)

return u

def build(u, p):

dfs_size(u, -1)

c = dfs_centroid(u, -1, size[u])

parent[c] = p

removed[c] = True

for v in list(adj[c]):

if not removed[v]:

build(v, c)

return c

root = build(0, -1)

return parent, root

12
[8] Flows & Matching — Dinic and Hopcroft–Karp

●​ Dinic’s Max Flow → Maximum flow in networks (assignments, capacities).

●​ Hopcroft–Karp → Maximum bipartite matching (jobs ↔ workers).
●​ Typical use case: "Maximum number of students who can be assigned to projects."

# [8.1] Dinic's Max Flow (directed)

class Dinic:

class Edge:

__slots__ = ('v','cap','rev')

def __init__(self, v, cap, rev):

self.v = v; self.cap = cap; self.rev = rev

def __init__(self, n):

self.n = n

self.g = [[] for _ in range(n)]

def add_edge(self, u, v, cap):

a = Dinic.Edge(v, cap, len(self.g[v]))

b = Dinic.Edge(u, 0, len(self.g[u]))

self.g[u].append(a)

self.g[v].append(b)

def bfs(self, s, t, level):

for i in range(len(level)): level[i] = -1

q = deque([s]); level[s] = 0

while q:

13
 u = q.popleft()

for e in self.g[u]:

if e.cap > 0 and level[e.v] < 0:

level[e.v] = level[u] + 1

q.append(e.v)

return level[t] >= 0

def dfs(self, u, t, f, level, it):

if u == t: return f

for i in range(it[u], len(self.g[u])):

e = self.g[u][i]

if e.cap > 0 and level[u] < level[e.v]:

ret = self.dfs(e.v, t, min(f, e.cap), level, it)

if ret > 0:

e.cap -= ret

self.g[e.v][e.rev].cap += ret

return ret

it[u] += 1

return 0

def max_flow(self, s, t):

flow = 0

level = [-1]*self.n

while self.bfs(s, t, level):

it = [0]*self.n

while True:

14
 pushed = self.dfs(s, t, 10**18, level, it)

if pushed == 0: break

flow += pushed

return flow

# [8.2] Hopcroft–Karp for bipartite matching (left: 0..n-1, right: 0..m-1)

def hopcroft_karp(n, m, adj): # adj: list for left side, adjacency to right
indices

# returns pair (matching_size, pairU, pairV)

pairU = [-1]*n

pairV = [-1]*m

dist = [0]*n

INF_D = 10**9

def bfs():

q = deque()

for u in range(n):

if pairU[u] == -1:

dist[u] = 0

q.append(u)

else:

dist[u] = INF_D

found = False

while q:

u = q.popleft()

15
 for v in adj[u]:

pv = pairV[v]

if pv != -1 and dist[pv] == INF_D:

dist[pv] = dist[u] + 1

q.append(pv)

if pv == -1:

found = True

return found

def dfs(u):

for v in adj[u]:

pv = pairV[v]

if pv == -1 or (dist[pv] == dist[u] + 1 and dfs(pv)):

pairU[u] = v

pairV[v] = u

return True

dist[u] = INF_D

return False

matching = 0

while bfs():

for u in range(n):

if pairU[u] == -1 and dfs(u):

matching += 1

return matching, pairU, pairV

16
[9] Dynamic Programming Patterns

●​ LIS (n log n) → Longest increasing subsequence problems.

●​ Knapsack → Subset sums, maximize value under weight.
●​ Bitmask DP → Traveling salesman, subsets of small N (N ≤ 20).
●​ Digit DP → Count numbers ≤ N with digit constraints.

# [9.1] Longest Increasing Subsequence (n log n)

def LIS_length(arr):

from bisect import bisect_left

d = []

for x in arr:

i = bisect_left(d, x)

if i == len(d):

d.append(x)

else:

d[i] = x

return len(d)

# [9.2] 0-1 Knapsack (1D optimized)

def knapsack_1d(values, weights, W):

dp = [0]*(W+1)

for val, wt in zip(values, weights):

for j in range(W, wt-1, -1):

dp[j] = max(dp[j], dp[j-wt] + val)

return dp[W]

# [9.3] Unbounded Knapsack

def unbounded_knapsack(values, weights, W):

dp = [0]*(W+1)

17
 for wt, val in zip(weights, values):

for j in range(wt, W+1):

dp[j] = max(dp[j], dp[j-wt] + val)

return dp[W]

# [9.4] Bitmask DP (TSP style example)

def tsp_bitmask(dist):

n = len(dist)

FULL = 1<<n

dp = [[INF]*n for _ in range(FULL)]

dp[1][0] = 0

for mask in range(FULL):

for u in range(n):

if not (mask & (1<<u)): continue

if dp[mask][u] >= INF: continue

for v in range(n):

if mask & (1<<v): continue

dp[mask | (1<<v)][v] = min(dp[mask | (1<<v)][v], dp[mask][u] +

dist[u][v])

ans = min(dp[FULL-1][i] + dist[i][0] for i in range(n))

return ans

# [9.5] Digit DP template (count numbers <= N with property)

def digit_dp_count(N_str):

L = len(N_str)

from functools import lru_cache

18
 @lru_cache(None)

def dfs(pos, tight, started, some_state):

# some_state: placeholder for problem-specific state

if pos == L:

return 1 # or 0 depending on condition

limit = int(N_str[pos]) if tight else 9

res = 0

for d in range(0, limit+1):

ntight = tight and (d == limit)

nstarted = started or (d != 0)

# skip or update some_state depending on digit

res += dfs(pos+1, ntight, nstarted, some_state)

return res

return dfs(0, True, False, 0)

[10] Data Structures

●​ Fenwick Tree → Prefix sums with updates (fast and simple).​

●​ Segment Tree → Range queries + updates (RMQ, sum).

●​ Lazy Segment Tree → Range updates and queries.
●​ Typical use case: "Add +5 to all in range [l,r] and query sum."

# [10.1] Fenwick Tree (Binary Indexed Tree)

class FenwickTree:
def __init__(self, n):
self.n = n
self.bit = [0]*(n+1)
def update(self, i, delta):
i += 1
while i <= self.n:
self.bit[i] += delta
i += i & -i

19
 def query(self, i):
i += 1
s = 0
while i > 0:
s += self.bit[i]
i -= i & -i
return s
def range_query(self, l, r):
return self.query(r) - self.query(l-1)

# [10.2] Segment Tree (point update, range query)

class SegmentTree:
def __init__(self, arr, func=min, default=INF):
self.n = len(arr)
self.func = func
self.default = default
self.size = 1
while self.size < self.n: self.size <<= 1
self.data = [default]*(2*self.size)
for i in range(self.n):
self.data[self.size+i] = arr[i]
for i in range(self.size-1, 0, -1):
self.data[i] = func(self.data[2*i], self.data[2*i+1])
def update(self, idx, value):
i = self.size+idx
self.data[i] = value
while i > 1:
i >>= 1
self.data[i] = self.func(self.data[2*i], self.data[2*i+1])
def query(self, l, r): # [l,r)
res = self.default
l += self.size; r += self.size
while l < r:
if l & 1: res = self.func(res, self.data[l]); l+=1
if r & 1: r-=1; res = self.func(res, self.data[r])
l >>= 1; r >>= 1
return res

# [10.3] Lazy Segment Tree (range update, range query sum)

class LazySegTree:
def __init__(self, n):
self.n = 1

20
 while self.n < n: self.n <<= 1
self.data = [0]*(2*self.n)
self.lazy = [0]*(2*self.n)
def push(self, node, l, r):
if self.lazy[node]:
self.data[node] += (r-l+1)*self.lazy[node]
if l != r:
self.lazy[node*2] += self.lazy[node]
self.lazy[node*2+1] += self.lazy[node]
self.lazy[node]=0
def update(self, ql, qr, val, node=1, l=0, r=None):
if r is None: r=self.n-1
self.push(node,l,r)
if ql>r or qr<l: return
if ql<=l and r<=qr:
self.lazy[node]+=val
self.push(node,l,r)
return
mid=(l+r)//2
self.update(ql,qr,val,node*2,l,mid)
self.update(ql,qr,val,node*2+1,mid+1,r)
self.data[node]=self.data[node*2]+self.data[node*2+1]
def query(self, ql, qr, node=1, l=0, r=None):
if r is None: r=self.n-1
self.push(node,l,r)
if ql>r or qr<l: return 0
if ql<=l and r<=qr: return self.data[node]
mid=(l+r)//2
return
self.query(ql,qr,node*2,l,mid)+self.query(ql,qr,node*2+1,mid+1,r)

[11] String Algorithms

●​ KMP/Z → Pattern matching in strings.

●​ Trie → Word dictionary problems.
●​ Rolling Hash → Substring comparisons (fast).
●​ Typical use case: "Check if a string appears in another in O(N)."

# [11.1] KMP Prefix Function

def kmp_prefix(s):
n = len(s)
lps = [0]*n
j = 0

21
 for i in range(1, n):
while j > 0 and s[i] != s[j]:
j = lps[j-1]
if s[i] == s[j]:
j += 1
lps[i] = j
return lps

# [11.2] Z-algorithm
def z_function(s):
n = len(s)
z = [0]*n
l = r = 0
for i in range(1,n):
if i<=r: z[i]=min(r-i+1,z[i-l])
while i+z[i]<n and s[z[i]]==s[i+z[i]]:
z[i]+=1
if i+z[i]-1>r: l,r=i,i+z[i]-1
return z

# [11.3] Trie
class TrieNode:
def __init__(self):
self.children={}
self.end=False
class Trie:
def __init__(self): self.root=TrieNode()
def insert(self,word):
node=self.root
for ch in word:
if ch not in node.children:
node.children[ch]=TrieNode()
node=node.children[ch]
node.end=True
def search(self,word):
node=self.root
for ch in word:
if ch not in node.children: return False
node=node.children[ch]
return node.end

# [11.4] Rolling Hash (Rabin–Karp)

22
class RollingHash:
def __init__(self, s, base=911382323, mod=10**9+7):
self.n=len(s)
self.base=base
self.mod=mod
self.p=[1]*(self.n+1)
self.h=[0]*(self.n+1)
for i in range(self.n):
self.p[i+1]=self.p[i]*base%mod
self.h[i+1]=(self.h[i]*base+ord(s[i]))%mod
def get_hash(self,l,r):
return (self.h[r]-self.h[l]*self.p[r-l])%self.mod

[12] Geometry

●​ Convex Hull → Smallest convex polygon covering points.

●​ Polygon area (shoelace) → Compute polygon area.
●​ Point-in-polygon → Check if query point lies inside polygon.
●​ Typical use case: Computational geometry ICPC tasks.

# [12.1] Point class

class Point:
__slots__=("x","y")
def __init__(self,x,y): self.x=x; self.y=y
def __sub__(self,other): return Point(self.x-other.x,self.y-other.y)
def cross(self,other): return self.x*other.y-self.y*other.x
def dot(self,other): return self.x*other.x+self.y*other.y

# [12.2] Convex Hull (Monotone chain)

def convex_hull(points):
points=sorted(set(points))
if len(points)<=1: return points
def cross(o,a,b): return (a[0]-o[0])*(b[1]-o[1])-(a[1]-o[1])*(b[0]-o[0])
lower=[]
for p in points:
while len(lower)>=2 and cross(lower[-2],lower[-1],p)<=0: lower.pop()
lower.append(p)
upper=[]
for p in reversed(points):
while len(upper)>=2 and cross(upper[-2],upper[-1],p)<=0: upper.pop()
upper.append(p)
return lower[:-1]+upper[:-1]

23
# [12.3] Polygon area (Shoelace)
def polygon_area(poly):
area=0
n=len(poly)
for i in range(n):
x1,y1=poly[i]
x2,y2=poly[(i+1)%n]
area+=x1*y2-x2*y1
return abs(area)/2

# [12.4] Point in polygon (ray casting)

def point_in_polygon(poly, p):
x,y=p
inside=False
n=len(poly)
for i in range(n):
x1,y1=poly[i]
x2,y2=poly[(i+1)%n]
if ((y1>y)!=(y2>y)) and (x < (x2-x1)*(y-y1)/(y2-y1)+x1):
inside=not inside
return inside

[13] Misc Utilities

●​ next_permutation → Generate permutations lexicographically.​

all_subsets → Iterate subsets (good for N ≤ 20).
●​ binary_search_first_true → Find smallest index satisfying condition.

# [13.1] next_permutation
def next_permutation(arr):
i=len(arr)-2
while i>=0 and arr[i]>=arr[i+1]: i-=1
if i==-1: return False
j=len(arr)-1
while arr[j]<=arr[i]: j-=1
arr[i],arr[j]=arr[j],arr[i]
arr[i+1:]=reversed(arr[i+1:])
return True

# [13.2] Iterate subsets

def all_subsets(n):
for mask in range(1<<n):
yield [i for i in range(n) if mask&(1<<i)]

24
# [13.3] Binary search utility
def binary_search_first_true(lo,hi,cond):
while lo<hi:
mid=(lo+hi)//2
if cond(mid): hi=mid
else: lo=mid+1
return lo

[14] Debugging & Test Harness

●​ Use debug() → Print variables without messing contest output.

●​ When: Local testing only (remove in final submission).

def debug(*args):
sys.stderr.write("DEBUG: " + " ".join(map(str,args)) + "\n")

# Example test harness

def run_tests(func, tests):
for i,(inp,expected) in enumerate(tests,1):
out=func(*inp)
print(f"Test {i}: {'PASS' if out==expected else 'FAIL'} | Got={out},
Expected={expected}")

[15] Main Function Skeleton

●​ Always wrap code in solve() + main() → Handles multiple test cases.

def solve():
# Write solution for one test case here
n = read_int()
arr = read_ints()
print(sum(arr)) # Example placeholder

def main():
t = 1
# t = int(input()) # uncomment if multiple test cases
for _ in range(t):
solve()

if __name__ == "__main__":
main()

25