Basics 0/98

Ad hoc and observation: solving with invariants · 2 of 2 Advanced

Constructive algorithms

Build any answer that meets the rules from a simple pattern, then trust it by checking every small input.

793 words · 4 min read

Part 1 of 4 Constructive algorithms

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 nn and kk, return a list of the numbers 1 to nn, each once, such that the absolute differences between neighbours take exactly kk different values. If several lists work, return any of them.

Constraints

  • 1≤k<n≤1041 \le k < n \le 10^4

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 n!n! of them: at n=15n = 15 already 15!≈1.3×101215! \approx 1.3 \times 10^{12}, while nn can be 10410^4. Instead, let's aim for an answer whose differences we control. We need kk different differences, and the simplest set to aim for is 1,2,…,k1, 2, \dots, k. The values 1 to k+1k + 1 can produce all of them: start at 1, jump up to k+1k + 1 for a difference of kk, come back down to 2 for k−1k - 1, go up to kk for k−2k - 2, and so on. Alternating the lowest and highest unused values this way gives a zigzag:

1, k+1, 2, k, 3, …differences: k, k−1, k−2, …, 11,\ k + 1,\ 2,\ k,\ 3,\ \dots \qquad \text{differences: } k,\ k - 1,\ k - 2,\ \dots,\ 1

That gives kk different differences, exactly as many as the problem asks for. Then we append the remaining values, k+2k + 2 up to nn, in increasing order. The zigzag has already used every difference from 1 to kk, the step into the tail is at most kk 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.

Sign up to run
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 n=5n = 5, k=3k = 3, 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 nn once, then run it on every nn and kk up to a small bound. This one passes for every nn from 2 to 11 and every kk from 1 to n−1n - 1.

Check an arrangement's differences

The widget builds the alternating order for the chosen nn and kk, writes the difference under each neighbouring pair, and runs the checker on it. The shaded values are the zigzag over 1 to k+1k + 1; 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 n=8n = 8 and k=4k = 4, 14 of the 28 possible swaps break the order.

n 8
k 4

Press two values to swap them. The checker recomputes every difference.

  1. 4
  2. 3
  3. 2
  4. 1
  5. 3
  6. 1
  7. 1

Distinct differences: 1, 2, 3, 4 (4)

The checker accepts: each of 1 to n appears once, and there are 4 distinct differences, as k = 4 asks.

With n=10n = 10 and k=9k = 9 there is no tail at all: the zigzag 1,10,2,9,3,8,…1, 10, 2, 9, 3, 8, \dots uses every difference from 9 down to 1.