A stress test prints a failing array. It has 200 elements. Your solution says 17, the brute force says 16, and neither answer tells you which part of the array matters.

Before adding more cerr, try deleting most of the input.

This tutorial builds a small counterexample reducer: give it a failing test and a predicate that recognizes the failure; it repeatedly simplifies the test while keeping that predicate true. There is a complete Python demo below, including an intentionally wrong LIS implementation. No packages are needed.

The useful part is not specific to LIS. It is learning what your reducer is allowed to change, and what it must preserve.

1. Start with an example we can check by hand

The task is to find the length of a strictly increasing subsequence.

Consider:

8 3 5 5 2 9 1 7 7 4 6 6

The correct answer is 3. An implementation that uses upper_bound instead of lower_bound in the usual tails algorithm returns 5: it allows equal values to extend the subsequence.

The reduced example is much more helpful:

0 0

Correct answer: 1. Wrong answer: 2.

Now the question is concrete: why can an equal value extend a strictly increasing subsequence?

In C++, lower_bound finds the first tail greater than or equal to x; upper_bound finds the first tail strictly greater than x. For strict LIS, the equal tail should be replaced. Python's corresponding functions are bisect_left and bisect_right.

2. Define exactly what counts as failure

For this demo:

def fails(a):
    return bool(a) and reference(a) != candidate(a)

The bool(a) matters: our demo's valid inputs are nonempty integer arrays. On another problem, the predicate must also enforce that problem's constraints.

A reducer only knows this predicate. It does not know whether it found your original bug, another wrong answer, an invalid test, or a broken checker.

For a usual batch problem, use this order:

1. Validate the proposed input.
2. Run the reference and candidate, with timeouts.
3. Check that both executions completed successfully.
4. Compare their answers using the problem's actual output rules.

If you are reducing a wrong answer, do not silently accept a crash as another wrong answer. For a constructive task, different valid outputs are fine: validate the construction instead of comparing text. For floating-point output, use the required tolerance.

3. Delete chunks, then try smaller chunks

Split the array into a few contiguous chunks. Try removing each chunk. If the remaining array still fails, keep it and start again. If none works, use smaller chunks, eventually trying individual elements.

This is a deletion-based variant of delta debugging, an established technique associated with Andreas Zeller and Ralf Hildebrandt. The technique is not new; the code below is a compact implementation for this tutorial. See Zeller's delta debugging guide for background.

Why not just delete one element at a time?

Besides being slow on large inputs, that can get stuck too early. Imagine a failure predicate that holds only for even lengths of at least two. Starting with four elements, every single deletion removes the failure. Deleting a pair preserves it.

Also, this is not binary search on a monotone predicate. A failure can disappear and reappear as elements are removed. Each proposed reduction must be tested.

4. Small values sometimes require a joint change

After deletion, this demo reaches [6, 6].

Try changing one value to zero:

[0, 6] -> both implementations return 2
[6, 0] -> both implementations return 1

Neither change preserves the failure. But changing both values to zero does.

That is why the reducer also tries coordinate compression: map the smallest distinct value to 0, the next to 1, and so on. It preserves comparisons and equality, so it is a natural simplification to try here.

It is not a universally valid rewrite. For a sum, distance, divisibility, or overflow bug, the actual magnitudes can matter. Even if compression produces a valid input, run fails again before accepting it. For a problem requiring positive values, start ranks at 1 and update the validator.

After compression, the code tries individual replacements with 0, 1, -1, and a value halfway toward zero. Each accepted replacement must strictly decrease absolute value.

We repeat deletion and value changes until neither makes progress. A value change can make another deletion possible.

5. Complete runnable demo

Save this as shrink_demo.py and run python shrink_demo.py (or python3 shrink_demo.py). The functions work directly on arrays to keep the example independent of compilers, shell syntax, and process handling.

"""A self-contained LIS counterexample reducer. Python 3, no dependencies."""
from bisect import bisect_left, bisect_right


def reference(a):
    # Strictly increasing subsequence, O(n^2).
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)


def candidate(a, fixed=False):
    tails = []
    for x in a:
        p = (bisect_left if fixed else bisect_right)(tails, x)
        if p == len(tails):
            tails.append(x)
        else:
            tails[p] = x
    return len(tails)


def fails(a):
    # This demo permits any nonempty array of integers.
    return bool(a) and reference(a) != candidate(a)


