data structures & algorithms (legend)
contest-grade algorithms, mapped onto cp-algorithms. segment trees, suffix automata, max flow, fft, and the dp optimizations that win icpc and codeforces. part 3 of 3.
28 lessons|6 modules|~6 hours
what you’ll learn
- answer range queries at speed with fenwick trees, segment trees, and lazy propagation
- decompose trees with binary lifting, euler tours, and heavy-light decomposition
- match and search strings with kmp, the z-function, suffix arrays, and aho-corasick
- solve the hard graph tier: scc, bridges, max flow, bipartite matching, and 2-sat
- wield fft, bitmask and digit dp, and the dp optimizations contests are won on
curriculum
planning sketchthis is a rough curriculum we’re still planning. modules and lessons are likely to shift before any lesson is recorded. want to shape it? mail@karnstack.com.
01
module one
range query structures
62 min5 lessons01sqrt decomposition: the gateway to range queriescoming soon12m
02fenwick tree (binary indexed tree)coming soon12m
03segment trees: point update, range querycoming soon15m
04lazy propagation: range updates done rightcoming soon14m
05sparse tables: o(1) idempotent range queriescoming soon9m
checkpoint
module quiz · range query structures
5 questions · ~5m · test your recall before moving on
02
module two
trees on trees
64 min5 lessons06binary lifting and lowest common ancestorcoming soon13m
07euler tour: flattening a tree into an arraycoming soon9m
08heavy-light decompositioncoming soon15m
09treaps: balanced bsts by coin flipcoming soon13m
10persistent data structures: remembering every past versioncoming soon14m
checkpoint
module quiz · trees on trees
5 questions · ~5m · test your recall before moving on
03
module three
strings at contest speed
61 min5 lessons11polynomial hashing: compare any two substrings in o(1)coming soon10m
12the prefix function and kmpcoming soon13m
13the z-functioncoming soon9m
14suffix arrayscoming soon15m
15aho-corasick: match thousands of patterns at oncecoming soon14m
checkpoint
module quiz · strings at contest speed
5 questions · ~5m · test your recall before moving on
04
module four
graphs, the hard tier
67 min5 lessons16strongly connected components: tarjan and kosarajucoming soon14m
17bridges and articulation pointscoming soon11m
18max flow: ford-fulkerson to diniccoming soon15m
19bipartite matching and min-cut applicationscoming soon14m
202-sat: boolean satisfiability you can solve fastcoming soon13m
checkpoint
module quiz · graphs, the hard tier
5 questions · ~5m · test your recall before moving on
05
module five
math and number theory
50 min4 lessons21modular arithmetic, fast exponentiation, modular inversecoming soon11m
22sieves, gcd, and the chinese remainder theoremcoming soon11m
23combinatorics and inclusion-exclusioncoming soon13m
24fft and ntt: multiply polynomials in n log ncoming soon15m
checkpoint
module quiz · math and number theory
5 questions · ~5m · test your recall before moving on
06
module six
dp optimizations, geometry, and the close
60 min5 lessons25bitmask dpcoming soon13m
26digit dpcoming soon10m
27dp optimizations: divide-and-conquer dp and the convex hull trickcoming soon15m
28computational geometry: convex hull and the sweep linecoming soon14m
--contest strategy and what to read nextcoming soon8m
checkpoint
module quiz · dp optimizations, geometry, and the close
5 questions · ~5m · test your recall before moving on
frequently asked
- when does this launch?
- in planning, sequenced after patterns. the curriculum on this page is a sketch. modules and lessons are likely to shift before any lesson is recorded.
- who is this for?
- engineers prepping for competitive programming (icpc, codeforces) or anyone who wants the hardest tier of structures and algorithms. it assumes parts 1 and 2 cold.
- why does it follow cp-algorithms?
- cp-algorithms.com is the canonical reference for contest algorithms. this part walks its hardest topics in a teachable order, with the intuition the reference assumes you already have.