---
title: 'Problem Reading and Constraint Analysis'
source: 'https://academia.sh/en/courses/advanced-algorithms/problem-reading-and-constraint-analysis'
course: 'Advanced Algorithms and Problem Solving'
language: en
updated: '2026-08-17T18:07:27+00:00'
license: 'CC BY-SA 4.0'
---

# Problem Reading and Constraint Analysis

Deriving a step budget from input size, and measuring that the budget alone cannot select the pattern: at n=12 the sorting pattern is 1.61 times costlier than the oracle, and a wrong constraint reading gives a wrong answer on 18 of 40 inputs.

The previous topic worked with named problems: the knapsack, the traveling salesman, n
queens. The shape of these problems was given; the question asked was which approach
solved them. In practice the situation is reversed. There is a piece of text in hand, a
few numbers appear inside it, and which pattern is suitable is never stated. What
selects the pattern is not the problem's name but its **constraints**.

This lesson turns constraint reading into a procedure and measures where that procedure
works and where it turns into guessing. The result runs two ways: input size genuinely
eliminates large families of solutions, but it does **not** choose among the ones that
remain — and when a constraint is misread, the solution that emerges can be the
cheapest of all of them, and still be wrong.

## From Input Size to a Step Budget

Constraint reading is a single calculation: the largest input size in the problem text
is taken, an upper bound is placed on the number of steps that can be spent at that
size, and each candidate solution's fit within that bound is computed. The bound is
called the **step budget**. Asymptotic notation itself was built in the Algorithm
Analysis topic of the Algorithms course and is not repeated here; what happens here is
turning the notation into a **decision criterion**.

- **AD1** — The step budget is the most steps a solution can spend and still count as
  acceptable. In this lesson the budget is **10<sup>8</sup> steps** and is taken as a
  constant.
- **AD2** — The budget is computed over the **worst case**. An average input does not
  enter the calculation; the purpose of the calculation is to eliminate a solution, not
  to praise one.
- **AD3** — A lookup in a hash table is one step, an insertion is one step. Both are
  constant.
- **AD4** — A sort's step count is the actual number of **comparisons made**, and it is
  measured by counting them. The sorting algorithms themselves were built in the
  Algorithms course and are used here.
- **AD5** — The worst-case input is produced like this: every value is even, the target
  is odd. Then no pair can give the target, and every solution is forced to run to the
  end.

The problem is this: does an array contain **two distinct positions whose sum equals
the target**. There are three candidates. Brute force tries every pair; it is this
course's oracle. The second candidate sorts the array and scans it with two pointers.
The third keeps a hash table in a single pass.

```python
"""How the step count of three solutions to the same problem behaves on the worst-case input."""
from functools import cmp_to_key

SEED = 20260218


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


class Counter:
    def __init__(self):
        self.step = 0

    def count(self, n=1):
        self.step += n


def worst_case_input(n, seed=SEED):
    """All values even, target odd: no pair can give the target."""
    array = [2 * i for i in range(n)]
    r = generator(seed)
    for i in range(n - 1, 0, -1):
        j = r(i + 1)
        array[i], array[j] = array[j], array[i]
    return array


def oracle_pairs(array, target, s):
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.count()
            if array[i] + array[j] == target:
                return True
    return False


def pattern_sort_two_pointer(array, target, s):
    def compare(a, b):
        s.count()
        return -1 if a < b else (1 if a > b else 0)
    sorted_array = sorted(array, key=cmp_to_key(compare))
    left, right = 0, len(sorted_array) - 1
    while left < right:
        s.count()
        total = sorted_array[left] + sorted_array[right]
        if total == target:
            return True
        left, right = (left + 1, right) if total < target else (left, right - 1)
    return False


def pattern_hash_table(array, target, s):
    seen = set()
    for x in array:
        s.count()
        if target - x in seen:
            return True
        s.count()
        seen.add(x)
    return False


print("n      brute force   sort+two pointer   hash table")
for n in (4, 8, 32, 128, 512, 2048):
    d = worst_case_input(n)
    s1, s2, s3 = Counter(), Counter(), Counter()
    oracle_pairs(d, 7, s1)
    pattern_sort_two_pointer(d, 7, s2)
    pattern_hash_table(d, 7, s3)
    print(f"{n:5d}  {s1.step:11d}  {s2.step:19d}  {s3.step:11d}")
print()
for ad, pattern in (("sort+two pointer", pattern_sort_two_pointer),
                    ("hash table      ", pattern_hash_table)):
    for n in range(2, 40):
        d = worst_case_input(n)
        s1, s2 = Counter(), Counter()
        oracle_pairs(d, 7, s1)
        pattern(d, 7, s2)
        if s2.step < s1.step:
            print(f"{ad} first n where it beats brute force: {n}"
                  f"  (pattern {s2.step} , oracle {s1.step})")
            break
```

