Competitive Programming — High School Advanced
The top level of the Vietnamese competitive-programming path, toward national and olympiad-style problems: lazy trees, binary lifting, tree DP, HLD, SCC, flow and matching, digit/interval/suffix DP, number theory, combinatorics, geometry, synthesis, debugging, and mock contests — all graded in the C++20 sandbox.
Who this course is for
Students who finished the HSG Intermediate course (or equivalent): fluent with segment trees, DSU, Dijkstra, DAG DP, bitmask DP, modular arithmetic, and KMP, ready for national-level HSG Tin hoc and olympiad preparation.
What you will be able to do
- Derive and prove algorithms for unfamiliar problems from constraints and structure
- Implement lazy segment trees, HLD, binary lifting, SCC, and flow networks under contest limits
- Model problems as digit DP, interval DP, tree DP, or network flow and defend the transformation
- Apply suffix structures, Mobius counting, and integer geometry with correctness arguments
- Combine multiple techniques in synthesis problems and stress-test solutions against brute force
- Sit six graded mock-contest problems per series, banking partial credit under time pressure
Advanced Attack Patterns
Meet-in-the-middle halving of exponential search, XOR and pairing invariants, constructive permutations, brute force rescaled as an oracle, and guess-check on monotone answers.
Lazy Propagation Segment Trees
Deferred updates with lazy tags: range add/min, range assign/sum, compose order for mixed tags, and the max-subarray node whose pull merges left, right, and across.
Fenwick Variants and Offline Power
The BIT beyond prefix sums: kth-order descent in O(log n), offline sweeps that reorder hard online problems into easy sorted ones, difference tricks for range updates, and inversion counting.
Binary Lifting and LCA
Sparse parent tables turn ancestor walks into O(log n) jumps; depth equalization and synchronized descent answer lowest common ancestors, k-th ancestors, and path queries on 2·10^5-node trees.
Tree DP: Take, Skip, and Reroot
The in/out state pattern solves independent set, vertex cover, and matching-shaped problems on trees; the cross term finds diameters; rerooting answers every node's question in one extra pass.
Heavy-Light Decomposition
Split a tree into chains so every root path is O(log n) segments; run the M2 lazy trees over chain positions to answer path updates and path aggregates in O(log^2 n).
Euler Tour Queries
Flatten the tree once and every subtree becomes a range: BIT-backed subtree adds, marked-node counts, and path updates through the 4-point LCA trick.
Strongly Connected Components
Kosaraju's two-pass DFS finds every SCC in O(n + m); shrinking components turns any digraph into a DAG, unlocking the whole Intermediate DAG toolbox.
Max Flow and Matching
Model capacities as networks, augment along BFS shortest paths, and read the min cut out of the final residual graph — bipartite matching included as a special case.
Digit DP
Counting over huge numeric ranges by walking the digits: tight chains, free-state transitions, and aggregated sums.
Interval DP
Answers built from inside-out intervals: split points, prefix-sum costs, and the O(n^3)/O(n^2) loops that make them affordable.
String Structures
Rolling hashes, the Z-function, pattern matching, and suffix arrays — the machinery behind substring equality and occurrence counting.
Number Theory II
Fermat inverses, factorial binomials, totient prefix sums, and CRT — modular arithmetic as a working toolset.
Combinatorics
Catalan counts, inclusion-exclusion, and constrained lattice paths — counting structures with closed forms mod 1e9+7.
Computational Geometry
Integer-only geometry: orientation tests, convex hulls, point-in-polygon, and closest pair — precision without floating point.
Technique Synthesis
Problems where two techniques must combine: prefix+search counting, compression+Fenwick, sweep+heap scheduling, and answer-search+greedy.
Debugging Under Contest Load
The three bug classes that cost the most points — overflow, stack depth, off-by-one — as graded hunts.
Contest Series I — Structures and Graphs
Two 120-minute mock contests retesting lazy trees, SCC, MST reasoning, and DSU under time pressure.
- Contest Scan — Reading for Structure⭐⭐⭐ advanced⏳ 25 min read
- Banking Points — Partial Credit as a Strategy⭐⭐⭐ advanced⏳ 25 min read
- Contest 1-A: Fever Chart⭐ beginner⏳ 40 min read
- Contest 1-B: Recipe Clusters⭐ beginner⏳ 40 min read
- Contest 2-A: Backup Network⭐ beginner⏳ 40 min read
- Contest 2-B: Island Mergers⭐ beginner⏳ 40 min read
Contest Series II — Trees and Strings
Two more 120-minute mock contests: binary lifting, KMP, subtree DP, Euler tours, and tries under time pressure.
- Contest Scan — Trees and Strings Edition⭐⭐⭐ advanced⏳ 25 min read
- Reading Your Own Code — the 5-Minute Audit⭐⭐⭐ advanced⏳ 25 min read
- Contest 3-A: Signal Chain⭐ beginner⏳ 40 min read
- Contest 3-B: Chant Rhythm⭐ beginner⏳ 40 min read
- Contest 4-A: Watchtower Coverage⭐ beginner⏳ 40 min read
- Contest 4-B: Motif Counter⭐ beginner⏳ 40 min read
Final HSG Simulation
The closing contest set: sweeps, answer binary search, convex hulls, Mobius counting, and a mixed drill.