Competitive Programming — High School Beginner
The Vietnamese Học sinh giỏi preparation path: reading statements, complexity, marking arrays, sorting and binary search, prefix and difference arrays, strings, number theory, STL, recursion and backtracking, basic DP, graphs, and four mock contests. Every problem is graded for real in the C++20 sandbox.
Who this course is for
High-school students (grades 10–12) preparing for Tin học chọn Học sinh giỏi from school rounds to provincial level; basic C++ knowledge (or taking cpp-beginner in parallel).
What you will be able to do
- Read a contest statement and extract exact constraints, I/O format, and subtasks
- Estimate complexity and pick an algorithm that fits the time limit
- Implement marking/frequency arrays, sorting, binary search, prefix and difference arrays fluently
- Solve string, number-theory (sieve), STL, recursion, and backtracking problems
- Solve basic DP and BFS/DFS graph problems at provincial-HSG level
- Sit four mock contests with subtasks and manage a 180-minute exam
Contest Reading & the C++ Bridge
Read a real statement (input/output/constraints/examples), understand judge verdicts, and take the solve(istream&, ostream&) convention used across the whole track.
Loops as Simulation
for/while as simulation engines: counters, accumulators, digit processing, and repeated computation — the patterns hidden inside most easy HSG problems.
Arrays
Indexing, traversal, min/max, counting, reverse and rotate — the array mechanics behind half of all easy HSG problems.
Marking & Frequency Arrays
The mảng đánh dấu technique: presence flags, frequency counting, and the value-range rule that decides when it is even possible.
Greedy Basics
Sorting + greedy choice with exchange-argument reasoning — and the counterexamples that kill bad greedy strategies.
Sorting
std::sort, custom comparators, and the sort-then-sweep family: min difference, merged intervals, and ranking.
Searching & Binary Search
Linear search, binary search as an invariant, lower_bound/upper_bound, and binary search on the answer.
Prefix Sums
Answer range-sum queries in O(1): 1D and 2D prefix sums, prefix counting, zero-sum subarrays, fixed-window maximum.
Difference Arrays
O(1) range updates: 1D difference arrays, reconstruction by prefix sum, 2D rectangle painting, exact-coverage counting.
Strings
std::string mechanics: indexing, traversal, palindromes, run-length encoding, anagram signatures, and a first honest look at counting distinct substrings.
Basic Number Theory
Divisibility, gcd/lcm with Euclid, divisors and primes in O(sqrt n), digit sums, and modular thinking for sums.
STL for Contests
The standard containers as problem-solving tools: vector, set, map, priority_queue, stack, queue, deque — chosen by problem shape.
Recursion
Functions that call themselves: base cases, tracing the stack, factorial and combination identities, recursive number tricks.
Backtracking
Systematic exhaustive search: choose, explore, uncommit — and prune so the search tree stays small enough to finish.
Dynamic Programming Basics
Stop recomputing: define a state, a transition, and base cases — then fill a table instead of recursing forever.
Graph Theory Fundamentals
Store a graph as adjacency lists, then walk it: BFS for shortest unweighted paths, DFS for structure, flood fill for grids.
Two Pointers & Sliding Window
Turn O(n^2) pair scans into O(n): two indices that each move forward at most n times.
Contest Technique
Read constraints like a lawyer, budget operations like an engineer, and bank partial credit like an investor.
Debugging Competitive Programs
Wrong answers are clues: reproduce, isolate, instrument, fix — then re-test the boundary that broke you.
Beginner Contest Series
Three mock contests mixing every beginner tool — time management and problem selection are graded skills too.
- Contest Strategy⭐ beginner⏳ 15 min read
- Time Management Under a Clock⭐ beginner⏳ 14 min read
- Contest 1-A: Desert Mirage⭐ beginner⏳ 10 min read
- Contest 1-B: Oasis Shares⭐ beginner⏳ 15 min read
- Contest 2-A: Lantern Rows⭐ beginner⏳ 10 min read
- Contest 2-B: Balloon Heights⭐ beginner⏳ 20 min read
- Final-A: Grid Corridor⭐ beginner⏳ 25 min read
- Final-B: The Vault Clock⭐ beginner⏳ 20 min read