def delete_chunks(a, fails):
    a = list(a)
    assert fails(a)
    parts = 2
    while len(a) >= 2:
        size = (len(a) + parts - 1) // parts
        for start in range(0, len(a), size):
            b = a[:start] + a[start + size:]
            if b and fails(b):
                a = b
                parts = max(2, parts - 1)
                break
        else:
            if parts >= len(a):
                return a
            parts = min(len(a), parts * 2)
    return a


def shrink(a, fails):
    a = list(a)
    assert fails(a)
    while True:
        before = a[:]
        a = delete_chunks(a, fails)
        # Try a coordinated rewrite, preserving order and equality.
        rank = {x: i for i, x in enumerate(sorted(set(a)))}
        b = [rank[x] for x in a]
        if sum(map(abs, b)) < sum(map(abs, a)) and fails(b):
            a = b
        for i, x in enumerate(a):
            # Strictly decrease |x|; avoid cycles such as 0 -> 1 -> 0.
            half = abs(x) // 2 * (1 if x >= 0 else -1)
            for y in dict.fromkeys((0, 1, -1, half)):
                if abs(y) >= abs(x):
                    continue
                b = a[:]
                b[i] = y
                if fails(b):
                    a = b
                    break
        if a == before:
            return a


def main():
    original = [8, 3, 5, 5, 2, 9, 1, 7, 7, 4, 6, 6]
    small = shrink(original, fails)
    print("Original:", original)
    print("Before: reference =", reference(original),
          ", candidate =", candidate(original))
    print("Reduced:", small)
    print("After: reference =", reference(small),
          ", candidate =", candidate(small))
    print("Fixed candidate:", candidate(small, fixed=True))


if __name__ == "__main__":
    main()

Output:

Original: [8, 3, 5, 5, 2, 9, 1, 7, 7, 4, 6, 6]
Before: reference = 3 , candidate = 5
Reduced: [0, 0]
After: reference = 1 , candidate = 2
Fixed candidate: 1

The reference uses the quadratic LIS recurrence. The candidate deliberately uses the wrong bound; fixed=True switches to the correct one.

For verification, both the reference and the fixed candidate were compared with exhaustive subsequence enumeration on all 3,279 arrays of lengths 1 through 7 over {-1, 0, 1}. The wrong candidate disagreed on 3,123 of them. Each of those cases was reduced and checked to ensure it still failed and no single deletion or listed individual value simplification preserved the failure. These are small-domain checks, not a proof of correctness on all inputs.

6. What the reducer guarantees

Assume the predicate is deterministic and every call finishes.

Every accepted deletion decreases length. Every accepted value rewrite decreases the sum of absolute values while keeping length fixed. Thus the pair

(length, sum of absolute values)

strictly decreases in lexicographic order. The loop terminates.

On return, the array still fails. No single-element deletion preserves the predicate: the last unsuccessful deletion pass tried chunks of size one. The final value pass also found no accepted rewrite from its small menu.

That does not mean we found the shortest possible failing test. A different sequence of edits may lead somewhere smaller. The reducer searches a limited set of transformations greedily; [0, 0] happens to be globally shortest for this particular bug because the two implementations agree on every singleton.

Do not infer logarithmic running time from the chunk sizes, either. Many attempts can fail, and each attempt runs your checker. This demo also copies arrays and uses a quadratic reference. Use it on small stress-test failures first; for expensive programs, add a check budget and cache deterministic results.

7. Adapting this to your next WA

Keep delete_chunks and shrink; replace the predicate and transformations to match the input.

The last row catches an easy mistake: reducing each case independently loses bugs caused by state leaking between test cases. If the failure needs case A followed by case B, the reducer must run that sequence in one process.

For a C++ solution, fails can serialize an array, run the two executables, and compare outputs. Recompute n every time; do not delete raw tokens and leave a stale length in the input. Likewise, if you delete graph vertices, repair the labels and edge count before checking the candidate.

Keep the original failing input too. Your predicate may preserve some wrong answer while changing which bug triggers it. After fixing the small case, rerun the original case and your stress tests.

There are two useful stopping points: a test the reducer cannot simplify further, and a test you already understand. The second is often enough.

If you have a nice example where shrinking exposed a surprising bug, a before/after pair would be useful in the comments, especially for trees or operation sequences.