Greedy Construction

Constructive Greedy

Here's a pattern that trips people up: some problems ask you to build a valid output, not just compute a number. You figure out the answer formula in 5 minutes, then spend 25 minutes struggling to actually construct a witness. The formula tells you what the answer is. The construction tells the judge how to achieve it.

This lesson covers the construction mindset through five problems, then dives deep into Array-to-Zero — which combines a parity invariant with a priority-queue construction.

Example 1: ABC178F — Contrast

Problem. Two sorted arrays A and B of length $n$, values in $[1, N]$. Rearrange B so that $A[i] \neq B[i]$ for all $i$, or report impossible.

The Greedy Choice: Find the formula first (the answer is often $n - \text{max\_frequency}$ or "only if sum is even"). Then build a witness that achieves it.

When Is It Impossible?

Before building anything, figure out when you're guaranteed to fail. If some value $v$ appears $\text{count}_A(v)$ times in A and $\text{count}_B(v)$ times in B, and $\text{count}_A(v) + \text{count}_B(v) > n$, then by the pigeonhole principle there must be a collision. There are $n$ positions, $v$ occupies $\text{count}_A(v)$ of them in A, and no matter how you rearrange B's $\text{count}_B(v)$ copies of $v$, at least one position must have $A[i] = B[i] = v$.

Impossibility criterion: any value $v$ with $\text{count}_A(v) + \text{count}_B(v) > n$ makes it impossible.

The Wrong Approach

You might try random shuffling and checking. Or you might try a greedy scan that avoids collisions one at a time. Both lead to corner cases that are painful to handle.

Instead of asking "how do I avoid collisions?", ask: "what arrangement maximally separates matching values?"

The Construction

Sort A ascending. Sort B descending.
Now check: does $A[i] = B[i]$ for any $i$?

Sorting A ascending and B descending pushes small values of A to the left and small values of B to the right. Values that match are maximally spread apart. If this arrangement still has collisions, swap to fix them. If swaps can't fix them, the problem is impossible.

Trace

Stare at this table. $A = [1, 1, 2, 3]$, $B = [1, 1, 2, 3]$. After sorting A ascending and B descending:

$i$	$A[i]$	$B[i]$ (desc)	Match?
0	1	3	No
1	1	2	No
2	2	1	No
3	3	1	No

No collisions. Output $B = [3, 2, 1, 1]$.

Now consider $A = [1, 1, 1, 2]$, $B = [1, 1, 1, 3]$. B descending $= [3, 1, 1, 1]$.

$i$	$A[i]$	$B[i]$ (desc)	Match?
0	1	3	No
1	1	1	Yes
2	1	1	Yes
3	2	1	No

Collisions at positions 1 and 2. Can we swap to fix? Try swapping $B[1]$ with $B[3]$: B becomes $[3, 1, 1, 1]$ — not helpful ($B[3]$ is also 1). Check the counts: $\text{count}_A(1) + \text{count}_B(1) = 3 + 3 = 6 > 4$. Impossible.

Verify the impossibility: 3 positions already have $A[i] = 1$. B has 3 copies of 1 to place somewhere. With only 1 non-1 position in A (position 3), at least two copies of B's 1 must land on an $A[i] = 1$ position. Pigeonhole confirms it.

The Code

sort(arrayA.begin(), arrayA.end());

auto descendingCompare = [](int first, int second) {
    return first > second;
};
sort(arrayB.begin(), arrayB.end(), descendingCompare);

for (int i = 0; i < numElements; i++) {
    if (arrayA[i] == arrayB[i]) {
        bool isFixed = false;
        for (int j = i + 1; j < numElements; j++) {
            if (arrayA[i] != arrayB[j] && arrayA[j] != arrayB[i]) {
                swap(arrayB[i], arrayB[j]);
                isFixed = true;
                break;
            }
        }
        if (!isFixed) {
            cout << "No\n";
            return 0;
        }
    }
}
cout << "Yes\n";
for (int i = 0; i < numElements; i++) {
    cout << arrayB[i] << (i == numElements - 1 ? "" : " ");
}
cout << "\n";

