Constructive Algorithms

Quick Revisit

• USE WHEN: Problem says "construct", "find any", or "print a valid" object satisfying constraints
• INVARIANT: Each construction step preserves all constraints; verify the output matches the spec
• TIME: Usually O(n) or O(n log n) | SPACE: O(n)
• CLASSIC BUG: Forgetting to handle impossibility cases ("NO" / "-1") before attempting construction
• PRACTICE: Practice Ladder

When a problem says "construct", "find any", or "print a valid" answer, you are not searching for a needle in a haystack—you are building the needle. The core skill is recognizing that most constructions follow a simple, provable pattern: a parity split, a greedy placement, or an inductive extension from a small base case.

Difficulty: Intermediate | Prerequisites: Greedy | CF Rating Range: 1200–1900 | Contest Frequency: Common—appears in most Codeforces rounds

---

Contents

• Intuition
• C++ STL Reference
• Implementation
• Operations Reference
• Problem Patterns & Tricks
• Advanced Construction Patterns
• Reading Constraints for Construction Hints
• Contest Cheat Sheet
• Gotchas & Debugging
• When NOT to Use This
• If I Had 5 Minutes
• Pattern Fingerprint
• Rating Progression
• Before You Code Checklist
• What Would You Do If...?
• The Mistake That Teaches
• Debug This
• Self-Test
• Practice Problems
• Further Reading
• What to Solve Next

---

Intuition

Construct a permutation of $[1..n]$ such that no two adjacent elements differ by exactly 1. For $n=5$, find any valid permutation or report impossible.

Your first instinct: try stuff.

  Attempt 1:  [1, 2, 3, 4, 5]  -->  |2-1|=1  FAIL at position 1-2
  Attempt 2:  [1, 3, 2, 4, 5]  -->  |3-2|=1  FAIL at position 2-3
  Attempt 3:  [2, 4, 1, 3, 5]  -->  |5-3|=2  ok... check all:
              |4-2|=2, |1-4|=3, |3-1|=2, |5-3|=2  --> VALID!

You got lucky. Now try $n=8$. Or $n=200000$. Trial-and-error collapses. Backtracking takes $O(n!)$ in the worst case—for $n=20$ that is already $\approx 2.4\times {10}^{18}$.

There is no way to guess your way through $2\times {10}^5$ elements. We need a pattern that works for every $n$.

Most constructive problems have a simple pattern hiding behind the constraints—look for parity splits, greedy placement, or build from a known base case and extend.

Analogy: assembling IKEA furniture. You do not randomly try screws—you follow a pattern (step 1: frame, step 2: shelves, step 3: doors). Each step makes progress and never breaks what you already built. A constructive algorithm is the same: identify a systematic rule, prove it preserves constraints, and apply it for every $n$.

For the permutation problem above, the pattern is a parity split: place all odd numbers first, then all even numbers. Adjacent odds differ by 2, adjacent evens differ by 2, and the gap between the last odd and first even is large enough. This works for every $n\ge 4$ (and $n\le 3$ needs a separate check).

Visual Walkthrough

Same permutation problem, $n=7$. Rule: place odds first, then evens.

  Step 1: Collect odds:   [1, 3, 5, 7]
  Step 2: Collect evens:  [2, 4, 6]
  Step 3: Concatenate:    [1, 3, 5, 7, 2, 4, 6]

  Verify adjacent differences:
    |3-1| = 2  ok
    |5-3| = 2  ok
    |7-5| = 2  ok
    |2-7| = 5  ok    <-- junction between odds and evens
    |4-2| = 2  ok
    |6-4| = 2  ok

  Result: ALL differences >= 2.  VALID.

Now generalize. For any $n\ge 4$:

  +-------------------------------------------------------+
  |  Odds block:   1, 3, 5, ..., (last odd <= n)          |
  |  Evens block:  2, 4, 6, ..., (last even <= n)         |
  |                                                       |
  |  Within each block: adjacent diff = 2     (always ok) |
  |  At junction:  first_even - last_odd                   |
  |    n=4: [1,3,2,4]  junction |2-3|=1  FAIL!            |
  |    n=5: [1,3,5,2,4] junction |2-5|=3  ok              |
  |    n=6: [1,3,5,2,4,6] junction |2-5|=3  ok            |
  +-------------------------------------------------------+

Wait—$n=4$ fails with this exact layout. Fix: swap order to evens-first or rearrange. For $n=4$: $[2,4,1,3]$ works (junction $|1-4|=3$). General fix: if $n$ is even and $n\ge 4$, start with evens; if odd, start with odds. Actually, for $n\ge 5$ both orders work. For $n=4$: evens first. For $n\le 3$: only $n=1$ trivially works; $n=2,3$ are impossible (not enough room to avoid diff = 1).

  n=1: [1]                         VALID (no adjacent pair)
  n=2: [1,2] or [2,1]             |diff|=1  IMPOSSIBLE
  n=3: all 6 permutations fail    IMPOSSIBLE
  n=4: [2, 4, 1, 3]               VALID
  n=5: [1, 3, 5, 2, 4]            VALID
  n=8: [2, 4, 6, 8, 1, 3, 5, 7]   VALID

Brute force for $n=8$: checking $8!=40320$ permutations. Parity split: $O(n)$.

The Invariant

+------------------------------------------------------------------+
| INVARIANT: After placing k elements, every adjacent pair in the  |
| partial sequence satisfies the constraint. The remaining          |
| elements can always be appended without violating it.             |
| Construction is complete when all n elements are placed.          |
+------------------------------------------------------------------+

Why this holds for the parity-split approach: within each block (odds or evens), consecutive elements differ by exactly 2, which satisfies $|\text{diff}|\ge 2$. At the junction between blocks (last element of first block, first element of second block), the difference is $\ge 3$ for $n\ge 5$. We handle $n\le 4$ as special cases.

Look at Step 3 above for $n=7$: when we append the evens block after the odds block, the invariant could break only at the junction—and $|2-7|=5$ preserves it.

  PARITY-SPLIT CONSTRUCTION AT A GLANCE
  ======================================

  n = 10:  [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]

  Differences:
  |4-2| |6-4| |8-6| |10-8| |1-10| |3-1| |5-3| |7-5| |9-7|
    2     2     2      2      9      2     2     2     2
    OK     OK     OK      OK      OK      OK     OK     OK     OK

  All >= 2. The junction |1 - 10| = 9 is always the largest gap.

