Constructive Algorithms
Parity arguments, invariants, greedy constructions, and reverse simulation through 10 problems.
Lessons
1. Introduction to Constructive Algorithms
Building valid solutions from constraints
2. Techniques Overview
What you'll learn
3. Codeforces 1375D Replace by MEX - Problem Statement
CF 1375D - transform array using MEX operations
4. Codeforces 1375D Replace by MEX - Why Naive Fails
Random operations don't converge
5. Codeforces 1375D Replace by MEX - Solution
Fix positions using MEX cycles
6. Codeforces 1375D Replace by MEX - Implementation
Greedy MEX placement
7. Codeforces 1375D Replace by MEX - Example and Complexity Analysis
Quadratic in array size
8. Codeforces 1450C1 Errich-Tac-Toe - Problem Statement
CF 1450C1 - modify grid to avoid wins
9. Codeforces 1450C1 Errich-Tac-Toe - Solution
Change one color class
10. Codeforces 1450C1 Errich-Tac-Toe - Implementation
Color class transformation
11. Codeforces 1450C1 Errich-Tac-Toe - Example and Complexity Analysis
Linear in grid size
12. Codeforces 1485D Multiples and Power Differences - Problem Statement
CF 1485D - construct grid with divisibility
13. Codeforces 1485D Multiples and Power Differences - Solution
LCM checkerboard
14. Codeforces 1485D Multiples and Power Differences - Implementation
LCM-based checkerboard
15. Codeforces 1485D Multiples and Power Differences - Example and Complexity Analysis
Linear construction
16. Codeforces 1559D1 Mocha and Diana - Problem Statement
CF 1559D1 - add edges to two forests simultaneously
17. Codeforces 1559D1 Mocha and Diana - Solution
Greedy with dual DSU
18. Codeforces 1559D1 Mocha and Diana - Implementation
Dual DSU edge selection
19. Codeforces 1559D1 Mocha and Diana - Example and Complexity Analysis
Quadratic pair iteration
20. Codeforces 1605D Treelabeling - Problem Statement
CF 1605D - label tree to control XOR traversal
21. Codeforces 1605D Treelabeling - Why Naive Fails
Exponential labelings
22. Treelabeling - Key Insight
Group numbers by highest bit
23. Codeforces 1605D Treelabeling - Solution
Bipartite coloring by bit groups
24. Codeforces 1605D Treelabeling - Implementation
Bipartite assignment by bit
25. Codeforces 1605D Treelabeling - Example and Complexity Analysis
Linear tree traversal
26. Codeforces 1572B Xor of 3 - Problem Statement
CF 1572B - make array all zeros with XOR operations
27. Codeforces 1572B Xor of 3 - Why Naive Fails
Search space is huge
28. Codeforces 1572B Xor of 3 - Solution
Parity and greedy zeroing
29. Codeforces 1572B Xor of 3 - Implementation
Check invariant and construct
30. Codeforces 1572B Xor of 3 - Example and Complexity Analysis
Linear construction
31. Codeforces 1638D Big Brush - Problem Statement
CF 1638D - reconstruct painting sequence
32. Codeforces 1638D Big Brush - Why Naive Fails
Forward simulation has too many choices
33. Codeforces 1638D Big Brush - Solution
Reverse greedy with queue
34. Codeforces 1638D Big Brush - Implementation
BFS-style reverse simulation
35. Codeforces 1638D Big Brush - Example and Complexity Analysis
Linear in grid size
36. Quiz: Constructive Algorithms
Test your understanding
37. Section Recap
What you've learned