Example 2: CF1007A — Reorder the Array

Problem. Reorder an array so that the number of positions where the new value strictly exceeds the original value is maximized. Output that maximum count.

Answer: $n - \text{max\_frequency}$.

Why? Let $f$ be the frequency of the most common element. Those $f$ copies of the same value can never satisfy "strictly greater than themselves." At least $f$ positions will have the same value as the original. The remaining $n - f$ positions can all be satisfied.

What would happen if the max frequency is more than $n/2$? Think about it: if the value 3 appears 4 times in an array of length 6, then after any rearrangement, at least $4 + 4 - 6 = 2$ positions must have 3 in both the original and the rearranged array. The formula still gives $6 - 4 = 2$ positions satisfied.

The construction: Sort the array. Rotate it by the offset equal to the max frequency. This ensures every element is paired with a different (larger) element, except the $f$ copies of the mode.

Trace

Array $= [1, 1, 2, 3, 3, 3]$. Sorted. Max frequency $= 3$ (the value 3). Answer $= 6 - 3 = 3$.

Rotation by 3:

$i$	Original (sorted)	Rotated (offset 3)	Strictly greater?
0	1	3	Yes
1	1	3	Yes
2	2	3	Yes
3	3	1	No
4	3	1	No
5	3	2	No

Exactly 3 positions satisfied. Matches the formula.

Example 3: CF322B — Ciel and Flowers

Problem. $r$ red, $g$ green, $b$ blue flowers. Make bouquets of either 3 same-color flowers or 1 of each color (RGB). Maximize the total number of bouquets.

The Structural Insight: At Most 2 Mixed Bouquets

This is a beautiful example of small-case enumeration. Here's where almost every first implementation breaks — you try to figure out the "right" number of mixed bouquets with some formula. But the claim is: the optimal solution uses at most 2 mixed (RGB) bouquets.

Proof. If we make 3 mixed bouquets, that uses $3R + 3G + 3B = 9$ flowers. We could instead make 1 red bouquet ($3R$) + 1 green bouquet ($3G$) + 1 blue bouquet ($3B$) = 3 bouquets from the same 9 flowers. Same count, no mixed bouquets needed. So 3 mixed bouquets is never strictly better than 0 mixed. The optimal number of mixed bouquets is 0, 1, or 2.

Once you know that, just try all three cases and take the max.

Trace

$r = 7$, $g = 4$, $b = 2$.

Mixed	Remaining $r$	Remaining $g$	Remaining $b$	Same-color	Total
0	7	4	2	$2 + 1 + 0 = 3$	3
1	6	3	1	$2 + 1 + 0 = 3$	4
2	5	2	0	$1 + 0 + 0 = 1$	3

Maximum is 4 (with 1 mixed bouquet).

Predict before reading the code: What's the answer for $r = 9, g = 9, b = 9$? Does mixing help when all counts are divisible by 3?

int maxBouquets = 0;
for (int mixedBouquets = 0; mixedBouquets <= min({redFlowers, greenFlowers, blueFlowers, 2}); mixedBouquets++) {
    int totalBouquets = mixedBouquets +
                        (redFlowers - mixedBouquets) / 3 +
                        (greenFlowers - mixedBouquets) / 3 +
                        (blueFlowers - mixedBouquets) / 3;
    maxBouquets = max(maxBouquets, totalBouquets);
}
cout << maxBouquets << "\n";

Example 4: ABC046D — AtCoDeer and Rock-Paper

Problem. N-turn RPS game. You play Rock (g) or Paper (p). Constraint: at all times, the number of Papers played so far must not exceed the number of Rocks. Opponent's moves are known. Maximize your score (#wins - #losses).

The Greedy Construction

Instead of asking "which turns should I play Paper?", ask: "does it matter which opponent move I play Paper against?"

