Counting clearance charts

A customs desk finds a tariff band by asking higher-or-lower a few times. How many different charts of questions can the desk be given?

The problem

A port's tariff has bands bands, numbered 1 upward in increasing order of duty. A clearance chart is built from checks. One check is at the top; every check names a band, and has at most two checks under it, one for declarations below its band and one for declarations above. Each band names exactly one check in the chart.

The chart must agree with the numbering: every band under a check's below side is lower than that check's band, and every band under its above side is higher. That is what lets a clerk find a band by following the answers instead of reading the whole chart.

Count the charts. Two charts differ when some position holds a different band, or when one has a check where the other has nothing.

Input. bands — the number of tariff bands.

Output. The number of distinct charts, as an integer.

Example.

bands = 3   ->  5

Band 2 on top gives one chart, with 1 below and 3 above. Band 1 on top leaves 2 and 3 above it, which stack two ways. Band 3 on top leaves 1 and 2 below it, also two ways. That is 1 + 2 + 2.

A second example, to show how fast this grows:

bands = 4    ->  14
bands = 19   ->  1767263190

Each extra band multiplies the count by roughly four. bands = 0 is the empty chart: one way to build nothing.

Constraints.

• 0 <= bands <= 19
• The answer fits in a 64-bit integer

Hints

Approach

Brute force

Build the charts and count what you built. There is no waste in the enumeration — every chart is distinct — so the work equals the answer: at 19 bands, 1.7 x 10^9 charts, each one allocated and thrown away.

The insight

Fix the top check and the ordering rule does the rest: if it names the k-th band, the k - 1 lower bands all sit below it and the rest above, so the charts with that band on top number one smaller count times another.

The two sides never interact. Any chart over the lower run can be paired with any chart over the upper run, which is a product, and summing over the choice of top band gives the total. Then the precondition that makes this cheap: a run of consecutive bands admits a number of charts that depends only on its length, not its values, because the ordering rule constrains the run internally in exactly the same way wherever it sits. So one array indexed by length, not by which bands.

Algorithm

1. Make charts of length bands + 1, and set charts[0] = 1.
2. For each size from 1 to bands:
3. For each below from 0 to size - 1, meaning below bands under the top check on the low side and size - 1 - below on the high side:
4. Add charts[below] * charts[size - 1 - below] to a running total.
5. Store that total in charts[size].
6. Return charts[bands].

Complexity

Time O(n^2) — one inner pass per size, of length that size, so about n^2 / 2 multiplications: 180 of them at n = 19. Space O(n) for the single array.

Solution

"""Counting clearance charts — fix the top band, then multiply the two sides."""


def solve(bands):
    # charts[size] counts the distinct charts over `size` consecutive bands.
    # Only the size matters, never which bands they are: the ordering rule sends
    # every lower band left and every higher band right, so two runs of equal
    # length admit exactly the same charts.
    charts = [0] * (bands + 1)
    charts[0] = 1                      # no bands: one chart, and it is the empty one
    for size in range(1, bands + 1):
        total = 0
        for below in range(size):      # `below` bands under the top check, size-1-below above
            total += charts[below] * charts[size - 1 - below]
        charts[size] = total
    return charts[bands]

TESTS = [
    ((3,), 5),
    ((4,), 14),
    ((1,), 1),
    ((2,), 2),
    ((0,), 1),
    ((10,), 16796),
    ((19,), 1767263190),
]

Pitfalls

• Setting charts[0] = 0. Every product then has a zero factor whenever a side is empty, and the whole table collapses to zero. An empty side has one arrangement, which is to put nothing there.
• Counting the orders bands could be filed in rather than the charts. Three bands have six orders but five charts: filing 2, 1, 3 and filing 2, 3, 1 build the same chart, so the six over-counts by one.
• Recursing on the formula with no table. The recursion recomputes the same lengths over and over and makes as many calls as there are charts — 1.7 x 10^9 at 19 bands, for a table with 20 entries in it.

Variants

• The BST invariant — the ordering rule this count rests on, and what it buys when a clerk uses the chart.
• The same unit, already there — shape again, compared between two charts rather than counted.