Revision Topics

• Algebra

• Fundamentals

• Binary Exponentiation
• Euclidean algorithm for computing the greatest common divisor
• Extended Euclidean Algorithm
• Linear Diophantine Equations

• Fibonacci Numbers

• Prime numbers

• Sieve of Eratosthenes
• Linear Sieve
• Primality tests

• Integer factorization

• Number-theoretic functions

• Euler’s totient function

• Number of divisors / sum of divisors

• Modular arithmetic

• Modular Inverse
• Linear Congruence Equation
• Chinese Remainder Theorem
• Garner’s Algorithm
• Factorial modulo p
• Discrete Log
• Primitive Root
• Discrete Root

• Montgomery Multiplication

• Number systems

• Balanced Ternary

• Gray code

• Miscellaneous

• Bit manipulation
• Enumerating submasks of a bitmask
• Arbitrary-Precision Arithmetic
• Fast Fourier transform
• Operations on polynomials and series
• Continued fractions

• Factoring Exponentiation

• Data Structures

• Fundamentals

• Minimum Stack / Minimum Queue

• Sparse Table

• Trees

• Disjoint Set Union
• Fenwick Tree
• Sqrt Decomposition
• Segment Tree
• Treap
• Sqrt Tree

• Randomized Heap

• Advanced

• Deleting from a data structure in O(T(n) log n)

• Dynamic Programming

• Introduction to Dynamic Programming
• Knapsack Problem

• DP optimizations

• Divide and Conquer DP

• Knuth’s Optimization

• Tasks

• Dynamic Programming on Broken Profile. Problem “Parquet”

• Finding the largest zero submatrix

• String Processing

• Fundamentals

• String Hashing
• Rabin-Karp for String Matching
• Prefix function - Knuth-Morris-Pratt
• Z-function
• Suffix Array

• Aho-Corasick algorithm

• Advanced

• Suffix Tree
• Suffix Automaton

• Lyndon factorization

• Tasks

• Expression parsing
• Manacher’s Algorithm - Finding all sub-palindromes in O(N)

• Finding repetitions

• Linear Algebra

• Matrices

• Gauss & System of Linear Equations
• Gauss & Determinant
• Kraut & Determinant

• Rank of a matrix

• Combinatorics

• Fundamentals

• Finding Power of Factorial Divisor
• Binomial Coefficients

• Catalan Numbers

• Techniques

• The Inclusion-Exclusion Principle
• Burnside’s lemma / Pólya enumeration theorem
• Stars and bars

• Generating all K-combinations

• Tasks

• Placing Bishops on a Chessboard
• Balanced bracket sequences

• Counting labeled graphs

• Numerical Methods

• Search

• Binary Search
• Ternary Search

• Newton’s method for finding roots

• Integration

• Integration by Simpson’s formula

• Geometry

• Elementary operations

• Basic Geometry
• Finding the equation of a line for a segment
• Intersection Point of Lines
• Check if two segments intersect
• Intersection of Segments
• Circle-Line Intersection
• Circle-Circle Intersection
• Common tangents to two circles

• Length of the union of segments

• Polygons

• Oriented area of a triangle
• Area of simple polygon
• Check if points belong to the convex polygon in O(log N)
• Minkowski sum of convex polygons
• Pick’s Theorem - area of lattice polygons

• Lattice points of non-lattice polygon

• Convex hull

• Convex hull construction

• Convex hull trick and Li Chao tree

• Sweep-line

• Search for a pair of intersecting segments

• Planar graphs

• Finding faces of a planar graph

• Point location in O(log N)

• Miscellaneous

• Finding the nearest pair of points
• Delaunay triangulation and Voronoi diagram
• Vertical decomposition
• Half-plane intersection - S&I Algorithm in O(N log N)

• Manhattan Distance

• Graphs

• Graph traversal

• Breadth First Search

• Depth First Search

• Connected components, bridges, articulations points

• Finding Connected Components
• Finding Bridges in O(N+M)
• Finding Bridges Online
• Finding Articulation Points in O(N+M)
• Strongly Connected Components and Condensation Graph

• Strong Orientation

• Single-source shortest paths

