Advanced -> Constructive¶

Output-sensitive problems where the main work is proving the existence and structure of a valid construction.

Topic slug: advanced/constructive
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 3
Repo companion pages: 3
Curated external problems: 10

Microtopics¶

invariants
parity-constructions
extremal-arguments
witness-building
greedy-construction
output-sensitive-construction
case-splits
existence-proofs

Learning Sources¶

Source	Type
IOI Syllabus 2025	`Primary`
Tips on Constructive Algorithms	`Essay / Blog`
CSES books	`Reference`

Practice Sources¶

Source	Type
Codeforces constructive algorithms tag	`Practice`
CSES Problem Set	`Practice`
BOI task archive	`Practice`

Repo Companion Material¶

Material	Type
Build the Permutation note	`anchor note`
VMCOINS note	`anchor note`
Stress testing workflow	`verification guide`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Same Parity Summands	`Codeforces`	`Easy`	-	Construction	Parity	Math	Simple but very clean constructive decomposition logic.
Snow Walking Robot	`Codeforces`	`Easy`	-	Path Construction	Grid Moves; Cancellation	Paths; Grid	A short constructive path-building problem with neat cancellation ideas.
A-B Palindrome	`Codeforces`	`Medium`	-	Construction	Symmetry Reasoning	Palindrome	A standard constructive palindrome filling task.
Build the Permutation	`Codeforces`	`Medium`	-	Greedy Construction	Permutations; Greedy Placement	Permutations	Build-a-valid-structure problems are exactly the constructive sweet spot.
Corrupted Array	`Codeforces`	`Medium`	-	Reconstruction	Sorting; Multiset Reasoning	Arrays	A good example of reconstructing hidden structure from noisy data.
Beautiful Tree	`Codeforces`	`Hard`	-	-	-	Tree Construction; Number Theory; Perfect Square	Shows how a constructive proof can be turned into a valid graph output under strong arithmetic constraints.
Multiples and Power Differences	`Codeforces`	`Hard`	-	-	-	Matrix Construction; Number Theory; Invariants	Classic constructive use of a hidden invariant to force the judge-accepted structure.
Nezzar and Nice Beatmap	`Codeforces`	`Hard`	-	-	-	Ordering; Geometry; Greedy Construction	Representative output-construction problem where the hard part is discovering the structure, not maintaining data.
Strange Housing	`Codeforces`	`Hard`	-	-	-	Graph Construction; DFS	Good example of mixing traversal with a constructive certificate.
Cycle Closing	`Codeforces`	`Very Hard`	-	-	-	Graph Operations; Shortest Paths; Tree Structure	A high-end constructive problem where the implementation follows a delicate existence argument.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`BUILDTHEPERMUTATION`	Build the Permutation	`primary`	`medium`	alternating core construction; local extrema counting; monotone leftover tail	Note	Code
`VMCOINS`	Trò chơi với những đồng xu	`primary`	`hard`	promise-driven constructive; translation matching; small residual search	Note	Code
`VMMARBLE`	Phân loại bi	`secondary`	`medium`	final-color assignment; residual-state dp; capacity-2 moves	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py