Let's work through the scoring: - Opponent plays 'p' (paper): your Rock loses ($-1$), your Paper ties ($0$) - Opponent plays 'g' (rock): your Paper wins ($+1$), your Rock ties ($0$)

In both cases, Paper is better or equal to Rock. So the greedy is: always play Paper when the constraint allows, regardless of opponent's move.

But there's a subtlety worth thinking through. If you greedily play Paper against 'p' (gaining $0$ vs $-1$ = benefit of $+1$), you consume a "Paper credit" that could have been used against 'g' for ($+1$ vs $0$ = benefit of $+1$). Equal benefit! So the order doesn't matter — just play Paper whenever the constraint allows.

int rockCount = 0, paperCount = 0, maxScore = 0;
for (char opponentMove : opponentMoves) {
    if (paperCount < rockCount) {
        paperCount++;
        maxScore += (opponentMove == 'g') ? 1 : 0;
    } else {
        rockCount++;
        maxScore += (opponentMove == 'p') ? -1 : 0;
    }
}

Challenge: What if the constraint were reversed (rocks $\leq$ papers at all times)? How does the code change, and does it affect the final score?

Example 5: CF979B — Treasure Hunt

Problem. Three players, each with a string of length $n$ (characters from 'a'-'z'). Each turn, everyone must change exactly one character to a different character. After $t$ turns, beauty = max frequency of any character. Determine who has the highest beauty.

Structural Insight: Parity and Saturation

Here's something that takes a while to click. For a string of length $n$ with initial max frequency $b$:

Case $b = n$ (all characters identical): Turn 1 forces beauty to $n-1$ (must change something). Turn 2 can restore to $n$. Beauty alternates based on parity of $t$.
Case $b < n$ and $n = 1$: Only one character, must change it each turn. Beauty $= 1$ always.
Case $b < n$: Each turn can increase beauty by 1 (change a non-max char to the max char). After enough turns, beauty saturates at $n$. Final beauty $= \min(n, b + t)$.

What breaks if you don't handle the $b = n$ case? You'd compute $\min(n, n + t) = n$ for all $t$, but after turn 1 the beauty is forced down to $n-1$ since you must change a character. The parity trap catches many first submissions.

Parity flow for beauty computation

int calculateBeauty(string& playerString, int turns) {
    int frequencies[26] = {};
    for (char character : playerString) {
        frequencies[character - 'a']++;
    }
    int maxFrequency = *max_element(frequencies, frequencies + 26);
    int stringLength = playerString.size();

    if (stringLength == 1) return 1;
    if (maxFrequency == stringLength) return (turns % 2 == 0) ? stringLength : stringLength - 1;
    return min(stringLength, maxFrequency + turns);
}

Example 6: Array-to-Zero (Construction with Priority Queues)

Problem. Given an array of $n$ non-negative integers, repeatedly pick any two numbers $a$ and $b$, remove them, and insert $|a - b|$. After $n-1$ operations, one number remains. Can you make it 0? If so, construct the sequence of operations.

The Parity Invariant

Before building anything, figure out the constraint. Each operation replaces $(a, b)$ with $|a - b|$. What happens to the total sum?

The total sum changes from $S$ to $S - a - b + |a - b|$. If $a \geq b$, this is $S - a - b + a - b = S - 2b$. The parity of $S$ doesn't change (we subtracted $2b$, which is even).

Invariant: The parity of the sum never changes. If the initial sum is odd, the final number is odd, so it cannot be 0. If the initial sum is even, we can reach 0.

Predict before continuing: Can $[4, 6, 2]$ reach 0? Can $[3, 5, 1]$?

Why Even Sum Is Sufficient

If the sum is even, we can partition the array into two subsets with equal sums. Call them $S_A$ and $S_B$ with $S_A = S_B = \text{total}/2$. Now pair up elements: repeatedly take one from A and one from B, replace with $|a - b|$. The invariant $\text{sum}_A = \text{sum}_B$ is maintained throughout, so the final number is $|\text{sum}_A - \text{sum}_B| = 0$.

The Priority Queue Construction