• Dijkstra - finding shortest paths from given vertex
• Dijkstra on sparse graphs
• Bellman-Ford - finding shortest paths with negative weights
• 0-1 BFS

• D´Esopo-Pape algorithm

• All-pairs shortest paths

• Floyd-Warshall - finding all shortest paths

• Number of paths of fixed length / Shortest paths of fixed length

• Spanning trees

• Minimum Spanning Tree - Prim’s Algorithm
• Minimum Spanning Tree - Kruskal
• Minimum Spanning Tree - Kruskal with Disjoint Set Union
• Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor
• Kirchhoff Theorem

• Prüfer code

• Cycles

• Checking a graph for acyclicity and finding a cycle in O(M)
• Finding a Negative Cycle in the Graph

• Eulerian Path

• Lowest common ancestor

• Lowest Common Ancestor
• Lowest Common Ancestor - Binary Lifting
• Lowest Common Ancestor - Farach-Colton and Bender algorithm
• Solve RMQ by finding LCA

• Lowest Common Ancestor - Tarjan’s off-line algorithm

• Flows and related problems

• Maximum flow - Ford-Fulkerson and Edmonds-Karp
• Maximum flow - Push-relabel algorithm
• Maximum flow - Push-relabel algorithm improved
• Maximum flow - Dinic’s algorithm
• Maximum flow - MPM algorithm
• Flows with demands
• Minimum-cost flow

• Assignment problem

• Matchings and related problems

• Bipartite Graph Check
• Kuhn’s Algorithm - Maximum Bipartite Matching

• Hungarian Algorithm

• Miscellaneous

• Topological Sorting
• Edge connectivity / Vertex connectivity
• Tree painting
• 2-SAT

• Heavy-light decomposition

• Miscellaneous

• Sequences

• RMQ task (Range Minimum Query - the smallest element in an interval)
• Longest increasing subsequence
• Search the subsegment with the maximum/minimum sum
• K-th order statistic in O(N)

• MEX task (Minimal Excluded element in an array)

• Game Theory

• Games on arbitrary graphs

• Sprague-Grundy theorem. Nim

• Schedules

• Scheduling jobs on one machine
• Scheduling jobs on two machines

• Optimal schedule of jobs given their deadlines and durations

• Miscellaneous

• Tortoise and Hare Algorithm (Linked List cycle detection)
• Josephus problem
• 15 Puzzle Game: Existence Of The Solution
• The Stern-Brocot Tree and Farey Sequences

APPROACH 2

1. Binary Search :
   Tutorial, Problems 6.3k, Tutorial, Implementation 1.6k, Problem 3.6k
2. Quicksort :
   Tutorial, Implementation 961, Tutorial 454
3. Merge Sort :
   Tutorial, Implementation 450, Tutorial 454
4. Suffix Array :
   Tutorial 842, Tutorial, Implementation 668, Tutorial, Implementation 153, Problem 374, Problem 181
5. Knuth-Morris-Pratt Algorithm (KMP) :
   Tutorial 639, Tutorial, Implementation 205, Tutorial 62, Problem 315
6. Rabin-Karp Algorithm :
   Tutorial, Implementation 296, Tutorial 55, Problem 115, Problem 61
7. Tries :
   Tutorial, Problems 427, Tutorial : I, 198 II 45, Tutorial 71, Problem 141, Problem 40, Problem 67
8. Depth First Traversal of a graph :
   Tutorial, Impelementation 460, Tutorial, Problems 268, Problem 280, Problem 102, Problem 88
9. Breadth First Traversal of a graph :
   Tutorial, Impelementation 165, Tutorial, Problems 268, Problem 121, Problem 58, Problem 35, Flood Fill 29
10. Dijkstra’s Algorithm :
    Tutorial, Problems 304, Problem 168, Tutorial(greedy) 62, Tutorial (with heap) 39, Implementation 56, Problem 62, Problem 60
11. Binary Indexed Tree :
    Tutorial, Problems 265, Tutorial 112, Original Paper 35, Tutorial 26, Tutorial 18, Problem 74, Problem 26,
    Problem 27, Problem 27, Problem 24, Problem 28, Problem 29
