Competitive Programming — High School Intermediate
The provincial-HSG level of the Vietnamese competitive-programming path: complexity budgets, binary search, interval sweeps, exchange-argument greedy, Fenwick and segment trees, DSU/MST, Dijkstra, DAG counting, tree algorithms, sequence/knapsack/bitmask DP, number theory, hashing and KMP, synthesis, debugging, and three mock contests — all graded in the C++20 sandbox.
Who this course is for
Students who finished the HSG Beginner course (or equivalent): fluent C++ I/O, arrays, sorting, prefix sums, basic DP and graphs, ready for provincial-level HSG Tin hoc.
What you will be able to do
- Pick an algorithm from the constraint line and defend the complexity choice
- Implement Fenwick trees, segment trees, DSU, Dijkstra, and topological DP under contest time limits
- Derive sequence/knapsack/bitmask DP states and transitions from scratch
- Apply hashing, KMP, two pointers, and exchange-argument greedy with correctness arguments
- Debug defective contest programs systematically: reproduce, isolate, verify
- Sit three 120-minute mock contests, banking subtask points under time pressure
Algorithm Analysis — Budgets, Amortized, and Meet-in-the-Middle
Turn constraints into an operation budget, recognize amortized cost, split search spaces in half, preprocess static ranges, and convert intervals into events.
Binary Search Mastery — From Arrays to the Answer
lower_bound and upper_bound as precision tools, occurrence counting, the monotonic predicate, and binary searching the answer itself with an honest feasibility check.
Intervals and Sweep Mastery
Merging, minimum covering points, minimum rooms (the tie convention), interval insertion, and free-time computation — all as sorted-event reasoning.
Greedy With Proof — Exchange Arguments and Heaps
Proving greedy by adjacent swaps, heap-driven merging, earliest-deadline-first, the two-heap running median, slot filling, and lookahead refueling.
Fenwick Trees — Dynamic Prefix Sums
The lowbit anatomy, point-update prefix-sum queries, prefix max with its one-way limitation, coordinate compression, and inversion counting.
Segment Trees — Range Queries With Range Updates
Build the recursive segment tree, extend it beyond sums with any merge, then add lazy propagation so range updates become O(log n) too.
DSU & Minimum Spanning Trees — Connectivity as a Tool
Disjoint set union with path halving and union by size, Kruskal's MST, redundant edges, and bottleneck queries answered offline while the forest grows.
Shortest Paths — Dijkstra & 0-1 BFS
Dijkstra's greedy expansion over a priority queue, why negative edges break it, the deque-based 0-1 BFS, and where plain BFS is already optimal.
DAGs & Topological Order — When Precedence Rules
Kahn's in-degree queue, the cycle verdict (count short of n), lexicographic order via min-heap, longest chains, critical paths, and path counting on DAGs.
Trees — Traversal, Subtrees, and Diameter
Parent-skip DFS/BFS (iterative), subtree sizes in reverse-BFS order, pre-order with sorted children, and diameter as the first DP on trees.
Sequence DP — LIS, Kadane, LCS
Three canonical sequence DPs: longest increasing subarray two ways, best contiguous sum with a one-line reset, and longest common subsequence with a rolling row.
Knapsack — 0/1, Unbounded, Counting
One array, two loop directions: reverse weight loop for 0/1 (each item once), forward for unbounded (reuse allowed). The direction is the policy.
Bitmask DP — Subsets as Integers
Represent a subset as an n-bit integer, iterate masks, transition by clearing one bit. Feasible only while n ≤ 20 — read that constraint first.
Number Theory — Sieve, GCD, Modular Power
Prime tables in O(n log log n), the gcd identity with safe ordering, binary exponentiation, and the modulo hygiene that decides verdicts.
Strings — Hashing and Pattern Matching
Rolling hash to compare substrings in O(1), palindromic prefix detection, distinct substring counting, and KMP for occurrence counting.
Synthesis — Choosing and Combining Techniques
Recognition under pressure: sliding windows, prefix-map counting, Kadane, exchange arguments, and a checkpoint that combines a data structure with greedy reconstruction.
Debugging — Fixing Broken Contest Code
Five real defective programs: read the code like a judge reads a submission, find the bug, and fix it.
Intermediate Contest Series
Three mock contests (two problems each) mixing every intermediate tool — time management and problem selection are graded skills too.
- Contest Strategy — Scan, Rank, Secure⭐⭐ intermediate⏳ 20 min read
- Time Management — When to Abandon a Problem⭐⭐ intermediate⏳ 20 min read
- Contest 2-A: Cầu thang phí⭐ beginner⏳ 25 min read
- Contest 2-B: Phường thị⭐ beginner⏳ 25 min read
- Contest 3-A: Mưa giữ nước⭐ beginner⏳ 25 min read
- Contest 3-B: Ngày thi cân bằng⭐ beginner⏳ 25 min read