Partition phase: Use subset-sum DP to split the array into two groups with equal sums.
Simulation phase: Put each group into a max-heap. Repeatedly pop the maximum from each heap, compute $|a - b|$, and push the difference back into the heap of the larger element. Continue until one element remains.

Detailed Trace

Stare at this table. Array $= [6, 3, 5, 2]$. Sum $= 16$ (even, so we can reach 0).

Partition: Find subsets with sum 8 each. One partition: $\{6, 2\}$ and $\{5, 3\}$.

Heap A $= \{6, 2\}$, Heap B $= \{5, 3\}$.

| Step | Pop from A | Pop from B | $|a - b|$ | Push to | Heap A | Heap B | |------|-----------|-----------|-----------|---------|--------|--------| | 1 | 6 | 5 | 1 | A | $\{2, 1\}$ | $\{3\}$ | | 2 | 2 | 3 | 1 | B | $\{1\}$ | $\{1\}$ | | 3 | 1 | 1 | 0 | done | $\{\}$ | $\{0\}$ |

Final value: 0. The construction works.

Verify it yourself: Check that $\text{sum}(\text{Heap A}) = \text{sum}(\text{Heap B})$ after each step. Step 1: $A=\{2,1\}$ sum=3, $B=\{3\}$ sum=3. Step 2: $A=\{1\}$ sum=1, $B=\{1\}$ sum=1. The invariant holds throughout.

What Breaks If You Skip the Partition?

Here's where almost every first implementation breaks. A tempting wrong approach: always pair the two largest numbers (single max-heap, no partition).

Try $[3, 1, 1, 1]$. Sum $= 6$ (even).

Wrong approach (single heap): - Pop 3, 1 → 2. Heap: $\{2, 1, 1\}$ - Pop 2, 1 → 1. Heap: $\{1, 1\}$ - Pop 1, 1 → 0. Result: 0. Works here!

But now try $[4, 4, 2, 2, 1, 1]$. Sum $= 14$ (even). Without the partition, a greedy single-heap approach might not produce 0 — it depends on the order of pops. The partition-based approach gives a clean invariant-based proof of correctness: $\text{sum}_A = \text{sum}_B$ at every step, so the final result must be 0.

The Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numElements;
    cin >> numElements;

    vector<int> elements(numElements);
    long long totalSum = 0;
    for (int i = 0; i < numElements; i++) {
        cin >> elements[i];
        totalSum += elements[i];
    }

    if (totalSum % 2 != 0) {
        cout << "No\n";
        return 0;
    }

    long long targetHalfSum = totalSum / 2;
    vector<bool> canReachSum(targetHalfSum + 1, false);
    canReachSum[0] = true;
    vector<vector<bool>> elementChosen(numElements, vector<bool>(targetHalfSum + 1, false));

    for (int i = 0; i < numElements; i++) {
        for (long long currentSum = targetHalfSum; currentSum >= elements[i]; currentSum--) {
            if (canReachSum[currentSum - elements[i]] && !canReachSum[currentSum]) {
                canReachSum[currentSum] = true;
                elementChosen[i][currentSum] = true;
            }
        }
    }

    if (!canReachSum[targetHalfSum]) {
        cout << "No\n";
        return 0;
    }

    priority_queue<int> heapA, heapB;
    long long remainingSum = targetHalfSum;
    for (int i = numElements - 1; i >= 0; i--) {
        if (elementChosen[i][remainingSum]) {
            heapA.push(elements[i]);
            remainingSum -= elements[i];
        } else {
            heapB.push(elements[i]);
        }
    }

    cout << "Yes\n";
    while (heapA.size() + heapB.size() > 1) {
        int maxA = heapA.top(); heapA.pop();
        int maxB = heapB.top(); heapB.pop();
        int difference = abs(maxA - maxB);

        cout << maxA << " " << maxB << " -> " << difference << "\n";

        if (difference > 0) {
            if (maxA >= maxB) {
                heapA.push(difference);
            } else {
                heapB.push(difference);
            }
        }
    }
    return 0;
}