General constructive invariant template:

  +------------------------------------------------------------------+
  | CONSTRUCTIVE INVARIANT                                           |
  |                                                                  |
  | 1. Define what "valid partial solution of size k" means.         |
  | 2. Show the base case (k=0 or k=1) is trivially valid.          |
  | 3. Show that adding element k+1 (chosen by your rule)            |
  |    preserves validity.                                           |
  | 4. Show termination: every element is eventually placed.         |
  +------------------------------------------------------------------+

What the Code Won't Teach You

A constructive solution is almost always short—20 lines of simple loops and conditionals. That brevity is deceptive. The code doesn't show the 30 minutes of scratch work that produced it: the small-case enumeration, the pattern recognition, the invariant discovery, and the moment the construction clicked into place.

  THE INVISIBLE WORK BEHIND CONSTRUCTIVE SOLUTIONS
  =================================================

  What you see (the code):          What actually happened:

  for i in 0..n:                    n=1: [1]         trivial
    if i % 2 == 0:                  n=2: impossible   (checked all 2!)
      ans[i] = evens[j++]           n=3: impossible   (checked all 6)
    else:                           n=4: [2,4,1,3]    pattern found!
      ans[i] = odds[k++]           n=5: [2,4,1,3,5]  extends!
                                    n=6: [2,4,6,1,3,5] generalizes!
  ~5 lines of code                  ^--- 20 min of hand-exploration

The construction follows from the invariant, not from intuition. When you're stuck, don't stare at the problem hoping for insight. Instead: (1) try $n=1..5$ by hand, (2) identify what all valid solutions share (the invariant), (3) build something that trivially satisfies that invariant. The construction usually writes itself after step 2.

"NO" answers have patterns too. Impossibility conditions are almost always clean—a parity mismatch, a count that doesn't divide evenly, or a small case ($n\le 3$) that fails exhaustively. If your impossibility check has five nested conditions, it is probably wrong.

With those lessons in mind, here is how to spot constructive problems during a contest.

When to Reach for This

Trigger phrases in problem statements:

• "construct a permutation / array / sequence such that..."
• "find any valid ..." or "print any ..."
• "output YES/NO, and if YES, print the answer"
• "determine if it is possible, and if so, construct..."
• "build a graph / tree with given properties"

Counter-examples—problems that look constructive but are not:

Problem type	Why it differs	Correct approach
"count the number of valid permutations"	Counting, not constructing	Combinatorics or DP
"find the lexicographically smallest valid array"	Optimization over constructions	Greedy with careful ordering, not free-form construction
"minimize cost to make the array valid"	Optimization objective	DP or greedy on cost, not pure construction

If the problem says "find any"—you have freedom. If it says "find the best" or "count"—it is a different technique.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
iota(first, last, val)	<numeric>	Fill range with val, val+1, val+2, ...	$O(n)$
swap(a, b)	<utility>	Swap two values	$O(1)$
reverse(first, last)	<algorithm>	Reverse a range	$O(n)$
rotate(first, mid, last)	<algorithm>	Rotate range so mid becomes first	$O(n)$
next_permutation(first, last)	<algorithm>	Next lexicographic permutation (brute-force)	$O(n)$
fill(first, last, val)	<algorithm>	Fill range with a single value	$O(n)$
set<T> / multiset<T>	<set>	Track available elements for placement	$O(\log n)$ ops
deque<T>	<deque>	Build sequence from both ends	$O(1)$ push front/back
vector<bool> / bitset<N>	<vector> / <bitset>	Track used elements	$O(1)$ per access
partition(first, last, pred)	<algorithm>	Split range by predicate (odds/evens)	$O(n)$

---

Implementation (Contest-Ready)

Version 1: Minimal—No-Adjacent-Diff-1 Permutation

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) { cout << 1 << "\n"; return 0; }
    if (n <= 3) { cout << -1 << "\n"; return 0; }

    vector<int> ans;
    for (int i = 2; i <= n; i += 2) ans.push_back(i);
    for (int i = 1; i <= n; i += 2) ans.push_back(i);

    for (int i = 0; i < n; i++)
        cout << ans[i] << " \n"[i == n - 1];
}

Version 2: Explained—Same Problem with Verification

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Base cases: n=1 is trivial; n=2,3 are provably impossible
    // (pigeonhole: too few values to avoid diff=1 everywhere).
    if (n == 1) { cout << 1 << "\n"; return 0; }
    if (n <= 3) { cout << -1 << "\n"; return 0; }

    // Parity split: place all evens first, then all odds.
    // Within each block consecutive elements differ by 2.
    // At the junction (last even, first odd):
    //   last_even = n or n-1 (whichever is even)
    //   first_odd = 1
    //   difference >= n-2 (for n>=4 this is >= 2, but n=4
    //   gives |1 - 4| = 3, safe).
    vector<int> ans;
    ans.reserve(n);

    // Evens: 2, 4, 6, ...
    for (int i = 2; i <= n; i += 2)
        ans.push_back(i);

    // Odds: 1, 3, 5, ...
    for (int i = 1; i <= n; i += 2)
        ans.push_back(i);

    // Verify (debug only -- remove before submission)
    for (int i = 0; i + 1 < n; i++)
        assert(abs(ans[i] - ans[i + 1]) != 1);

    for (int i = 0; i < n; i++)
        cout << ans[i] << " \n"[i == n - 1];

    return 0;
}

---

Operations Reference

Operation	Time	Space
Parity split construction	$O(n)$	$O(n)$
Sort-based construction (e.g., rearrange by key)	$O(n\log n)$	$O(n)$
Greedy placement with set of available elements	$O(n\log n)$	$O(n)$
Small-case brute force + extend	$O(n)$ after base	$O(n)$
Graph-based construction (build edges)	$O(n+m)$	$O(n+m)$
Verify a constructed answer	$O(n)$ to $O(n\log n)$	$O(n)$

Most constructive solutions run in $O(n)$ or $O(n\log n)$. If yours is slower, you have almost certainly missed the pattern—step back and enumerate small cases again.

