Competitive Programming — High School Mastery
The problem-solving capstone of the Vietnamese HSG path: not more algorithms, but the working method — reading constraints, discovering the key observation, synthesizing techniques, proving correctness, optimizing, debugging plausible-but-wrong code, building counterexamples, stress testing, and harvesting partial scores — drilled through 14 process-first modules and graded in the C++20 sandbox.
Who this course is for
Students who finished the HSG Advanced and HSG Intensive courses (or equivalent) and can already implement advanced algorithms; the goal now is independent mastery of unfamiliar HSG and olympiad-style problems.
What you will be able to do
- Infer the algorithm class from constraints alone and state the operation budget before coding
- Decompose an unfamiliar statement into a mathematical model and a subproblem plan
- Discover invariants, parity, monotonicity, and exchange arguments by structured experimentation
- Prove greedy and DP correctness, and construct counterexamples for plausible-but-wrong approaches
- Synthesize combined techniques (DP + data structures, graphs + DP, offline + sweeps) under one budget
- Optimize a working solution: find the bottleneck, apply the acceleration, prove the new bound
- Debug compiled, sample-passing wrong code and repair it with minimal reasoning
- Stress-test with a brute/reference/generator harness and maximize partial score under contest pressure
The Mastery Process
The full pipeline from statement to defended solution: model, budget the complexity, find the cheapest correct idea, verify adversarially, implement. Every later module drills one stage of this loop.
Constraint to Complexity
Reading the constraint table as the setter's confession: n ≤ 20 means brute force is intended, n·q at 2·10^5 is a death sentence, values ≤ 10^18 mean log-scale. Honest op-count arithmetic first.
Problem Decomposition
Turning prose into a formal model: find the quantities, cut into independent subproblems, restate the objective (complement counting, equivalent objects), handle coupled constraints by state design.
Observation Discovery
Finding the unlock by experiment: compute small cases by hand, stare at the table, extract the invariant/parity/monotonicity — then prove it before trusting it.
Greedy Proof and Counterexamples
When sorting works and when it lies: exchange arguments, bottleneck scheduling, and constructing the adversary that breaks a plausible greedy.
DP Reasoning and Synthesis
Designing states from the objective's degrees of freedom, transitions from the last decision, and fusing DP with prefix/min structures when the naive transition is too fat.
Graph and Tree Synthesis
Fusing traversal order with DP: topological order as the DP schedule, DSU as reachability bookkeeping, and rerooting for when every node wants to be the root.
Offline and Query Synthesis
The offline superpower: read everything, sort events, sweep once. Turning q independent questions into one ordered pass, and counting contributions instead of configurations.
Optimization Laboratory
Improving a working solution methodically: profile the bottleneck, name its complexity, pick the acceleration that removes it, prove the new bound — the W is always the correct-but-too-slow baseline.
Partial Scoring Laboratory
Reading scoring bands as a design spec: every subtask is a solvable problem, the bands are a ladder, and a correct 40 points beats a heroic 0.
Wrong Solution Clinic
The debugging discipline: localize by bisecting the input space, name the bug category, build the minimal counterexample — the skill of reading code that lies politely.
Counterexample and Adversarial Lab
Attacking your own solution before the judge does: the adversarial checklist (ties, asymmetry, degeneracy, scale), minimal counterexample construction, and proof-first trust.
Stress Testing and Decision Training
The three-program harness: brute force as oracle, a generator, and differential testing; then the contest-level decisions the harness cannot make for you.
Mixed Expert Sets and Simulation
Problems with no topic label: the full pipeline under time discipline. The techniques are hidden; the recognition is the exam.