12. Segment Tree (with lazy propagation) :
    Tutorial, Implementation 228, Tutorial 103, Tutorial, Problems, Implementation 83, Tutorial, Implementation and Various Uses 48, Persistent Segment Tree: I 20, II 22, problems same as BIT, Problem 74, Problem 20/HLD is used as well/
13. Z algorithm :
    Tutorial, Problem 427, Tutorial 27, Tutorial 22, problems same as KMP.
14. Floyd Warshall Algorithm :
    Tutorial, Implementation 145, Problem 70, Problem 8
15. Sparse Table (LCP, RMQ) :
    Tutorial, Problems 97, Tutorial, Implementation(C++) 24, Java implementation 8
16. Heap / Priority Queue / Heapsort :
    Implementation, Explanation 133, Tutorial 49, Implementation 17, Problem 104, Chapter from CLRS
17. Modular Multiplicative Inverse 86
18. Binomial coefficients (nCr % M): Tutorial 137, Tutorial 13, Paper 18 (Link Not Working), Problem 33
19. Suffix Automaton :
    Detailed Paper 33, Tutorial, Implementation (I) 33, Tutorial, Implementation (II) 9, Problem 9, Problem 4, Problem 115, Problem 181, Tutorial, Implementation 6
20. Lowest Common Ancestor :
    Tutorial, Problems 110, Paper 24, Paper 12, Problem 33, Problem 13, Problem 21
21. Counting Inversions :
    Divide and Conquer 68, Segment Tree 23, Fenwick Tree 26, Problem 28
22. Euclid’s Extended Algorithm 130
23. Suffix Tree :
    Tutorial 66, Tutorial 9, Intro 7, Construction : I 5, II 3, Implementation 6, Implementation 3, Problem 7, Problem 5, Problem 3, Problem 2
24. Dynamic Programming :
    Chapter from CLRS(essential), Tutorial, Problems 403, Problem 193, Problem 43, Problem 29, Problem 29, Tutorial 28, Problem 19, Problem 9, Problem 29, Longest Increasing Subsequence 16, Bitmask DP 99, Bitmask DP 24, Optimization 35, Problem 18, Problem 13, Problem 8, Problem 7, Problem 8, Problem 10, Problem 23, DP on Trees : I 33, II 13
25. Basic Data Structures :
    Tutorial 278, Stack Implementation 163, Queue Implementation, Tutorial 52, Linked List Implementation 142
26. Logarithmic Exponentiation 147
27. Graphs :
    Definition, Representation 282, Definition, Representation 27, Problem 115, Problem 40
28. Minimum Spanning Tree :
    Tutorial 35, Tutorial, Kruskal’s Implementation 26, Prim’s Implementation 11, Problem 17, Problem 7, Problem 28, Problem 5, Problem 3
29. Efficient Prime Factorization 62
30. Combinatorics :
    Tutorial, Problems 229, Problem 102, Tutorial 64
31. Union Find/Disjoint Set :
    Tutorial 87, Tutorial, Problems 43, Problem 35, Problem 28, Problem 15
32. Knapsack problem :
    Solution, Implementation 136
33. Aho-Corasick String Matching Algorithm :
    Tutorial 61, Implementation 23, Problem 15, Problem 2, Problem 3, Problem 3
34. Strongly Connected Components :
    Tutorial, Implementation 46, Tutorial 3, Problem 16, Problem 4, Problem 4
35. Bellman Ford algorithm :
    Tutorial, Implementation 53, Tutorial, Implementation 3, Problem 10, Problem 10
36. Heavy-light Decomposition :
    Tutorial, Problems 47, Tutorial, Implementation 12, Tutorial 10, Implementation 6, Implementation 3, Problem 7, Problem 3, Problem 3
37. Convex Hull :
    Tutorial, Jarvis Algorithm Implementation 52, Tutorial with Graham scan 5, Tutorial 2, Implementation 5, Problem 7, Problem 12, Problem 2, Problem 1, Problem 4
38. Line Intersection :
    Tutorial, Implementation 42, Tutorial, Problems 7
39. Sieve of Erastothenes 67
40. Interval Tree :
    Tutorial, Implementation 56, Problem 23, Problem 3, Problem 3, Problem 3, Problem 2, Problem 4, Tutorial 3
