Constructive

Constructive Algorithms — CF Hallmark

Constructive problems ask you to build something meeting constraints, not just check existence.

---

Core Strategies

1. Start from target and work backwards

Instead of "how to reach goal", ask "what's the final state, and what's the operation before it?"

2. Parity / Modulo constructions

• Build alternating arrays: [0,1,0,1,...] or [i%2, i%3, ...]
• Use (i + j) % 2 for grid coloring

3. Binary representation tricks

• Decompose numbers into powers of 2
• Use bit positions as "buckets"

4. Small cases first, generalize

• Solve for n=1, n=2, n=3 manually → see pattern → generalize

5. Extreme values

• Put all min values first or all max values first
• Fill with 0s or 1s and adjust

6. Permutation constructions

• Reverse sorted: [n, n-1, ..., 1]
• Cyclic shifts: rotate by k
• Adjacent swaps: build by swapping pairs

7. Mex constructions

• To get a specific mex, ensure 0..mex-1 are present, mex is absent
• For mex of subarrays, use prefix/suffix structures

---

Common CF Constructive Problems

Problem Type	Trick
Build array with given sum/AND/XOR	Set most elements to 0 or 1, adjust last element
Permutation with adjacent constraints	Interleave low and high: [1, n, 2, n-1, ...]
Matrix with row/col sums	Greedy fill from top-left, last cell absorbs remainder
String with given character differences	Group same chars, rotate blocks
Graph with degree constraints	Connect highest-degree nodes first (Havel-Hakimi)
Partition into 2 groups with equal sum	Sort descending, greedy assign to smaller sum group
Arrange to avoid condition	If pattern P is bad, try its complement or cyclic shift
Build a tree with given diameter	Make a path of length diameter, attach leaves

○ Mark as completed