---

Problem Patterns & Tricks

Parity-Based Construction

Split elements into two groups (odd/even, positive/negative, small/large) and arrange them so the constraint is satisfied within and between groups.

// Construct permutation where adjacent elements have different parity
// and no two adjacent differ by exactly 1.
vector<int> ans;
for (int i = 2; i <= n; i += 2) ans.push_back(i); // evens
for (int i = 1; i <= n; i += 2) ans.push_back(i); // odds

Works when the constraint involves a "gap" between adjacent elements—parity naturally creates gaps of $\ge 2$.

Problems: CF 1381A1, CF 1174B

Greedy Build (Assemble One Element at a Time)

Maintain a partial solution. At each step, pick the element that satisfies the constraint and is "safest" (leaves the most options for future steps). Often uses a set or priority queue.

// Construct permutation with given relative-order constraints.
// Greedy: always place the smallest available valid element.
set<int> avail;
for (int i = 1; i <= n; i++) avail.insert(i);
vector<int> ans;
for (int i = 0; i < n; i++) {
    // find smallest element in avail satisfying current constraint
    auto it = avail.lower_bound(/* constraint-dependent */);
    ans.push_back(*it);
    avail.erase(it);
}

The key insight borrowed from interval scheduling: at each step you have a set of valid choices, and "safest" usually means smallest or largest—whichever preserves the most options for elements placed later.

Problems: CF 1352G, CF 1521B

  GREEDY BUILD: Place elements one at a time
  ===========================================

  Goal: arrange [1..6] so no two adjacent have diff = 1

  Step 1: Place 2        [2]
  Step 2: Place 4        [2, 4]       |4-2|=2 OK
  Step 3: Place 6        [2, 4, 6]    |6-4|=2 OK
  Step 4: Place 1        [2, 4, 6, 1] |1-6|=5 OK  <-- junction
  Step 5: Place 3        [2, 4, 6, 1, 3] |3-1|=2 OK
  Step 6: Place 5        [2, 4, 6, 1, 3, 5] |5-3|=2 OK

  +---+---+---+---+---+---+
  | 2 | 4 | 6 | 1 | 3 | 5 |
  +---+---+---+---+---+---+
  |<- evens ->|<-- odds -->|
               ^
               junction: always safe when n >= 4

Small Case Then Extend

Solve for small $n$ by hand (or brute force), then show how to extend a solution of size $k$ to size $k+1$ or $k+2$. Inductive construction.

// Example: construct array of size n with some property.
// Base: n=1 -> [1].
// Extend: given valid array of size k, insert k+1 at position p
// where the constraint still holds.
vector<int> ans = {1};
for (int val = 2; val <= n; val++) {
    // find valid insertion position for val
    int pos = /* ... */;
    ans.insert(ans.begin() + pos, val);
}

This is especially common in problems where the constraint is "local" (depends only on neighbors). Inserting a new element only affects its two neighbors, so you just need to find a safe spot.

Problems: CF 1352D, CF 1554B

Graph-Based Construction

Build a graph (tree, matching, coloring) satisfying degree/distance/connectivity constraints. Typical approach: start from a spanning structure (star, path, chain) and add edges.

// Construct a tree on n nodes with exactly k leaves.
// Strategy: build a path of (n-k+1) nodes (2 leaves),
// then attach remaining (k-1) leaves to internal nodes.
vector<pair<int,int>> edges;
// Path: 1 - 2 - 3 - ... - (n-k+1)
for (int i = 1; i <= n - k; i++)
    edges.push_back({i, i + 1});
// Attach remaining nodes as leaves to node 2 (or any internal node)
for (int i = n - k + 2; i <= n; i++)
    edges.push_back({2, i});

Problems: CF 1041E, CF 1033C

Reverse Engineering (Work Backwards)

Instead of building the answer from scratch, start from the target and undo operations. If the problem says "apply operations to reach state X", sometimes it is easier to start at X and reverse.

// Problem: given final array, find the sequence of operations.
// Reverse: undo operations from the end state.
vector<int> ops;
while (!is_initial_state(a)) {
    // find and reverse the last operation applied
    int op = find_reverse_op(a);
    apply_reverse(a, op);
    ops.push_back(op);
}
reverse(ops.begin(), ops.end());

Classic example: given a sequence of pops from a stack, reconstruct the push order. Work backwards: the last pop was the last push.

Problems: CF 1530C, CF 1017B

  REVERSE ENGINEERING: Work backwards from the answer
  ===================================================

  Problem: construct array where prefix sums are all distinct

  Target:  prefix sums = {s0, s1, s2, s3, s4}  (all distinct)

       s0    s1    s2    s3    s4
       |     |     |     |     |
       v     v     v     v     v
  a = [a0,   a1,   a2,   a3,   a4]
       |     |     |     |     |
       +---->+ a1  = s1 - s0
             +---->+ a2  = s2 - s1
                   +---->+ a3  = s3 - s2
                         +---->+ a4  = s4 - s3

  Choose s_i = i*(i+1)/2: {0, 1, 3, 6, 10}
  Then a = [0, 1, 2, 3, 4]  -- trivially works!

Checkerboard / Alternating Placement

For grid or sequence problems where "no two adjacent share property X", use a checkerboard pattern or alternation.

// Fill n x m grid so no two adjacent cells have the same value.
// Use (i+j) % 2 to alternate.
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        grid[i][j] = (i + j) % 2;

When elements are weighted, sort by weight and place the largest values on one color of the checkerboard.

Problems: CF 1353C, CF 1385C

---

Advanced Construction Patterns

The patterns above cover the most common shapes. The three complete, compilable examples below tackle archetypes that show up frequently at CF 1500–2100 and demand more careful implementation—each one illustrating a distinct construction mindset.

Pattern A: Swap-to-Front Construction

Problem: Given an array of $n$ integers, make it non-decreasing using the minimum number of swaps. Output the swap sequence as pairs $(i,j)$.