41. Counting Sort 38
42. Probabilities 84
43. Matrix Exponentiation :
    Tutorial 109, Tutorial 8
44. Network flow :
    (Max Flow)Tutorial : I, 33 II 6, Max Flow(Ford-Fulkerson) Tutorial, Implementation 19, (Min Cut) Tutorial, Implementation 4, (Min Cost Flow)Tutorial : I, 6 II, 2 III 1, Dinic’s Algorithm with Implementation 5, Max flow by Edmonds Karp with Implementation 7, Problem 10, Problem 2, Problem 2, Problem 3, Problem 2, Problem, Problem 4, Problem 1, Problem 1, Problem 1, Problem, Problem 1, Problem, Problem 2, Problem 3
45. K-d tree :
    Tutorial 63, Tutorial 16, Implementation 20, Problem 24
46. Deque 49
47. Binary Search Tree :
    Tutorial, Implementation 105, Searching and Insertion 22, Deletion 7
48. Quick Select :
    Implementation 25, Implementation 4
49. Treap/Cartesian Tree :
    Tutorial(detailed) 32, Tutorial, Implementation 14, Uses and Problems 25, Problem 2, Problem 2
50. Game Theory :
    Detailed Paper 73, Tutorial, Problems 24, Grundy Numbers 12, Tutorial with example problems - I, 10 II, 2 III, 1 IV 1, Tutorial, Problems 15, Problem 5, Problem 7, Problem 8, Problem 5, Problem 2, Problem 2, Problem 4, Problem 5, Problem 8, Problem 4, Problem 6, Nim 8
51. STL (C++) :
    I, 325 II 130, Crash Course 440
52. Maximum Bipartite Matching 35
53. Manacher’s Algorithm :
    Implementation 34, Tutorial 18, Tutorial, Implementation 3, Tutorial, Implementation 3, Problem 5, Problem 4, Problem 9
54. Miller-Rabin Primality Test 25 and this 4
55. Stable Marriage Problem 50
56. Hungarian Algorithm 39, Tutorial 6
57. Sweep line Algorithm : I 29, II 8
58. LCP :
    Tutorial, Implementation 91, Tutorial, Implementation 10
59. Gaussian Elimination 35
60. Pollard Rho Integer Factorization 11, problem 11
61. Topological Sorting 26
62. Detecting Cycles in a Graph : Directed - I 16, II 7
    Undirected : I 7
63. Geometry : Basics 59, Tutorial 29
64. Backtracking :
    N queens problem 53, Tug of War 12, Sudoku 12
65. Eulerian and Hamiltonian Paths :
    Tutorial 8, Tutorial 2, (Eulerian Path and Cycle)Implementation 3, (Hamiltonian Cycle)Implementation 7
66. Graph Coloring :
    Tutorial, Implementation 65
67. Meet in the Middle :
    Tutorial 71, Implementation 13
68. Arbitrary Precision Integer(BigInt) 6, II 1
69. Radix Sort 15, Bucket Sort 6
70. Johnson’s Algorithm :
    Tutorial 49, Tutorial 6, Implementation 11
71. Maximal Matching in a General Graph :
    Blossom/Edmond’s Algorithm, Implementation 22, Tutte Matrix 2, Problem 8
72. Recursion : I, 63 II 15, Towers of Hanoi 25 with explanation 13
73. Inclusion and Exclusion Principle : I 29, II 1
74. Co-ordinate Compression 23
75. Sqrt-Decomposition :
    Tutorial 53, Tutorial 13, Problem 31, Problem 17
76. Link-Cut Tree :
    Tutorial 53, Wiki 12, Tutorial, Implementation 17, Problem 15, Problem 5, Problem 4, Problem 7
77. Euler’s Totient Function :
    Explanation, Implementation, Problems 63, Explanation, Problems 14
78. Burnside Lemma :
    Tutorial 51, Tutorial 10, Problem 17
79. Edit/Levenshtein Distance :
    Tutorial 35, Introduction 12, Tutorial 11, Problem 19, Problem 12
80. Branch and Bound 77
81. Math for Competitive Programming 759
82. Mo’s Algorithm : Tutorial and Problems 302