What is a constructive problem?
A constructive problem asks us to produce an object that meets some rules, such as an arrangement, a grid or a string, rather than a number or a yes-or-no answer. When several objects meet the rules and the judge accepts any of them, we are free to pick one that is easy to describe and easy to prove correct. Let's see an example.
Given and , return a list of the numbers 1 to , each once, such that the absolute differences between neighbours take exactly different values. If several lists work, return any of them.
Constraints
Sample 1 · Input
n = 3, k = 1
Output
[1,2,3]
Sample 2 · Input
n = 3, k = 2
Output
[1,3,2]
In the second sample, [1, 3, 2] has differences 2 and 1, which is two different values. A search would try arrangements, and there are of them: at already , while can be . Instead, let's aim for an answer whose differences we control. We need different differences, and the simplest set to aim for is . The values 1 to can produce all of them: start at 1, jump up to for a difference of , come back down to 2 for , go up to for , and so on. Alternating the lowest and highest unused values this way gives a zigzag:
That gives different differences, exactly as many as the problem asks for. Then we append the remaining values, up to , in increasing order. The zigzag has already used every difference from 1 to , the step into the tail is at most because the zigzag ends on a value of at least 2, and the steps inside the tail are 1, so the tail adds no new difference.
def construct_array(n, k):
lo, hi, out = 1, k + 1, []
while lo <= hi:
out.append(lo)
lo += 1
if lo <= hi:
out.append(hi)
hi -= 1
return out + list(range(k + 2, n + 1))
print(construct_array(3, 1))
print(construct_array(3, 2))
print(construct_array(5, 3))The two samples print [1, 2, 3] and [1, 3, 2]; for , , the differences of [1, 4, 2, 3, 5] are 3, 2, 1, 2.
A construction is easy to get slightly wrong, so we also write a checker that recomputes the differences and confirms the output uses each of 1 to once, then run it on every and up to a small bound. This one passes for every from 2 to 11 and every from 1 to .
Check an arrangement's differences
The widget builds the alternating order for the chosen and , writes the difference under each neighbouring pair, and runs the checker on it. The shaded values are the zigzag over 1 to ; the rest is the tail.
Swap two values and the checker runs again. Can you find a swap that keeps the order valid? With the starting and , 14 of the 28 possible swaps break the order.
With and there is no tail at all: the zigzag uses every difference from 9 down to 1.
Compare the construction with a search
- Alternating construction
n steps - Each value is written once.
- Checker
n steps - One pass for the differences and one to confirm each of 1 to appears once.
- Search over arrangements
n! orders - orders for 15 values, and can be .
Common construction mistakes
Starting the tail at instead of .
- Where it breaks
- For , the zigzag is
[1, 4, 2, 3], which already holds 4. A tail from 4 appends it again,[1, 4, 2, 3, 4, 5], which has six values and repeats one. - The fix
- The zigzag uses exactly 1 to , so the tail starts at . A checker that confirms each of 1 to appears once catches this at once.
Trusting a construction after the samples pass.
- Where it breaks
- Both samples have , so a rule that only works when or passes them and fails on , .
- The fix
- Run the checker on every and up to a small bound before submitting.
Recall Why does appending $k + 2$ to $n$ add no new difference?
The zigzag has at least two values and starts with 1, so its last value is at least 2, and the step up to is at most . The zigzag has used every difference from 1 to , so that step repeats one of them. Inside the tail every step is 1, which the zigzag also used.
Key terms
| Term | Meaning |
|---|---|
| Constructive problem | A problem that asks for any object meeting the rules. |
| Checker | A program that tests whether an output meets the rules, used to try a construction on every small input. |