Idea: Selection sort is optimal for minimum-swap sorting: find the position of the value that belongs at index $i$, swap it there. Each swap places at least one element in its final position, so at most $n-1$ swaps are needed. This is a classic "construct the operation sequence" problem (see also Reverse Engineering).

  SWAP-TO-FRONT CONSTRUCTION
  ===========================

  Array: [4, 3, 1, 2]       Target: [1, 2, 3, 4]

  Step 1: value 1 is at idx 2  -->  swap(0, 2)  -->  [1, 3, 4, 2]
  Step 2: value 2 is at idx 3  -->  swap(1, 3)  -->  [1, 2, 4, 3]
  Step 3: value 3 is at idx 3  -->  swap(2, 3)  -->  [1, 2, 3, 4]

  3 swaps, each placing one element in its correct position.
  Worst case: n-1 swaps (reverse-sorted input).

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Build sorted target and map each value to its target index.
    // For duplicates, use stable ordering so equal elements keep
    // relative order (avoids unnecessary swaps).
    vector<int> sorted_a(a);
    sort(sorted_a.begin(), sorted_a.end());

    // pos[v] = current index of value v (handle duplicates via queue)
    map<int, queue<int>> pos;
    for (int i = 0; i < n; i++) pos[a[i]].push(i);

    // target_at[i] = which original-index element should end up at i
    vector<int> target(n);
    for (int i = 0; i < n; i++) {
        target[i] = pos[sorted_a[i]].front();
        pos[sorted_a[i]].pop();
    }

    // Selection-sort: for each position, swap the correct element in
    vector<pair<int,int>> swaps;
    vector<int> where(n); // where[i] = current position of element
    iota(where.begin(), where.end(), 0);
    vector<int> who(n);   // who[j] = which element is at position j
    iota(who.begin(), who.end(), 0);

    for (int i = 0; i < n; i++) {
        int need = target[i];       // original index of element for pos i
        int cur = where[need];      // its current position
        if (cur != i) {
            swaps.push_back({i, cur});
            int other = who[i];
            // perform swap in tracking arrays
            swap(who[i], who[cur]);
            swap(where[need], where[other]);
        }
    }

    cout << swaps.size() << "\n";
    for (auto [x, y] : swaps)
        cout << x << " " << y << "\n";

    return 0;
}

Complexity: $O(n\log n)$ for sorting, $O(n)$ for the swap loop.

Pattern B: Degree-Sequence Graph Construction (Erdős-Gallai)

Problem: Given a degree sequence $d_1,d_2,\dots ,d_n$, construct a simple undirected graph realizing that sequence, or report it is impossible.

Theory: The Erdős-Gallai theorem says a non-increasing sequence $d_1\ge d_2\ge \cdots \ge d_n$ is graphical (realizable as a simple graph) if and only if:

1. $\sum d_i$ is even, and
2. for every $k=1,\dots ,n$: $\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{i=k+1}^{n}min(d_i,k)$.

Construction: Use the greedy Hakimi algorithm—repeatedly connect the highest-degree vertex to the next-highest-degree vertices and reduce degrees. This connects to graph-based construction and graph representation concepts from Graph Representation.

  HAKIMI CONSTRUCTION
  ====================

  Degrees: [3, 3, 2, 2, 2]    sum=12 (even) OK

  Sort desc: [3, 3, 2, 2, 2]   (vertices: v1..v5)

  Round 1: v1 has deg 3 -> connect to v2, v3, v4
           Remaining degrees: [-, 2, 1, 1, 2]
           Edges so far: (1,2) (1,3) (1,4)

  Sort desc: [2, 2, 1, 1]  (vertices: v2, v5, v3, v4)

  Round 2: v2 has deg 2 -> connect to v5, v3
           Remaining: [-, 1, 0, 1]
           Edges so far: + (2,5) (2,3)

  Sort desc: [1, 1]  (vertices: v4, v5 with remaining deg 1 each)

  Round 3: v4 has deg 1 -> connect to v5
           Edge: (4,5)     Done!

  Final edges: (1,2) (1,3) (1,4) (2,5) (2,3) (4,5)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> d(n);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
        total += d[i];
    }

    // Erdos-Gallai check 1: sum must be even
    if (total % 2 != 0) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    // Erdos-Gallai check 2: inequality for each prefix
    vector<pair<int,int>> dv(n);
    for (int i = 0; i < n; i++) dv[i] = {d[i], i};
    sort(dv.rbegin(), dv.rend());

    vector<int> sd(n);
    for (int i = 0; i < n; i++) sd[i] = dv[i].first;

    // Prefix sums of sorted degrees
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + sd[i];

    bool graphical = true;
    for (int k = 1; k <= n && graphical; k++) {
        long long lhs = prefix[k];
        long long rhs = (long long)k * (k - 1);
        for (int i = k; i < n; i++)
            rhs += min(sd[i], k);
        if (lhs > rhs) graphical = false;
    }

    if (!graphical) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    // Hakimi greedy construction
    // Use a priority queue of (remaining_degree, vertex_id)
    vector<pair<int,int>> edges;
    priority_queue<pair<int,int>> pq;
    for (int i = 0; i < n; i++)
        if (d[i] > 0) pq.push({d[i], i});

    while (!pq.empty()) {
        auto [deg, u] = pq.top(); pq.pop();
        if (deg == 0) continue;

        // Connect u to the next 'deg' highest-degree vertices
        vector<pair<int,int>> neighbors;
        for (int i = 0; i < deg; i++) {
            if (pq.empty()) {
                // should not happen after Erdos-Gallai check
                cout << "IMPOSSIBLE\n";
                return 0;
            }
            neighbors.push_back(pq.top());
            pq.pop();
        }
        for (auto& [nd, v] : neighbors) {
            edges.push_back({u + 1, v + 1}); // 1-indexed output
            nd--;
            if (nd > 0) pq.push({nd, v});
        }
    }

    cout << edges.size() << "\n";
    for (auto [u, v] : edges)
        cout << u << " " << v << "\n";

    return 0;
}

Complexity: $O(n^2\log n)$ in the worst case (each round pops up to $n$ elements). For contest constraints ($n\le {10}^3$) this is fine. For $n\le {10}^5$ a more advanced implementation using sorted arrays is needed.

Pattern C: Balanced Parentheses with Max Nesting Depth $k$

Problem: Given $n$ pairs of parentheses and a maximum nesting depth $k$, construct a balanced parentheses string where the deepest nesting is exactly $k$, or report impossible.

