Module 1: 2D DP

Longest common subsequence (LCS)
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) in $O(N \log N)$
Knapsack problem
Lazy DP

Module 2: DSU

System of disjoint sets

Module 3: MST

Minimum and maximum spanning trees
Kruskal's Algorithm
Prim's Algorithm
Borůvka's Algorithm

Module 4: Combinatorics

Stars and columns
The principle of inclusion-exclusion

Module 5: Geometry

Finding the area of a simple polygon

Module 6: Arbitrary-Precision Arithmetic

Long Arithmetic

Module 7: Data structures for keeping minimum

Stack with Minimum
Queue with Minimum
Deque with Minimum

Module 8: Heap [BONUS]

Binary Heap

Lazy DP - Preparation to IOI Part 3

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 3/Module 1: 2D DP/Lazy DP

Lazy DP

Lazy DP