```
n      brute force   sort+two pointer   hash table
    4            6                   10            8
    8           28                   22           16
   32          496                  152           64
  128         8128                  861          256
  512       130816                 4483         1024
 2048      2096128                22015         4096

sort+two pointer first n where it beats brute force: 8  (pattern 22 , oracle 28)
hash table       first n where it beats brute force: 6  (pattern 12 , oracle 15)
```

The table's first row is constraint reading's most overlooked result: at n=4, **brute
force is the cheapest of the three solutions** — 6 steps, against the hash table's 8 and
the sorting pattern's 10. The sorting pattern only becomes cheaper than the oracle at
**n=8**, the hash table at **n=6**. Brute force is not a poor choice at small input
sizes; what is poor is choosing it without knowing at which size it stops being one.

## Budget Calculation at Four Input Sizes

The measurement above goes up to 2048, but constraint reading has to make a decision up
to 10<sup>8</sup>, and actually running brute force at that size is not an option. For
this reason the budget calculation is done **with a formula validated against the
measured count**: first it is checked whether the formula holds at small n, then the
formula is carried to large n.

- **AD6** — Brute force's worst-case step count is estimated as $n(n-1)/2$, the hash
  table's as $2n$, the sorting pattern's as $n\log_2 n + n$.
- **AD7** — A formula can be used in the budget calculation only **as long as it does
  not fall below** the measured step count. A formula that understates is not accepted.

```python
"""Does the estimate formula hold against the measured step count, and the budget
calculation at four input sizes."""
from math import log2

MEASURED = {8: (28, 22, 16), 32: (496, 152, 64), 128: (8128, 861, 256),
            512: (130816, 4483, 1024), 2048: (2096128, 22015, 4096)}
BUDGET = 10 ** 8


def estimate(n):
    return (n * (n - 1) // 2, int(n * log2(n)) + n, 2 * n)


print("n      brute force         sort+two pointer        hash table")
print("       measured  estimate  m/e   measured  estimate  m/e   measured  estimate")
for n, (a, b, c) in MEASURED.items():
    ta, tb, tc = estimate(n)
    print(f"{n:5d}  {a:7d}  {ta:6d}  {a / ta:.2f}  {b:8d}  {tb:6d}  {b / tb:.2f}"
          f"  {c:8d}  {tc:6d}")
print()
print(f"step budget: {BUDGET}")
print("n            brute force     sort+two pointer   hash table")
for n in (10 ** 3, 10 ** 5, 10 ** 6, 10 ** 8):
    ta, tb, tc = estimate(n)
    d = [("fits" if t <= BUDGET else "no fit") for t in (ta, tb, tc)]
    print(f"{n:<11d}  {ta:.2e} {d[0]:6s}  {tb:.2e} {d[1]:6s}  {tc:.2e} {d[2]:6s}")
```

```
n      brute force         sort+two pointer        hash table
       measured  estimate  m/e   measured  estimate  m/e   measured  estimate
    8       28      28  1.00        22      32  0.69        16      16
   32      496     496  1.00       152     192  0.79        64      64
  128     8128    8128  1.00       861    1024  0.84       256     256
  512   130816  130816  1.00      4483    5120  0.88      1024    1024
 2048  2096128  2096128  1.00     22015   24576  0.90      4096    4096

step budget: 100000000
n            brute force     sort+two pointer   hash table
1000         5.00e+05 fits    1.10e+04 fits    2.00e+03 fits  
100000       5.00e+09 no fit  1.76e+06 fits    2.00e+05 fits  
1000000      5.00e+11 no fit  2.09e+07 fits    2.00e+06 fits  
100000000    5.00e+15 no fit  2.76e+09 no fit  2.00e+08 no fit
```