Key observations:

• A balanced string of $n$ pairs always has nesting depth between 1 and $n$.
• Impossible when $k<1$ or $k>n$.
• Strategy: build a prefix of $k$ opening parens (to reach depth $k$), close some, then distribute remaining pairs at depth $\le k$.

  BALANCED PARENS WITH DEPTH k
  =============================

  n=5, k=3:

  Strategy: open k parens, then alternate open/close at depth k.

  Build:  ((( ))  (( ))  ()
          ^^^     ^^     ^
          depth3  depth2 depth1

  Simpler approach: open k parens, close all k, then append
  (n-k) pairs at depth 1:

  ((()))()()       depth=3, pairs=5  OK

  n=6, k=2:

  (())(())(())     depth=2, pairs=6  OK

  Or: (()) repeated 3 times.
  General: repeat "(()...)" with k-deep nesting, enough times.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    // Impossible cases
    if (k < 1 || k > n) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    // Construction: we need exactly n pairs with max depth = k.
    // Approach: build groups. Each group is a balanced substring
    // with depth exactly min(remaining_pairs, k_target).
    //
    // Simplest method: one deep group of depth k, then (n-k)
    // groups of depth 1.
    //   Group 1: "(((...)))" with k pairs  -> depth k
    //   Groups 2..n-k+1: "()" each         -> depth 1
    //
    // Max depth = k. Total pairs = k + (n-k) = n.

    string result;
    result.reserve(2 * n);

    // Group 1: k nested pairs
    for (int i = 0; i < k; i++) result += '(';
    for (int i = 0; i < k; i++) result += ')';

    // Remaining (n-k) pairs at depth 1
    for (int i = 0; i < n - k; i++) result += "()";

    // Verify depth
    int depth = 0, max_depth = 0;
    for (char c : result) {
        depth += (c == '(') ? 1 : -1;
        max_depth = max(max_depth, depth);
    }
    assert(max_depth == k);
    assert(depth == 0);
    assert((int)result.size() == 2 * n);

    cout << result << "\n";
    return 0;
}

Complexity: $O(n)$ time and space. The construction is trivially correct by inspection—the first group nests to depth $k$, and all subsequent groups nest to depth 1, so the overall max depth is $k$.

---

Reading Constraints for Construction Hints

Constructive problems hide enormous clues in their constraints—if you learn to read them before touching the construction, the solution shape often reveals itself. This is one of the highest-leverage skills at CF 1400+, and it pairs directly with the general approach in How to Solve Problems.

The Constraint Decoder

  CONSTRAINT --> CONSTRUCTION STRATEGY
  ======================================

  "print any valid permutation"
  +-----------------------------------------+
  | n <= 10^5                               |
  | --> O(n) or O(n log n) construction     |
  | --> Look for: parity split, greedy      |
  |     placement, sort-and-interleave      |
  +-----------------------------------------+

  "if multiple answers exist, print any"
  +-----------------------------------------+
  | --> You have FREEDOM -- exploit it!     |
  | --> Simplest construction wins          |
  | --> Don't optimize what doesn't need it |
  +-----------------------------------------+

  "sum of n over all test cases <= 2*10^5"
  +-----------------------------------------+
  | --> Per-test O(n log n) is fine         |
  | --> Total work is bounded, not per-test |
  | --> Don't over-optimize individual tests|
  +-----------------------------------------+

  "it can be proven that the answer always exists"
  +-----------------------------------------+
  | --> Skip impossibility checking!        |
  | --> Focus purely on construction        |
  | --> The pattern is probably universal   |
  | --> Hints: the answer is always simple  |
  +-----------------------------------------+

  "1 <= k <= n"  (extra parameter)
  +-----------------------------------------+
  | --> k often controls a split point      |
  | --> Try: first k elements one way,      |
  |     remaining (n-k) another way         |
  +-----------------------------------------+

  "the answer is a permutation of 1..n"
  +-----------------------------------------+
  | --> Every value used exactly once       |
  | --> Swap-based construction often works |
  | --> Track what's placed with bool array |
  +-----------------------------------------+

Constraint-to-Technique Mapping

  +------------------+-------------------+-----------------------------+
  | Constraint Clue  | Expected Approach | Technique Family            |
  +------------------+-------------------+-----------------------------+
  | n <= 20          | O(2^n) or O(n!)   | Brute force / bitmask       |
  | n <= 10^3        | O(n^2)            | Nested loop construction    |
  | n <= 10^5        | O(n log n)        | Sort + greedy / set-based   |
  | n <= 10^6        | O(n)              | Parity split / direct build |
  | "print any"      | Freedom           | Simplest valid pattern      |
  | "always exists"  | No NO case        | Universal construction      |
  | "YES/NO + answer"| Two phases        | Check + construct           |
  | parity in input  | Parity split      | Odds/evens separation       |
  | graph + degrees  | Erdos-Gallai      | Hakimi greedy               |
  | tree + property  | Root + DFS build  | Inductive tree construction |
  +------------------+-------------------+-----------------------------+
         |
         v
     Read constraints FIRST, code SECOND.

Worked Example: Decoding a Problem Statement

"Given $n$ ($1\le n\le 2\times {10}^5$), construct a permutation $p_1,p_2,\dots ,p_n$ such that $|p_i-i|\ge 2$ for all $i$, or report that it is impossible. If there are multiple valid answers, print any."

Decoding:

1. $n\le 2\times {10}^5$ → $O(n)$ or $O(n\log n)$ construction.
2. "print any" → we have freedom, don't try to optimize.
3. "or report impossible" → there exist some $n$ where it fails.
4. "$|p_i-i|\ge 2$" → each element must be far from its index.

Scratch work: $n=1$: $p_1=1$, $|1-1|=0<2$. Impossible. $n=2$: $[2,1]$, $|2-1|=1<2$. Impossible. $n=3$: all 6 perms fail. $n=4$: $[3,4,1,2]$ → diffs $=[2,2,2,2]$. Works! $n=5$: $[3,4,5,1,2]$ → diffs $=[2,2,2,3,3]$. Works!

