The Ultimate Topic List

A comprehensive list of topics in Competitive Programming

Completed: ‌
out of 569

Copy Link to Basics

💡 Complete the basic topics in the given order to get started with Competitive Programming.

Intro to Programming

What is Programming?

Learn a Language

💡 Learning C++ is recommended.

Intro to C++ and Setting up the Environment

Data Types, Variables and Input Output

Operators

Conditional Statements

10.

Pointers and References

11.

Structures

Intro to Competitive Programming

12.

What is Competitive Programming?

Bitwise Thinking

13.

Bitwise Operations and Bitmasks

Complexity Analysis

14.

Big O Notation and Time and Space Complexity Analysis

15.

Fast Input Output

Recursion

16.

Recursion

Very Basic Math

17.

Divisors

18.

GCD and LCM

19.

Harmonic Number

Range Queries Without Updates

20.

Prefix Sum

21.

Prefix XOR

Standard Template Library (STL)

22.

Intro to STL, Containers and Iterators

23.

24.

25.

26.

27.

28.

29.

Set, Unordered Set and Multiset

30.

Map and Unordered Map

31.

Bitset

32.

List

Leveraging Monotonicity

33.

Binary Search

34.

Two Pointers

Basic Sorting Algorithms

35.

36.

37.

38.

39.

40.

41.

42.

C++ STL Sort and Custom Comparator

Divide and Conquer

43.

Divide and Conquer

Greedy and Constructive

44.

Basic Greedy Algorithms

45.

Basic Constructive Algorithms

2D Prefix Sum

46.

2D Prefix Sum

More Techniques

47.

Difference Array

48.

Sliding Window Technique

Bit Manipulation

49.

Bit Manipulation

50.

The XOR Trick

Basic Modular Arithmetic

51.

Binary Exponentiation and Basic Modular Arithmetic

52.

Fermat's Little Theorem and Modular Inverse

Basic Counting

53.

Permutations, Combinations and Basic Counting Problems

54.

Stars and Bars

55.

Pigeonhole Principle

Very Basic Graphs

56.

Introduction to Graphs | Definitions and Representations

Copy Link to Data Structures (DS)

Segment Tree

57.

Segment Tree (Point Update Range Query)

58.

Segment Tree with Lazy Propagation

59.

Persistent Segment Tree

60.

Persistent Segment Tree with Lazy Propagation

61.

2D Segment Tree

62.

Dynamic Segment Tree

63.

2D Dynamic Segment Tree

64.

Merge Sort Tree

65.

Iterative Segment Tree

66.

Segment Tree Merging

67.

Segment Tree Beats

68.

XOR Segment Tree

69.

Historic Information on Segment Trees

Binary Indexed Tree (BIT)

70.

BIT / Fenwick Tree

71.

Lower bound on BIT

72.

BIT with Range Update and Range Query

73.

2D BIT

74.

2D BIT with Range Update and Range Query

Sparse Table

75.

Sparse Table

76.

Sparse Table 2D

77.

Disjoint Sparse Table

Trie

78.

Trie on Strings and Bits

79.

Persistent Trie

Disjoint Set Union (DSU)

80.

DSU / Union Find

81.

DSU with Rollbacks

82.

Reachability Tree / DSU Tree / Kruskal Reconstruction Tree (KRT)

83.

Partially Persistent DSU

84.

Persistent DSU

85.

Augmented DSU / Weighted DSU

86.

DSU on Tree and Small to Large Merging

87.

[Trick] Maintaining Log N DSU / Range Parallel DSU

Square Root Decomposition

88.

Basic SQRT Decomposition

89.

Splitting Objects into Light and Heavy / Case Processing

90.

Batch Processing / SQRT Decomposition on Queries

91.

SQRT Decomposition Split and Build Technique

92.

SQRT Fragmented Tree / Block Tree / SQRT Decomposition on Trees

93.

Mo's Algorithm

94.

Rollback Mo and Mo's with DSU

95.

Mo's on Tree

96.

Sweepline Mo

97.

Mo's with Update / 3D Mo (Offline)

98.

Mo's with Update / 3D Mo (Online)

99.

4D Mo