The Construction Mindset

Construction problems follow a consistent pattern:

Find the formula — the answer is $n - \text{max\_frequency}$, "sum of rising edges", "only if sum is even", etc.
Prove achievability — if the formula says "yes", show how to build a witness.
Handle impossibility — if the formula says "no", prove it by invariant or pigeonhole.
Small-case enumeration — when an unknown parameter (like "number of mixed bouquets") has a small range, try all values.

Instead of asking "how do I build the answer?", ask: "what invariant must the answer satisfy, and how do I construct something that respects it?"

Try It

Warm-up 1: Ciel and Flowers

Compute the answer by hand for each. Predict first, then verify with the formula.

A. $r = 9$, $g = 9$, $b = 9$.

Try mix = 0: $3 + 3 + 3 = 9$. Try mix = 1: $1 + 2 + 2 + 2 = 7$. Try mix = 2: $2 + 2 + 2 + 2 = 8$. Answer $= 9$ (0 mixed).

When each color is a multiple of 3, mixed bouquets never help. Why? Each mixed bouquet uses 1 of each color, "wasting" the divisibility by 3.

B. $r = 4$, $g = 4$, $b = 4$.

Try mix = 0: $\lfloor 4/3 \rfloor + \lfloor 4/3 \rfloor + \lfloor 4/3 \rfloor = 1 + 1 + 1 = 3$. Try mix = 1: $1 + \lfloor 3/3 \rfloor + \lfloor 3/3 \rfloor + \lfloor 3/3 \rfloor = 1 + 1 + 1 + 1 = 4$. Try mix = 2: $2 + \lfloor 2/3 \rfloor + \lfloor 2/3 \rfloor + \lfloor 2/3 \rfloor = 2 + 0 + 0 + 0 = 2$. Answer $= $ 4.

C. $r = 2$, $g = 2$, $b = 2$.

Try mix = 0: $0 + 0 + 0 = 0$. Try mix = 1: $1 + 0 + 0 + 0 = 1$. Try mix = 2: $2 + 0 + 0 + 0 = 2$. Answer $= 2$ (all mixed).

When counts are small and not divisible by 3, mixed bouquets dominate.

Warm-up 2: Array-to-Zero

Can these arrays reach 0? Predict before checking.

A. $[4, 6, 2]$. Sum $= 12$ (even). Yes. B. $[3, 5, 1]$. Sum $= 9$ (odd). No. C. $[0, 0, 0]$. Sum $= 0$ (even). Yes (already done). D. $[7, 7]$. Sum $= 14$ (even). Yes: $|7 - 7| = 0$.

For array $[4, 6, 2]$, find a partition into equal-sum subsets and trace the priority-queue construction step by step. Verify that $\text{sum}_A = \text{sum}_B$ after every operation.

Challenge

In the Contrast problem, prove that sorting A ascending and B descending minimizes the number of positions where $A[i] = B[i]$. What property of sorted arrays makes opposite-direction sorting maximize separation?

Problems

Problem	Link	Difficulty
ABC178F — Contrast	atcoder.jp/contests/abc178/tasks/abc178_f	600pts
CF1007A — Reorder the Array	codeforces.com/problemset/problem/1007/A	1600
CF322B — Ciel and Flowers	codeforces.com/problemset/problem/322/B	1600
ABC046D — AtCoDeer and Rock-Paper	atcoder.jp/contests/abc046/tasks/arc062_b	300pts
CF979B — Treasure Hunt	codeforces.com/problemset/problem/979/B	1800

Mixed	Remaining \(r\)	Remaining \(g\)	Remaining \(b\)	Same-color	Total
0	7	4	2	\(2 + 1 + 0 = 3\)	3
1	6	3	1	\(2 + 1 + 0 = 3\)	4
2	5	2	0	\(1 + 0 + 0 = 1\)	3

\(i\)	\(A[i]\)	\(B[i]\) (desc)	Match?
0	1	3	No
1	1	2	No
2	2	1	No
3	3	1	No