Pattern: shift by 2 positions, wrapping around. This is a rotate-based construction—connect back to the C++ STL Reference above.

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|  CONSTRUCTIVE ALGORITHMS CHEAT SHEET                         |
+--------------------------------------------------------------+
|  WHEN TO USE:                                                |
|  - "construct / find any / print a valid"                    |
|  - "YES/NO + output the answer"                              |
|  - freedom to choose ANY valid answer                        |
+--------------------------------------------------------------+
|  RECIPE:                                                     |
|  1. Check small cases (n=1,2,3) for impossibility            |
|  2. Look for a pattern: parity split? alternation?           |
|  3. Prove the pattern works (invariant on partial solution)  |
|  4. Handle edge cases separately                             |
+--------------------------------------------------------------+
|  KEY PATTERNS:                                               |
|  - Parity split    -> separate odds/evens, big/small         |
|  - Greedy build    -> set of available, pick safest           |
|  - Extend from base -> solve small, grow inductively         |
|  - Work backwards  -> reverse the operations                 |
|  - Checkerboard    -> (i+j)%2 for grids                      |
+--------------------------------------------------------------+
|  COMPLEXITY: usually O(n) or O(n log n)                      |
|  SPACE:      O(n) for the answer array                       |
+--------------------------------------------------------------+
|  DANGER:                                                     |
|  - Forgetting impossible cases (output -1 or NO)             |
|  - Off-by-one at block junctions                             |
|  - Confusing "find any" with "find optimal"                  |
+--------------------------------------------------------------+

---

Gotchas & Debugging

Forgetting Impossibility Cases

Many constructive problems have values of $n$ (or constraint combos) where no valid answer exists. Always check small cases first. If $n\le 3$ is impossible, hard-code it. If the problem has parity constraints, check if the input parity is consistent.

// Always handle impossible cases FIRST
if (n <= 3 && n != 1) { cout << -1 << "\n"; return 0; }

Off-By-One at Block Junctions

When concatenating two constructed blocks (e.g., odds then evens), the constraint can fail at the boundary. Always verify the junction element explicitly.

// After building ans[], verify the junction
int mid = evens.size(); // index where odds start
assert(abs(ans[mid] - ans[mid - 1]) != 1); // check junction

Not Verifying the Answer

Constructive problems are uniquely suited to self-verification—you built the answer, so check it. Add an $O(n)$ verification loop before submission. Remove it only if TLE is a concern.

// Verify: O(n) check after construction
for (int i = 0; i + 1 < n; i++) {
    assert(/* constraint between ans[i] and ans[i+1] */);
}

Assuming the Pattern Works Without Proof

"It passed the examples" is not a proof. Constructive solutions are especially prone to subtle failures at boundary values ($n=4$, $n=1$, even $n$ vs odd $n$). Stress test against brute force for $n\le 10$:

// Stress test for constructive problems
for (int n = 1; n <= 12; n++) {
    auto ans = construct(n);
    if (ans.empty()) { cout << n << ": impossible\n"; continue; }
    assert(verify(ans)); // check every constraint
}

Printing Format Errors

Constructive problems often have strict output format: "print n space-separated integers" or "print YES/NO on the first line, then the answer." Missing a newline or printing an extra space can cause WA on strict judges.

// Safe output pattern
cout << "YES\n";
for (int i = 0; i < n; i++)
    cout << ans[i] << " \n"[i == n - 1];

Confusing Permutation vs Array

"Construct an array" allows repeated values. "Construct a permutation" means each value $1..n$ exactly once. Using a value twice in a permutation is an instant WA. Track used values with a boolean array.

vector<bool> used(n + 1, false);
for (int x : ans) {
    assert(!used[x]); // each value used exactly once
    used[x] = true;
}

Integer Overflow in Constraint Check

If the constraint involves sums or products (e.g., "construct array where prefix sums are all positive"), intermediate values can overflow int. Use long long for sums.

Mental Traps

"My construction handles all the examples, so it must be correct." Constructive solutions are uniquely prone to this trap. The examples are chosen to illustrate the problem, not to break your construction. An adversarial test case with all-same elements, maximum n, or alternating parities will expose gaps that examples never test.

  THE EXAMPLE-PASSING TRAP
  ========================

  Your construction:  [evens, then odds]
  Examples:           n=4 OK  n=6 OK  n=8 OK
  Adversarial:        n=3 X  (you forgot small cases)

  +----+---+---+----+---+----+---+----+
  | OK | ? | X | OK | ? | OK | ? | OK |  <-- examples only test OK
  +----+---+---+----+---+----+---+----+
     1   2   3    4   5    6   7    8
                 ^
                 |  hidden failure at n=3

"The construction needs to be clever." The correct construction is almost always embarrassingly simple. If yours has 10 cases and special handling for odd/even/prime n, step back—you're likely overcomplicating it. The simplest constructions are usually: sort, split by parity, pair first/last, or reverse a segment.

"I should prove it rigorously before coding." In contest, a hand-verified pattern over n=1..6 plus a one-sentence argument ("evens differ by 2, odds differ by 2, junction differs by >=3") is enough. Save formal proofs for upsolving.

---

When NOT to Use This

Not every "build something" problem is a constructive algorithm problem. Reaching for construction patterns when the problem is really optimization or counting wastes time and produces wrong answers—the two failure modes are hard to debug once you are already 30 minutes into a flawed approach.

Don't use constructive techniques when:

Situation	Why not	Use instead
"Find the minimum cost to make the array valid"	Optimization, not free construction	DP or greedy on cost (Greedy)
"Count the number of valid permutations"	Counting, not building	Combinatorics / DP (DP chapter)
"Find the lexicographically smallest valid array"	Constrained optimization	Greedy with careful tie-breaking
"Given a construction, verify it is valid"	Just checking, not building	Direct simulation
"Find all valid constructions"	Enumeration, not single answer	Backtracking / Complete Search

The litmus test: If the problem says "find any"—constructive. If it says "find the best / smallest / count"—probably not constructive.

One more thing worth burning in: the correct construction for most constructive problems is embarrassingly simple—5–10 lines. If yours has 50 lines of case analysis, you missed the pattern. Step back, try small cases again, and look for what all valid solutions share. The construction follows from the invariant, not the other way around.

---

If I Had 5 Minutes

