Why this matters when you build with AI
Greedy methods look right almost every time. An AI tool will often propose one, explain it in two confident sentences, and pass the sample in the statement. The sample is usually too small to show the flaw. A greedy that picks the best-looking choice at each step can be wrong on a case with three items, as the example below shows, and the explanation will not mention it.
Constructive problems ask for an output that has a property, such as an arrangement, a set or a path. Many of them have no standard method, so people call them ad hoc. For these problems the test is not a comparison with a fixed answer. You write a validator, which is a short program that checks whether an output has the required property. The validator is often more useful than a brute force, because it can check large outputs too.
This lesson covers three habits. First, study extreme cases, where a value is at its smallest or largest, because they show the structure of the answer. Second, look for an invariant, which is a property that stays true after every step of a construction. Third, test every greedy choice against a brute force on small inputs. The first failing input is the counterexample, and it is the most useful thing the test can give you.
This lesson uses C++17 and Python, compiled with g++ 15.2.0 and run with Python 3.14.4 on Ubuntu. Output on your machine should match for the counts and for the printed answers.
The idea: three tools
A greedy method makes one choice at a time and never takes it back. It picks the option that looks best at the moment. A greedy is correct only if some argument shows that the choice cannot block a better answer later.
A constructive method builds the answer piece by piece, with a rule that keeps the partial answer possible. The rule is the invariant. An invariant is a statement that is true before the first step and stays true after each step. For example: "the values used so far are distinct, and the remaining positions can still be filled."
An extreme case is the input where a parameter is at its smallest or largest value, such as k = 0, k = n - 1 or k = n. Extreme cases often show the shape of the answer at once. If the shape is forced, the general answer is usually a small variation of it.
A counterexample is a small input on which a method gives a wrong answer. You find counterexamples by running the method against a brute force, and the smallest one is the easiest to understand.
Worked example: exactly k excedances
Here is an original problem written for this lesson. A permutation is an arrangement of the numbers 1 to n in some order, with each number used once.
Given
nandk, print a permutationp_1 ... p_nof the numbers 1 tonsuch that exactlykindicesihavep_i > i. Call such an index an excedance: the value there is larger than its position. If no such permutation exists, print -1. Input: one line withnandk. Output:nnumbers on one line, or -1. Any valid answer is accepted. Constraints:1 <= n <= 200000and0 <= k <= n.
The word "any" matters. Many valid permutations exist, so a judge for this problem must check the output, not compare it with one fixed answer.
Small cases by hand
Start with n = 1. The only permutation is [1], which has no excedance. So k = 0 works and k = 1 does not.
For n = 2 there are two permutations. [1, 2] has no excedance. In [2, 1], position 1 holds 2, which is larger than 1, so there is one excedance. So k = 0 and k = 1 work, and k = 2 does not.
For n = 3 and k = 2, try 2 3 1. Position 1 holds 2 (excedance), position 2 holds 3 (excedance), and position 3 holds 1 (not an excedance). That is two excedances, so it works.
Look at what the small cases already show. A position i can be an excedance only if it holds a value bigger than i. The last position, n, can never hold a value bigger than n. So the last position is never an excedance, and k = n is impossible for every n. The question is whether every k from 0 to n - 1 is possible. The brute force answers that.
A brute force that counts every permutation
The brute force tries every permutation of 1 to n, using next_permutation from the standard library to move from one arrangement to the next. For each one it counts the excedances, and it adds one to a counter for that count.
#include <bits/stdc++.h>
using namespace std;
// For each n, try every permutation of 1..n and count how many
// positions i have p_i > i (call these excedances).
// Prints, for each n, how many permutations have each count.
int main() {
for (int n = 1; n <= 7; n++) {
vector<int> p(n);
iota(p.begin(), p.end(), 1);
vector<long long> ways(n + 1, 0);
do {
int ex = 0;
for (int i = 0; i < n; i++)
if (p[i] > i + 1) ex++;
ways[ex]++;
} while (next_permutation(p.begin(), p.end()));
cout << "n=" << n << " counts for k=0.." << n << ":";
for (int k = 0; k <= n; k++) cout << ' ' << ways[k];
cout << '\n';
}
}Compile and run it with the warning and sanitizer flags:
g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wconversion -fsanitize=address,undefined -fno-sanitize-recover=all brute.cpp -o brute
./bruteReal output of our run:
n=1 counts for k=0..1: 1 0
n=2 counts for k=0..2: 1 1 0
n=3 counts for k=0..3: 1 4 1 0
n=4 counts for k=0..4: 1 11 11 1 0
n=5 counts for k=0..5: 1 26 66 26 1 0
n=6 counts for k=0..6: 1 57 302 302 57 1 0
n=7 counts for k=0..7: 1 120 1191 2416 1191 120 1 0Read the last two numbers of each row. The count for k = n is always 0, as the argument above says. The count for k = n - 1 is always 1. So for every n up to 7, each k from 0 to n - 1 is possible, and k = n is not. This is a pattern from data, and the next section proves the case that matters most.
The extreme case: k = n - 1
Suppose k = n - 1. Then each of the positions 1 to n - 1 is an excedance, so p_i >= i + 1 for each of them. Work down from the top.
- Position
n - 1needs a value at leastn, so it holdsn. - Position
n - 2needs a value at leastn - 1. The valuenis already used, so it holdsn - 1. - Keep going the same way. Each position
igets the valuei + 1.
The last position then gets the one value left, which is 1. The only permutation with n - 1 excedances is 2 3 ... n 1. That is why the count for k = n - 1 is always 1.
This is a useful habit. You did not need the general case to learn the shape of the answer. The extreme case gave it to you in four lines of reasoning.
The construction
The extreme case suggests a construction. Take the first k + 1 positions and rotate their values, so that each of the first k positions holds the next number, and position k + 1 holds 1. Every other position keeps its own value, which is not an excedance.
For n = 5 and k = 2, the first three positions become 2, 3, 1 and the rest stay as 4, 5:
position: 1 2 3 4 5
value: 2 3 1 4 5
excedance: y y n n nThere are two excedances, so the answer is correct. The construction needs k + 1 <= n, which is the same as k <= n - 1. That is exactly the case where an answer exists. The invariant here is simple: after the first k positions are set, each of them holds a value one bigger than its position, and the values used are all distinct.
#include <bits/stdc++.h>
using namespace std;
// Input: n and k. Output a permutation of 1..n with exactly k
// positions i where p_i > i, or -1 if none exists.
// Construction: for i = 1..k set p_i = i + 1, set p_{k+1} = 1,
// and keep every other position fixed. This needs k + 1 <= n.
int main() {
int n, k;
cin >> n >> k;
if (k >= n) {
cout << -1 << '\n';
return 0;
}
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= k; i++) p[i] = i + 1;
p[k + 1] = 1;
for (int i = 1; i <= n; i++) {
if (i > 1) cout << ' ';
cout << p[i];
}
cout << '\n';
}Our run gave these answers for five inputs:
input 5 2 -> 2 3 1 4 5
input 5 0 -> 1 2 3 4 5
input 5 4 -> 2 3 4 5 1
input 1 0 -> 1
input 1 1 -> -1The 5 0 case shows that a fixed point, where p_i = i, is not an excedance. The 5 4 case is the extreme shape from the proof. The cost is O(n) time and O(n) memory, which is fine for n = 200000.
A validator, not a fixed answer
Because many answers are valid, the test must check the properties directly. The validator below takes n, k and the output, and reports why the output is wrong, if it is. It is short, and it can check any n, including values far too large for the brute force.
def problem(n, k, tokens):
"""Return None if the answer is valid, else a short reason."""
if k >= n:
return None if tokens == ["-1"] else "expected -1"
if tokens == ["-1"]:
return "printed -1 but a permutation exists"
try:
p = [int(t) for t in tokens]
except ValueError:
return "not numbers"
if len(p) != n or sorted(p) != list(range(1, n + 1)):
return "not a permutation of 1..n"
ex = sum(1 for i in range(n) if p[i] > i + 1)
if ex != k:
return f"has {ex} excedances, wanted {k}"
return NoneThe validator does three checks: the count of numbers, that the numbers are exactly 1 to n, and the excedance count. Each check gives a reason that you can read. The validator is the program that tells you a result is wrong. The brute force only tells you the answer is wrong on small n.
The tempting greedy
Here is a greedy that looks reasonable. Go left to right. While fewer than k excedances have been placed, give the current position the largest unused value, because a large value is more likely to be bigger than its position. Once k excedances are placed, give each remaining position the smallest unused value.
#include <bits/stdc++.h>
using namespace std;
// A tempting greedy. Go left to right. While fewer than k excedances
// have been placed, give the position the largest unused value.
// Otherwise give it the smallest unused value.
int main() {
int n, k;
cin >> n >> k;
set<int> unused;
for (int v = 1; v <= n; v++) unused.insert(v);
int placed = 0;
vector<int> p;
for (int i = 1; i <= n; i++) {
int v;
if (placed < k) {
v = *unused.rbegin();
unused.erase(prev(unused.end()));
} else {
v = *unused.begin();
unused.erase(unused.begin());
}
if (v > i) placed++;
p.push_back(v);
}
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
cout << p[i];
}
cout << '\n';
}It passes the sample 5 2, since it prints 5 4 1 2 3, which has two excedances. That is exactly why a sample is a poor test. Now trace it by hand on n = 3 and k = 2:
- Position 1: fewer than 2 placed, so take the largest unused value, 3. Since 3 > 1, the count becomes 1.
- Position 2: still fewer than 2 placed, so take the largest unused value, 2. Since 2 is not bigger than 2, the count stays 1.
- Position 3: still fewer than 2 placed, so take the largest unused value, 1. It is not bigger than 3, so the count stays 1.
The output is 3 2 1 with one excedance, but k = 2. The greedy is wrong, and the case is small enough to check on paper. The correct answer 2 3 1 exists.
The reason is that the greedy spends the large values on early positions. Late positions need a value bigger than their own index, and by then only small values remain. The invariant that the greedy should keep is "the remaining values can still give the remaining positions the excedances we need." The greedy does not check it.
Testing the greedy on many small inputs
Run the greedy for every n from 1 to 8 and every k below n, and check each output with the validator. The check file also checks the construction from above for n up to 30, and five large random inputs. This is the same loop idea as the stress test in the first contest module. Here the validator replaces the brute force, because the output can be checked directly.
import random
import subprocess
def run(prog, n, k):
out = subprocess.run([prog], input=f"{n} {k}\n", capture_output=True, text=True, timeout=10)
return out.stdout.split(), out.returncode
def problem(n, k, tokens):
"""Return None if the answer is valid, else a short reason."""
if k >= n:
return None if tokens == ["-1"] else "expected -1"
if tokens == ["-1"]:
return "printed -1 but a permutation exists"
try:
p = [int(t) for t in tokens]
except ValueError:
return "not numbers"
if len(p) != n or sorted(p) != list(range(1, n + 1)):
return "not a permutation of 1..n"
ex = sum(1 for i in range(n) if p[i] > i + 1)
if ex != k:
return f"has {ex} excedances, wanted {k}"
return None
# 1. The construction, for every n up to 30 and every k up to n.
bad = []
for n in range(1, 31):
for k in range(0, n + 1):
tokens, code = run("./solve", n, k)
reason = problem(n, k, tokens)
if code != 0 or reason:
bad.append((n, k, reason))
print("solve, n = 1..30, every k: failures =", len(bad), bad[:3])
# 2. The construction on a few large random inputs.
rnd = random.Random(7)
big_bad = 0
for _ in range(5):
n = rnd.randint(100000, 200000)
k = rnd.randint(0, n)
tokens, code = run("./solve", n, k)
if code != 0 or problem(n, k, tokens):
big_bad += 1
print("solve, 5 large random cases: failures =", big_bad)
# 3. The tempting greedy, for n up to 8, only where an answer exists.
first_fail = None
fails = 0
for n in range(1, 9):
for k in range(0, n + 1):
if k >= n:
continue
tokens, code = run("./greedy_bad", n, k)
reason = problem(n, k, tokens)
if reason:
fails += 1
if first_fail is None:
first_fail = (n, k, tokens, reason)
print("greedy_bad, n = 1..8, k < n: failing pairs =", fails)
print("first failure:", first_fail)Real output of our run:
solve, n = 1..30, every k: failures = 0 []
solve, 5 large random cases: failures = 0
greedy_bad, n = 1..8, k < n: failing pairs = 12
first failure: (3, 2, ['3', '2', '1'], 'has 1 excedances, wanted 2')The construction passed every check. The greedy failed 12 of the 36 feasible pairs with n up to 8. The first failure is the n = 3, k = 2 case we traced by hand, so the smallest counterexample is the one you can check on paper.
The validator reports a reason for each failure, so you do not have to guess what went wrong. A failure that says "has 1 excedances, wanted 2" points straight at the count.
How a counterexample teaches the fix
The counterexample n = 3, k = 2 tells you which property the greedy lost. After position 1 gets the value 3, the greedy has one excedance and needs one more. Position 2 then gets 2, which is not bigger than 2, so that step adds nothing. The construction avoids this because it decides the shape of the first k + 1 positions in advance, rather than taking the largest value each time.
Another counterexample, n = 4 and k = 3, gives 4 3 2 1, which has two excedances. Both failures share a cause: the large values go to the early positions, and the later positions can no longer be excedances.
Complexity
The construction takes O(n) time and O(n) memory. The brute force takes O(n × n!) time, so it is only usable for n up to about 9 or 10. The greedy shown here uses a set and takes O(n log n) time, but its speed does not matter, since it is wrong.
The answer stays within the normal integer range for every input in the constraints. The printed values are at most n, so 32-bit integers are enough.
Common mistakes
Trusting a greedy because it passes the sample. The sample 5 2 passes with the wrong greedy. The symptom is a judge that rejects a submission on a hidden test with a small n. Test every greedy on all inputs with n up to 8 or 9 before you submit it.
Printing a permutation when k is too large. For k = n the answer is -1. The symptom is the validator message "expected -1". Check the boundary k >= n in the code and in the tests.
Counting fixed points as excedances. A position with p_i = i is not an excedance, because the condition is strict. The symptom is one extra count in each run of fixed points. Use p_i > i exactly as written.
An off-by-one in the rotation. The position k + 1 must exist, so the rotation needs k + 1 <= n. The symptom is an out-of-range write for k = n. Handle k >= n before the rotation, as the code does.
Expecting one exact output. The problem accepts any valid answer. If your answer is valid but differs from the sample output, check the judge rules before you change the code. If the judge compares text, you need a different judge, not a different permutation.
Using a brute force as the only check at large n. The brute force cannot reach n = 200000. The validator can, and it should be your check at large n.
Writing the greedy first and the reason second. A greedy idea has to come with an argument why it keeps the answer possible. If you cannot state the invariant, treat the greedy as a guess and test it.
Checklist
- Work the small cases by hand, including the case where no answer exists.
- Find the extreme case, and check whether its shape is forced.
- Write the brute force and print the counts for each parameter value.
- Write the construction, and state the invariant it keeps.
- Write a validator that checks the output rule directly, and reports a reason.
- Test every greedy choice on all inputs with a small
n, and keep the first failing case. - Test the construction at large
nwith the validator, not with the brute force. - Check the boundary cases:
n = 1,k = 0, andk = n. - Compare your output with the judge rules, since many constructive problems accept any valid answer.
Hands-on exercise
Make a new folder. Save the brute force as brute.cpp, the construction as solve.cpp, the greedy as greedy_bad.cpp, and the Python checks as check.py. Build the three programs with the flags from this lesson.
- Run
bruteand copy the rows for n = 5, 6 and 7. Check that the last count in each row is 0, and the one before it is 1. - Run
check.py. Record the four output lines. - Trace
greedy_badby hand onn = 4andk = 3. Write each position, the value it takes, and the count after the step. Compare your trace with the program output. - Write your own greedy,
greedy_mine.cpp, that places the smallest unused value greater than the current position while it still needs excedances, and otherwise places the smallest unused value. Add it to the check, run it fornup to 8, and record the first failing pair, if any.
Show the answer
Step 1: the rows for n = 5, 6 and 7 end in 26 1 0, 57 1 0 and 120 1 0 respectively, which is the count for k = n - 2, then k = n - 1, then k = n. The last count is 0 and the one before it is 1. Step 2: the four output lines are the ones shown in the lesson, with the same numbers. Step 3: position 1 takes 4 (count 1), position 2 takes 3 (count 2), position 3 takes 2 (not bigger than 3, count 2), position 4 takes 1 (count 2). The output is 4 3 2 1 with two excedances, not three. Step 4: the smallest-greater greedy gives i + 1 to each of the first k positions, because for those positions the value i + 1 is the smallest unused value above i. The rest are filled in increasing order, which gives fixed points. So its output is the same as the construction. Our check of this greedy, run as a Python simulation of the same logic rather than as the C++ program, gave exactly k excedances for every n up to 11 and every k below n. The simulation is evidence, and the argument above is the reason it holds for every n.
Practice problems
Work each problem by hand first, then check it in code.
Practice 1: arrange letters with no equal neighbours. You are given three counts a, b and c of the letters a, b and c, with total n = a + b + c. Print a string with exactly those counts, in which no two neighbouring letters are equal, or print -1 if none exists.
Hint: the most frequent letter needs a gap between each pair of its copies. Think about how many positions can be chosen with no two neighbours in a row of n positions. Then try placing the letters in order of frequency, first into the even positions and then into the odd ones.
Show the answer
An answer exists exactly when the largest count is at most (n + 1) // 2. A row of n positions has at most (n + 1) // 2 positions with no two neighbours, so a letter with more copies than that cannot be placed. When the largest count is within the limit, sort the letters by count, write them into the slots 0, 2, 4, ... and then 1, 3, 5, ..., so the most frequent letter fills the even slots first. Our check of this method against an exhaustive search for every triple with total up to 9 gave 219 triples and no problems. Examples: (3, 2, 1) gives ababac, and (4, 1, 1) gives -1.
def build(a, b, c):
n = a + b + c
counts = sorted([("a", a), ("b", b), ("c", c)], key=lambda t: -t[1])
if counts[0][1] > (n + 1) // 2:
return None
order = []
for letter, cnt in counts:
order += [letter] * cnt
slots = list(range(0, n, 2)) + list(range(1, n, 2))
res = [""] * n
for slot, letter in zip(slots, order):
res[slot] = letter
return "".join(res)Practice 2: a greedy for the knapsack. There are three items, each with a weight and a value: item 1 has weight 6 and value 10, item 2 has weight 5 and value 8, and item 3 has weight 5 and value 8. The capacity is 10. Each item can be taken at most once. Find the largest total value that fits. Then write the greedy that takes items in order of value divided by weight, skipping any item that does not fit, and find out whether it gives the best answer.
Hint: compare the two items with weight 5 against the single item with weight 6.
Show the answer
The best total is 16, from taking items 2 and 3, whose weights add to 10. The greedy by value divided by weight ranks item 1 first (10/6, about 1.67), then items 2 and 3 (8/5 = 1.6 each). It takes item 1, which fills 6 of the 10 units, then skips items 2 and 3 because only 4 units remain. Its total is 10, which is not the best. The counterexample is the three-item set itself, and a brute force over the eight subsets finds 16. Ratio greedies are exact for the fractional version of this problem, where an item can be cut, but not for the one where each item is taken whole.
Practice 3: count the extreme case. How many permutations of 1 to 5 have exactly 4 excedances? Give the permutation, and explain why there are no others, using the argument from the lesson.
Hint: work from position 4 down to position 1, and ask which value each position can take.
Show the answer
There is exactly one: 2 3 4 5 1. Each of positions 1 to 4 must hold a value at least one bigger than its position. Position 4 must hold 5, position 3 must hold 4 (since 5 is used), position 2 must hold 3, and position 1 must hold 2. Position 5 gets the last value, 1. Our brute force for n = 5 prints 1 for k = 4, which agrees.
Practice 4: deficiencies. A deficiency is a position i with p_i < i. Given n and k, print a permutation with exactly k deficiencies, or -1 if none exists. Reuse the construction from the lesson.
Hint: reverse the positions and complement the values. Position j takes the value n + 1 - q_(n+1-j), where q is an excedance permutation.
Show the answer
Let q be the output of the construction for (n, k), and let p_j = n + 1 - q_(n+1-j). The values of p are a permutation, because complementing values keeps them in 1 to n. Now p_j < j is the same as q_i > i with i = n + 1 - j, so the deficiencies of p are exactly the excedances of q, which is k. For k >= n print -1. Our check for every n from 1 to 14 and every k below n found the count correct each time. For n = 5 and k = 2, the answer is 1 2 5 3 4, which has deficiencies at positions 4 and 5.
Python notes
The validator and the checks above are in Python, because they are short and need no speed. The brute force and the constructions are in C++, because the brute force reaches only about n = 9, and the constructions must run at n = 200000.
For a small problem, a Python brute force works too. It needs about n! steps, so it is practical only up to about n = 8. Python's itertools.permutations produces every permutation too, although in a different order.
Python also has no integer overflow, so a Python check can use any size of value without a risk. The contest solution still needs the fixed-size types of C++.
Summary
For a constructive problem, study the extreme cases first, build the answer with an invariant, and check it with a validator. Test every greedy on small inputs, because the first failing case is the counterexample that shows what the greedy lost.