Heavy Light Decomposition (HLD)

100.

Heavy Light Decomposition (HLD) ft Subtrees and Path Query

Centroid Decomposition

101.

Centroid Decomposition

102.

Persistent Centroid Decomposition

Long Path Decomposition

103.

Long Path Decomposition

BST

104.

Binary Search Tree (BST)

Balanced Binary Search Tree (BBST)

105.

106.

107.

108.

109.

Link Cut Tree (LCT)

110.

Link Cut Tree (LCT)

111.

Euler Tour Tree (ETT)

112.

Top Tree / AAA Tree

113.

Link Cut Cactus

Policy Based Data Structures

114.

Ordered Set

115.

GP Hash Table

More Tree Data Structures

116.

Wavelet Tree

117.

Cartesian Tree

118.

K-Dimensional Tree (KD Tree)

119.

SQRT Tree

120.

Permutation Tree

121.

PQ Tree

Dynamic Connectivity

122.

Dynamic Connectivity Problem (Offline)

123.

Dynamic Connectivity Problem (Online) / HDLT Algorithm

Miscellaneous

124.

Monotonic Stack: All Nearest Smaller Values and All Subarray Maximum/Minimum

125.

126.

127.

128.

129.

130.

131.

Persistent Meldable Heap / Leftist Heap

Techniques

132.

Venice Technique

133.

Offline Queries

134.

Static to Dynamic Trick / Log Decomposition

135.

Divide and Conquer on Queries

136.

CDQ Divide and Conquer

137.

Queue Undo Trick

138.

Priority Queue Undo Trick

Copy Link to Graph Theory

💡 Complete the "Very Basic Graphs" section under the "Basics" category first.

Graph Traversal

139.

Depth First Search (DFS)

140.

Breadth First Search (BFS)

141.

142.

143.

144.

145.

Lowest Common Ancestor (LCA)

146.

Binary Lifting and LCA

147.

LCA in O(1)

Graph Connectivity

148.

Strongly Connected Components (SCC)

149.

Incremental SCC

150.

Articulation Bridges and Bridge Tree

151.

Online Articulation Bridges

152.

Articulation Points and Block Cut Tree

153.

Three Edge Connectivity

154.

Four Edge Connectivity

155.

Dynamic K-Connectivity

156.

Ear Decomposition

Orientation

157.

Strong Orientation

158.

ST-numbering / Bipolar Orientation

Minimum Spanning Tree (MST)

159.

Minimum Spanning Tree (Prim's and Kruskal's)

160.

Steiner Tree Problem

161.

Boruvka's Algorithm

162.

Minimum Diameter Spanning Tree

163.

164.

165.

166.

167.

Kirchoffs Theorem ft Number of MSTs

Shortest Paths

168.

Dijkstra's Algorithm

169.

[Trick] Dijkstra on Segment Tree

170.

Floyd Warshall

171.

Bellman Ford

172.

Shortest Path Faster Algorithm (SPFA)

173.

174.

175.

176.

177.

Suurballe's Algorithm

178.

A* Algorithm

Cycles

179.

Cycle Detection

180.

[Problem] Minimum Weight Cycle For Each Vertex

181.

[Problem] Minimum Weight Cycle For Each Edge

182.

Minimum Mean Weight Cycle

183.

Number of 3 and 4 length Cycles

More Tree Stuff

184.

Virtual Tree / Auxiliary Tree

185.

Rerooting Technique

186.

Union of Two Paths on a Tree

187.

Intersection of Two Paths on a Tree

188.

[Problem] Number of Paths of Each Length in a Tree

189.

Dynamic Online Tree Diameter

190.

[Problem] Tree Orientation to Maximize Pairs of Reachable Nodes

Satisfiability

191.

2 SAT

192.

3 SAT

193.

System Of Difference Constraints

Eulerian Path

194.

Eulerian Path and Cycle

Hamiltonian Path

195.

Hamiltonian Path and Cycle

196.

Hamiltonian Path Heuristic Algorithm

Cliques and Independent Sets

197.

Maximum Clique

198.

Maximum Independent Set (MIS)

Graph Coloring

199.

Chromatic Number