Five steps for when the clock is ticking:

1. Try $n=1,2,3,4,5$ by hand. Most impossibilities and patterns reveal themselves by $n=5$.
2. Look for parity. If the constraint involves "adjacent" or "difference," split odds and evens.
3. Check if "always exists." If the problem guarantees an answer, skip impossibility logic entirely.
4. Build and verify. Write the construction, then add a 3-line assert loop. If it fails, your pattern is wrong.
5. Don't be clever. The simplest answer (sort, reverse, rotate, split) is almost always the right one.

Real-Life Analogy: Constructive algorithms are like packing a suitcase—you don't randomly throw in clothes and hope they fit. You fold shirts in a stack, roll pants along the sides, stuff socks in shoes. Simple rules, applied systematically, always work.

---

Pattern Fingerprint

Quick lookup: given what you see in the problem, which pattern to try first.

+-------------------------------+-----------------------------------+
| What You See in the Problem   | Try This Pattern First            |
+-------------------------------+-----------------------------------+
| "no two adjacent differ by 1" | Parity split (Pattern 1)          |
| "construct a permutation"     | Parity split or swap-based (A)    |
| "build a graph with degrees"  | Erdos-Gallai + Hakimi (B)         |
| "balanced parentheses"        | Nesting-depth construction (C)    |
| "undo operations to reach X"  | Reverse engineering (Pattern 5)   |
| "fill a grid with property"   | Checkerboard (Pattern 6)          |
| "tree with k leaves"          | Path + attach leaves (Pattern 4)  |
| "extend solution from small"  | Small case + extend (Pattern 3)   |
| "minimize swaps / operations" | Swap-to-front / selection (A)     |
| "given constraints, print any"| Greedy build (Pattern 2)          |
+-------------------------------+-----------------------------------+

---

Rating Progression

What to expect at each Codeforces rating level:

+----------------------------------------------------------------------+
|  CF 1200  |  "Warm-up" constructions                                 |
|           |  - Parity split, simple rearrangement                    |
|           |  - Impossibility is obvious (small n fails)              |
|           |  - Pattern visible from 2-3 examples                    |
|           |  Example: CF 1352D, CF 1622A                             |
+----------------------------------------------------------------------+
|  CF 1500  |  "Standard" constructions                                |
|           |  - Need to identify the right invariant                  |
|           |  - May require sort + interleave                         |
|           |  - Impossibility check has 1-2 conditions                |
|           |  Example: CF 1554B, CF 1619D                             |
+----------------------------------------------------------------------+
|  CF 1800  |  "Tricky" constructions                                  |
|           |  - Pattern not obvious from small cases alone             |
|           |  - May need graph/tree reasoning                         |
|           |  - Multiple valid approaches, but only simple ones pass  |
|           |  Example: CF 1521B, CF 1029E                             |
+----------------------------------------------------------------------+
|  CF 2100  |  "Expert" constructions                                  |
|           |  - Requires combining 2+ techniques                      |
|           |  - Impossibility is subtle (number theory, parity arg)   |
|           |  - Construction proof is non-trivial                     |
|           |  - Often paired with segment trees or advanced DS        |
|           |  Example: CF 1385E, CF 1404B                             |
+----------------------------------------------------------------------+

---

Before You Code Checklist

Run through these 5 points before writing a single line:

• [ ] Small cases: Have I tried $n=1,2,3,4,5$ by hand?
• [ ] Impossibility: Do I know exactly which inputs are impossible? Is the condition clean (parity, divisibility, small $n$)?
• [ ] Pattern: Can I state the construction rule in one sentence? (e.g., "evens first, then odds")
• [ ] Junction check: If I'm concatenating blocks, have I verified the boundary between them?
• [ ] Freedom: Am I exploiting "print any" freedom, or am I over-constraining myself?

---

What Would You Do If...?

Test your constructive thinking with these scenarios:

Scenario 1: You're asked to construct a permutation of $[1..n]$ where $a_i+a_{n+1-i}=n+1$ for all $i$. You try $n=4$: $[1,4,3,2]$ doesn't work ($1+2=3\ne 5$). $[2,3,4,1]$: $2+1=3\ne 5$. $[4,1,2,3]$: $4+3=7\ne 5$. What now?

Hint: Pair $(i,n+1-i)$. Place value $n+1-i$ at position $i$. Answer: $[n,n-1,\dots ,1]$—just reverse! Sometimes the construction IS the identity. Check: $a_i=n+1-i$, $a_{n+1-i}=i$, sum $=n+1$. OK.

Scenario 2: You need to construct an array of $n$ positive integers with sum $S$ and max element $\le M$. You compute $n\le S$ (since each element $\ge 1$) and $S\le n\cdot M$ (since each element $\le M$). These are necessary. Are they sufficient?

Hint: Yes! Start with all 1's (sum $=n$). Distribute remaining $S-n$ across elements, adding at most $M-1$ to each. Greedy: add $min(M-1,\text{remaining})$ to each element left-to-right.

Scenario 3: The problem says "construct a binary string of length $n$ with exactly $k$ ones such that no two ones are adjacent." You quickly see $k\le \lceil n/2\rceil$ is necessary. How do you construct it?

Hint: Place ones at even indices: positions $0,2,4,\dots$ until $k$ ones placed. This guarantees no two adjacent. Works when $k\le \lceil n/2\rceil$.

---

The Mistake That Teaches

The Debugging Story: "Why Does $n=4$ Keep Failing?"

You're solving the no-adjacent-diff-1 permutation problem. Your code:

vector<int> ans;
for (int i = 1; i <= n; i += 2) ans.push_back(i); // odds first
for (int i = 2; i <= n; i += 2) ans.push_back(i); // then evens

It passes $n=5,6,7,8$ on your local tests. You submit—Wrong Answer on test 3. The test case? $n=4$.

Your output: $[1,3,2,4]$. Check: $|3-2|=1$. Fail at the junction.

You stare at the code. The pattern works for $n\ge 5$ because the last odd is $\ge 5$ and the first even is 2, giving a gap of $\ge 3$. But for $n=4$, the last odd is 3 and the first even is 2—gap of 1.