The top table confirms the formula. For brute force, measured and estimated are
**identical** (ratio 1.00); the same for the hash table. For the sorting pattern the
ratio **rises** from 0.69 to 0.90: the formula overstates the true comparison count at
every n, that is, it errs on the safe side, satisfying AD7. The amount of overstatement
is not constant — at small n the estimate is 1.45 times the measurement, at n=2048 it is
1.12 times. **This is the point where constraint reading turns into guessing:** the
formula used carries a coefficient, and until that coefficient is measured, the budget
calculation is a guess.

The bottom table is the four sizes this lesson asked for. At n=1,000, **all three
solutions** fit the budget; constraint reading eliminates nothing here, and the choice
is left to another criterion. At n=100,000, brute force is eliminated at 5.00·10<sup>9</sup>
steps, leaving two candidates. At n=1,000,000 the table stays the same. At
n=10<sup>8</sup>, **none of the three fit** — even the hash table, the cheapest, asks
for 2.00·10<sup>8</sup> steps, twice the budget. This last row is constraint reading's
most useful output: if not even a single-pass solution fits at that size, the problem
text must be giving **another constraint**, and it has not been read.

## When a Constraint Is Misread

The entire calculation above assumed one thing: that all three candidates give the
correct answer. Until that assumption is tested, the budget calculation cannot select a
solution. The course's rule applies here as well — **a pattern whose precondition is
not tested against the oracle is not considered measured.**

A fourth candidate is added. Someone who thinks the problem text says "values do not
exceed 20" can keep an array marking the range 0..20 and answer in a single pass. What
was missed is that the text does not state a lower bound, and values can be negative.

- **AD8** — The corpus is the shared reference's corpus: 40 inputs, each with 12 values,
  values ranging from −9 to 20. The target is 11.
- **AD9** — The wrong constraint reading **silently skips** an out-of-range value; it
  does not crash, it returns an answer.
- **AD10** — The second corpus is produced with seed `20260219`, and whether the
  diverging-input ratio stays in the same order of magnitude is written down.

```python
"""The budget calculation does not choose the pattern, the oracle does. Two corpora."""
from functools import cmp_to_key

SEED, SECOND, LENGTH, CORPUS_SIZE = 20260218, 20260219, 12, 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


class Counter:
    def __init__(self):
        self.step = 0

    def count(self, n=1):
        self.step += n


def corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH):
    r = generator(seed)
    return [{"no": i + 1, "array": [r(30) - 9 for _ in range(length)]}
            for i in range(n)]


def oracle_pairs(array, target, s):
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.count()
            if array[i] + array[j] == target:
                return True
    return False


def pattern_sort_two_pointer(array, target, s):
    def compare(a, b):
        s.count()
        return -1 if a < b else (1 if a > b else 0)
    sorted_array = sorted(array, key=cmp_to_key(compare))
    left, right = 0, len(sorted_array) - 1
    while left < right:
        s.count()
        total = sorted_array[left] + sorted_array[right]
        if total == target:
            return True
        left, right = (left + 1, right) if total < target else (left, right - 1)
    return False


def pattern_hash_table(array, target, s):
    seen = set()
    for x in array:
        s.count()
        if target - x in seen:
            return True
        s.count()
        seen.add(x)
    return False


def pattern_counting_array(array, target, s, upper=20):
    """WRONG CONSTRAINT READING: values are assumed to be in the range 0..upper."""
    present = [False] * (upper + 1)
    for x in array:
        s.count()
        if 0 <= x <= upper:
            complement = target - x
            if 0 <= complement <= upper and present[complement]:
                return True
            present[x] = True
    return False


def measure(pattern, items, target):
    diverging, pattern_steps, oracle_steps = [], 0, 0
    for k in items:
        s1, s2 = Counter(), Counter()
        a = pattern(k["array"], target, s1)
        b = oracle_pairs(k["array"], target, s2)
        pattern_steps, oracle_steps = pattern_steps + s1.step, oracle_steps + s2.step
        if a != b:
            diverging.append(k["no"])
    return {"diverging": len(diverging), "first_diverging": diverging[:5],
            "pattern_step": pattern_steps, "oracle_step": oracle_steps}


for seed in (SEED, SECOND):
    print(f"corpus seed {seed} , 40 inputs x 12 values , target 11")
    K = corpus(seed)
    for ad, pattern in (("sort+two pointer", pattern_sort_two_pointer),
                        ("hash table          ", pattern_hash_table),
                        ("counting (wrong constraint)", pattern_counting_array)):
        print(f"  {ad}", measure(pattern, K, 11))
    print()
```