200.

Welsh-Powell Algorithm

201.

Chromatic Polynomial ft Number of DAGs

202.

Edge Coloring of Simple Graph

203.

Edge Coloring of Bipartite Graph

Graph Counting

204.

Counting Labeled Graphs

205.

Prufer Code

206.

[Problem] Number of Arborescences with n Nodes

207.

Tuttes Theorem ft Arborescences in a Graph

208.

BEST Theorem

Dynamic Acyclic Graphs (DAG)

209.

DAG Reachability

210.

Incremental DAG Reachability

Dominators

211.

Dominator Tree

Special Graphs

212.

Cactus Graph

213.

Tournament Graph

214.

Chordal Graph

Flow and Min Cut

215.

Maximum Flow / Minimum Cut

216.

Min Cost Max Flow (MCMF)

217.

Min Cost Max Flow with Negative Cycles

218.

Maximum Closure Problem

219.

L-R Flow

220.

Gomory-Hu Tree

221.

Gomory-Hu Tree of a Planar Graph

222.

Stoer Wagner Algorithm

223.

Chinese Postman Problem

224.

Uniqueness of Min Cut

225.

Maximum Density Subgraph

226.

Min Cut in a Planar Graph

227.

Max Cut in a Planar Graph

Matching

228.

Bipartite Matching (HopCroft Karp Algorithm and Kuhn's Algorithm)

229.

Hungarian Algorithm / Bipartite Weighted Matching

230.

Blossom Algorithm Unweighted / General Matching / Randomized General Matching

231.

Blossom Algorithm Weighted / General Weighted Matching

232.

Stable Marriage Problem

233.

Konig's Theorem and Maximum Independent Set in Bipartite Graphs

234.

Halls Theorem

235.

Matching using Determinants

Partially Ordered Set (POSET)

236.

POSET ft Dilworth's and Mirsky's Theorem

Miscellaneous

237.

238.

239.

240.

241.

Copy Link to Number Theory

Primes and Divisors

242.

Sieve, Prime Factorization and Divisors

243.

Linear Sieve

244.

Segmented Sieve

245.

Sieve upto 1e9

246.

Miller-Rabin Primality Test

247.

Pollard Rho

248.

Prime Counting Function

249.

[Problem] Counting Numbers Having Exactly K Divisors

250.

[Problem] Smallest Number Having Exactly K Divisors

251.

Sum of The Number of Divisors in cbrt(n)

252.

Wilson's Theorem

253.

Implicit Prime Factorization

Multiplicative Functions

254.

Number of Divisors / Sum of Divisors / Sigma Function

255.

Euler's Totient Function / Phi Function

256.

Power Tower / Generalized Euler theorem

257.

Mobius Function and Mobius Inversion

258.

Dirichlet convolution

259.

Min_25 Sieve

260.

Powerful Number Sieve / PN Sieve

Euclidean Algorithm

261.

Euclidean Algorithm

262.

Extended Euclid

263.

Bezout's Identity

264.

Chicken McNugget Theorem

Modular Arithmetic

265.

Linear Congruence Equation

266.

Chinese Remainder Theorem (CRT)

267.

Primitive Root

268.

Multiplicative Order and Carmichael's Lambda Function

269.

Discrete Log / Baby Step Giant Step

270.

Discrete Root

271.

Discrete Root in O(P^(1/4))

272.

Discrete Square Root, Tonelli Shanks Algorithm, Cipolla's Algorithm

273.

Number of Distinct Kth Powers Modulo N

274.

Number of Solutions to X^2 = 1 mod M

Linear Diophantine Equations

275.

Linear Diophantine Equation with Two Variables

276.

Linear Diophantine Equation with N Variables

277.

Trivariable Linear Diophantine Equation with Nonnegative Solutions

278.

Multivariable Linear Diophantine Equation with Nonnegative Solutions

279.

Linear Diophantine With N Unknowns and Two Equations

Solutions to Equations

280.

Number of Solutions to a Basic Linear Algebraic Equation

281.

Number of Solutions to a Basic Linear Algebraic Equation using Meet in the Middle

282.

Number of Nonnegative Integer Solutions to ax + by ≤ c

283.

Number of Integer Solutions to 1/x + 1/y = 1/k

284.

Two / Three / Four Squares Theorem

285.

Pell's Equation

Floor Sum

286.

Sum of Floors

287.

Floor Sum and Mod Sum of Arithmetic Progression

288.

Generalized Floor Sum of Arithmetic Progression

Fibonacci Numbers

289.

Fibonacci Numbers

290.

[Problem] LCM of Fibonacci Numbers

291.

Pisano Period

292.

Phi Field

Miscellaneous

293.

Pythagorean Triplets

294.

Min of Mod of Arithmetic Progression

295.

Factorial Number System

296.

Stern-Brocot Tree and Rational Approximation

297.

[Problem] Number of a * x mod p in a Range

298.

[Problem] Smallest Nonnegative Integer x s.t. l ≤ a * x mod p ≤ r

Copy Link to Combinatorics

💡 Complete the "Basic Counting" section under the "Basics" category first.

Techniques

299.

Contribution Technique

Catalan

300.

Catalan Numbers

301.

Catalan Convolution

Inclusion Exclusion

302.

Principle of Inclusion and Exclusion (PIE)

303.

Derangements

304.

Inclusion Exclusion on Multiples

Factorials and Binomial Coefficients (nCr)

305.

Lucas Theorem

306.

nCr Modulo Any Mod

307.

Large Factorials and Binomial Coefficients

308.

Legendre's Formula

309.

Prefix Sum Queries of Binomial Coefficients

310.

Prefix Sum of Binomial Coefficients for a Fixed Large N

311.

Sum of nCr Over a Fixed Congruence Class

312.

[Problem] Sum of nCr(a[i], K) for each K from 1 to N

Stirling Numbers

313.

Stirling Numbers (Basic)

314.

Stirling Number of the First Kind for Fixed N

315.

Stirling Number of the First Kind for Fixed K

316.

Stirling Number of the Second Kind for Fixed N

317.

Stirling Number of the Second Kind for Fixed K

Partitions

318.

Partitions of an Integer, Partition Function and Pentagonal Number Theorem

319.

Partitions of a Set / Bell Number

Miscellaneous

320.

Burnside's Lemma / Polya Enumeration Theorem

321.

Bertrand's Ballot Theorem

322.

Young Tableaus and the Hook Length Formula

Copy Link to Math

Convolution

323.

Fast Fourier Transform (FFT)

324.

Number Theoretic Transform (NTT)

325.

2D FFT / NTT

326.

Online FFT / NTT

327.

Fast Walsh Hadamard Transform (FWHT) and its Variations

328.

GCD Convolution

329.

LCM Convolution

Polynomial

330.

331.

332.

333.

334.

335.

336.

Polynomial Composition

337.

Multipoint Evaluation

338.

Chirp Z Transform

339.

Polynomial Interpolation

340.

Polynomial Shift

341.

Shift of Sampling Points of Polynomial

342.

Polyomial Division and Remainder

343.

Polynomial Roots Under a Modulo

344.

Resultant of Two Polynomials and Half-GCD Algorithm

345.

Lagrange Interpolation

346.

[Problem] Sum of r^i * poly(i)

347.

Polynomial with Binomial Coefficients

348.

Subset Sum Problem using Generating Functions

349.

Polynomial Factorization of (x^n - 1) and Cyclotomic Polynomials

350.

Schwartz–Zippel Lemma

351.

Lagrange Inversion Theorem

Matrices

352.

Matrix Exponentiation

353.

Permanent of a Matrix

354.

Freivald's Algorithm

355.

Vandermonde Matrix

356.

Hafnian of a Matrix / Number of Perfect Matchings in a Graph

357.

Frobenius Form of a Matrix and Fast Matrix Power

Linear Recurrence

358.

Linear Recurrence Relations

359.

Linear Recurrence using Cayley-Hamilton Theorem in O(N^2 log K)

360.

Linear Recurrence using Generating Functions in O(N log N log K)

361.

Linear Recurrence with Polynomial Coefficients

362.

Linear Recurrence on Matrices

363.

Generating Function of a Linear Recurrence

364.

Berlekamp Messey

365.

Reeds-Sloane Algorithm

Linear Algebra

366.

Gaussian Elimination

367.

Gaussian Elimination Modulo 2

368.

Determinant of a Matrix

369.

Determinant under Composite Modulo

370.

Characteristic Polynomial and Hesserberg Matrix

371.

[Problem] Determinant of Product Matrix

372.

Determinant of Sparse Matrix and Black Box Linear Algebra

373.

[Problem] Determinant of Permutant and Circulant Matrix

374.

GCD Determinant / Smith's Determinant

375.

Cauchy–Binet formula

376.

Inverse of a Matrix

377.

Inverse of a Matrix modulo 2

378.

Thomas Algorithm

379.

Vector Space and XOR Basis

380.

[Technique] XOR Basis ft Reduced Row Echelon Form

381.

[Technique] XOR Basis ft Lexicographically Largest Basis

382.

XOR Basis with Deletions

383.

q Binomial

Formulas

384.

Gauss's Eureka Theorem

385.

Titu's Lemma

386.

Lifting-the-exponent(LTE) Lemma

387.

Faulhaber's Formula and Bernoulli Numbers

Calculus

388.

Differentiation and Integration

389.

Line Integral

Probabilities and Expected Values

390.

Probabilities and Expected Values

391.

Expected Value Powers Technique

392.

The Slime Trick

393.

Expected Occurrence Time as Substring

394.

Gambler's Ruin

395.

Martingale

Mathematical Optimization

396.

Lagrange Multiplier

397.

Linear Programming / Simplex Algorithm

398.

Duality in Linear Programming (LP <> Flow)

Miscellaneous

399.

Continued Fractions

400.

Polynomial Real Roots

401.

Finite Field Arithmetic Binary

Copy Link to Strings

String Matching

402.

Knuth Morris Pratt (KMP) and Prefix Automaton

403.

Z algorithm

404.

String Matching using Bitsets

405.

String Matching with FFT ft Wildcard Matching

Hashing

406.

407.

408.

409.

Aho Corasick

410.

Aho Corasick

411.

Dynamic Aho Corasick

Suffix Structures

412.

Suffix Array

413.

Isomorphic Suffix Array

414.

Dynamic Suffix Array

415.

Suffix Automaton

416.

[Problem] Distinct Substring Queries in Range

417.

Suffix Tree

Palindromes

418.

Palindromic Tree

419.

Persistent Palindromic Tree

420.

Manachers Algorithm

421.

[Problem] Minimum Palindrome Factorization

422.

[Problem] Number of Palindromes in Range

Longest Common Subsequence (LCS)

423.

Longest Common Subsequence (LCS)

424.

All Substring Longest Common Subsequence

425.

Bit LCS

426.

Cyclic LCS

427.

LCS on RLE compressed string

Miscellaneous

428.

Balanced Brackets

429.

Expression Parsing

430.

Lyndon Factorization / Duval Algorithm

431.

Finding Repetitions / Main-Lorentz Algorithm

432.

De Bruijn Sequence

Copy Link to Dynamic Programming (DP)

Intro to DP

433.

Knapsack and Basic Dynamic Programming

434.

Knapsack and Subset Sum Optimizations

Digit DP

435.

Digit DP

DP Optimizations

436.

Divide and Conquer Optimization

437.

Knuth Optimization

438.

Aliens Trick / WQS Binary Search

439.

1D1D DP Optimization

440.

DP Optimization using Data Structures [Some Practice Problems]

Convex Hull Trick (CHT)

441.

Convex Hull Trick (CHT) and Dynamic CHT

442.

Persistent CHT

Li Chao Tree

443.

Li Chao Tree

444.

Persistent Li Chao Tree

445.

Extended Li Chao tree

Bit Related DP

446.

Bitmask DP

447.

Sum Over Subsets DP (SOS DP)

448.

[Problem] Subset Union of Bitsets

449.

Subset Convolution

450.

[Trick] Dynamic Submask Count

451.

[Problem] XOR Equation

More Tricks

452.

Open and Close Interval Trick

453.

Slope Trick

454.

x2 +1 Trick