The fix: Swap the order—evens first, then odds. For $n=4$: $[2,4,1,3]$ → $|4-1|=3$. OK. For $n\ge 5$, both orders work. Add the $n=4$ special case, or just always use evens-first.

Lesson: The junction between blocks is where constructive solutions break. Always check it for the smallest valid $n$, not just large $n$.

Mnemonic Anchor: "Junction Jeopardy"—where your blocks meet is where your bugs hide. Always verify the seam.

---

Debug This

Find the bug in each snippet. All are common mistakes in constructive problems.

Bug 1: Off-by-one in parity split

// Goal: permutation where no adjacent elements differ by 1
// Bug: what happens when n = 4?
vector<int> construct(int n) {
    vector<int> ans;
    for (int i = 1; i <= n; i += 2) ans.push_back(i);
    for (int i = 2; i <= n; i += 2) ans.push_back(i);
    return ans;
}

Answer

For $n=4$: output is $[1,3,2,4]$, and $|3-2|=1$—fails at the junction. Fix: Use evens-first order, or special-case $n=4$.

vector<int> construct(int n) {
    vector<int> ans;
    for (int i = 2; i <= n; i += 2) ans.push_back(i); // evens first!
    for (int i = 1; i <= n; i += 2) ans.push_back(i);
    return ans;
}

Bug 2: Forgetting impossibility check

// Goal: construct degree-sequence graph
// Bug: no validation before construction
void solve() {
    int n; cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++) cin >> d[i];

    // Immediately start Hakimi construction (WRONG!)
    sort(d.rbegin(), d.rend());
    // ... construction code ...
    cout << "YES\n";
}

Answer

Missing Erdős-Gallai check. If $\sum d_i$ is odd or the degree sequence is not graphical, the construction will produce an invalid graph or crash. Fix: Always validate before constructing.

long long total = 0;
for (int x : d) total += x;
if (total % 2 != 0) { cout << "NO\n"; return; }
// + full Erdos-Gallai check

Bug 3: Permutation with duplicates

// Goal: permutation of [1..n] with some property
// Bug: can you spot the duplicate?
vector<int> construct(int n) {
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = (i * 2) % n + 1;
    }
    return ans;
}

Answer

When $n$ is even, this produces duplicates. For $n=4$: indices $0,1,2,3$ give values $1,3,1,3$—not a permutation! The formula $(2i)modn+1$ only produces a permutation when $gcd(2,n)=1$, i.e., $n$ is odd. Fix: Add a used[] check, or use a different formula for even $n$.

vector<bool> used(n + 1, false);
for (int x : ans) {
    assert(!used[x] && "Duplicate in permutation!");
    used[x] = true;
}

Bug 4: Wrong junction check in block construction

// Goal: build array in two blocks with a property at the junction
// Bug: off-by-one in junction verification
vector<int> evens, odds;
for (int i = 2; i <= n; i += 2) evens.push_back(i);
for (int i = 1; i <= n; i += 2) odds.push_back(i);
vector<int> ans = evens;
ans.insert(ans.end(), odds.begin(), odds.end());

// Verify junction (BUGGY)
int mid = evens.size();
if (abs(ans[mid] - ans[mid + 1]) == 1) { // <-- wrong indices!
    cout << -1 << "\n";
    return;
}

Answer

The junction is between ans[mid - 1] (last of evens) and ans[mid] (first of odds), not between ans[mid] and ans[mid + 1]. The latter checks inside the odds block, not the junction. Fix: abs(ans[mid - 1] - ans[mid]) == 1.

---

Self-Test

• [ ] Given a constructive problem, list the first 3 steps you take before writing any code.
• [ ] Write the parity-split construction for "no adjacent elements differ by 1" from memory.
• [ ] Explain why stress-testing against brute force for n <= 10 is especially important for constructive problems.
• [ ] State the typical form of "NO" conditions in constructive problems (give 2 examples).
• [ ] Construct a permutation of 1..8 where a[i] + a[9-i] = 9 for all i. Identify the pattern.
• [ ] Explain why "find any valid" gives you freedom that "find the lexicographically smallest" does not.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Construct a Rectangle	CF 1622A	800	Simple parity check + build
2	Array Coloring	CF 1857B	900	Parity-based construction
3	Permutation	CSES	1100	Classic no-adjacent-diff-1 permutation
4	Yet Another Constructive Problem	CF 1554B	1200	Small case analysis + extend
5	Constructing the Array	CF 1352D	1400	Greedy build with priority queue
6	MEX and Increments	CF 1619D	1600	Greedy construction with stack
7	Nastia and a Good Array	CF 1521B	1600	GCD-based greedy construction
8	Tree with Small Distances	CF 1029E	1700	Graph-based: greedy tree construction
9	Tree Tag	CF 1404B	1900	Tree diameter + constructive argument
10	Constructive Problem	CF 1385E	1900	Complex construction with segment analysis

---

Further Reading

Constructive algorithms trace back to existence proofs in combinatorics—showing that an object exists by explicitly building it. The Erdős-Gallai theorem (1960) and Hakimi's constructive proof (1962) are early examples of turning existence conditions into algorithms, a tradition that now dominates competitive programming.

• CF Blog: How to come up with constructive algorithms—community strategies and worked examples.
• CF Tag: constructive algorithms—full problem list sorted by rating, ideal for targeted practice.
• USACO Guide: Ad Hoc / Constructive—introduction to constructive thinking in contests.
• cp-algorithms.com—reference for graph and number-theory constructions.

Cross-references in this guidebook:

• Greedy—prerequisite; many constructions are greedy at their core.
• Interactive Problems—constructive output with judge interaction.
• STL Quick Reference—containers and algorithms used in constructions.
• How to Solve Problems—general problem-solving framework that applies to reading constraints.
• Complete Search—brute-force alternative when construction is not possible.
• Graph Representation—prerequisite for graph-based constructions (Pattern 4, Pattern B).
• Binary Search—sometimes combined with construction (binary search on the answer, construct to verify).
• Divide and Conquer—recursive constructions often follow D&C structure.
• Practice Ladder—rated constructive problems.

---

What to Solve Next

• Contribution Technique—counting by contribution, a complementary skill.
• Greedy—many constructions are greedy at their core; review the exchange argument.
• Practice Ladder—drill constructive problems by rating.