```
corpus seed 20260218 , 40 inputs x 12 values , target 11
  sort+two pointer {'diverging': 0, 'first_diverging': [], 'pattern_step': 1398, 'oracle_step': 866}
  hash table           {'diverging': 0, 'first_diverging': [], 'pattern_step': 486, 'oracle_step': 866}
  counting (wrong constraint) {'diverging': 18, 'first_diverging': [4, 10, 13, 14, 15], 'pattern_step': 396, 'oracle_step': 866}

corpus seed 20260219 , 40 inputs x 12 values , target 11
  sort+two pointer {'diverging': 0, 'first_diverging': [], 'pattern_step': 1441, 'oracle_step': 970}
  hash table           {'diverging': 0, 'first_diverging': [], 'pattern_step': 566, 'oracle_step': 970}
  counting (wrong constraint) {'diverging': 17, 'first_diverging': [3, 4, 6, 7, 8], 'pattern_step': 391, 'oracle_step': 970}
```

Three numbers side by side. **Oracle:** 866 steps, correct on 40 of 40 inputs.
**Patterns:** the hash table 486 steps, the sorting pattern 1398 steps, the wrong
constraint reading 396 steps. **Diverging inputs:** **0** for the first two, **18** for
the wrong reading — that is, a different answer than the oracle on 18 of 40 inputs, a
ratio of **0.4500**.

The result says two things. First, **step-count ranking is not correctness ranking**:
the candidate that spends the fewest steps (396) is exactly the one that gives the wrong
answer. Second, at n=12 the sorting pattern is **1.61 times costlier** than the oracle
(1398 against 866). The budget calculation had selected this pattern for large n; at the
actual input size of 12, that same choice is worse than the oracle. The budget
calculation is a tool for **elimination**, not a tool for selection.

The second corpus confirms the result: diverging inputs drop from 18 to 17 (ratio
0.4250), staying in the same order of magnitude; the two correct patterns give 0
diverging inputs there as well. The shared reference's first reading had already shown
two pointers to be wrong on 25 of 40 inputs on an unsorted input; the 18 here is the
**constraint-reading** side of the same rule — the pattern is correct, the reading is
not.

## Summary

- Constraint reading is the operation of deriving a **step budget** from input size and
  eliminating candidates with it; in this lesson the budget is 10<sup>8</sup> steps and
  the calculation is always done over the worst case.
- Measurement vindicates brute force at small input: at n=4, the cheapest of the three
  solutions is brute force with 6 steps; the hash table only beats it at n=6, the
  sorting pattern at n=8.
- The budget leaves a different number of candidates at four sizes: at n=1,000 all
  three fit, at n=100,000 and n=1,000,000 brute force is eliminated, at
  n=10<sup>8</sup> **none** fit — even the hash table asks for 2.00·10<sup>8</sup> steps.
- Until a formula is validated against measurement, the budget calculation is a guess:
  for the sorting pattern the estimate is 1.45 times the measurement at n=8, 1.12 times
  at n=2048; for brute force and the hash table the ratio is exactly 1.00.
- Comparison against the oracle says what the budget calculation cannot: the candidate
  spending the fewest steps (396 steps) gives the wrong answer on **18 of 40** inputs,
  17 on the second corpus; the two correct patterns give 0 diverging inputs on both
  corpora.
- At the real input size, budget ranking can reverse: at n=12 the sorting pattern is
  1.61 times costlier than the oracle. The budget calculation eliminates, it does not
  select.

## Next Step

In this lesson the oracle was used once, and it caught a wrong constraint reading on 18
inputs. But those 18 inputs came from a corpus already in hand; a different corpus
would have caught a different number. The next lesson takes up exactly this dependency:
**which inputs** should a solution be compared against the oracle on, how many times do
edge cases show up in a randomly generated corpus, and once a diverging input is found,
how is it shrunk down to its smallest form. The measure remains a count: how many of
the deliberately broken versions are caught by which corpus.