The fly cue sheet

A stage manager is counting the cue sheets a show could legally have. Each set piece needs two cues, and one of them can never come first.

The problem

A theatre flies its scenery from the grid above the stage. Each set piece gets exactly two cues in the show: an in cue that lowers it to the deck, and an out cue that lifts it away. The crew calls one cue at a time, so a running order is a sequence of all 2 * pieces cues, and the only rule is that a piece's out cue must be called after its in cue. Nothing else is fixed: two pieces may hang together, or one may fly out before the next flies in.

The stage manager wants to know how many different cue sheets satisfy that rule. The count grows fast, so report it modulo 1000000007.

Input. pieces — an integer, the number of set pieces. Each contributes one in cue and one out cue.

Output. The number of valid cue sheets, taken modulo 1000000007.

Example.

pieces = 2   ->  6

Call the pieces A and B. The six sheets are A-in A-out B-in B-out, A-in B-in A-out B-out, A-in B-in B-out A-out, and the three mirror images that start with B. The four sheets where a piece leaves before it arrives are struck out.

A second example, showing the growth:

pieces = 3   ->  90

Six cues have 720 orderings; only 90 of them keep every piece in before out.

Constraints.

• 1 <= pieces <= 500
• The answer is reported modulo 1000000007

Hints

Approach

Brute force

Generate all (2 * pieces)! orderings of the cues and keep the ones that never lift a piece before it lands. At 5 pieces that is 3628800 sequences; at 10 it is 2.4 quintillion. Correct, and finished before you would like only for toys.

The insight

A sheet for k pieces is a sheet for k - 1 pieces with two new cues wedged in, and the two slots can be chosen in k * (2k - 1) ways — the order of the new pair is forced, so each choice of slots is exactly one sheet.

A sheet of k - 1 pieces has 2k - 2 cues and therefore 2k - 1 gaps around them. Placing two cues means picking two of the 2k positions in the new sheet, which is 2k * (2k - 1) / 2 = k * (2k - 1); the earlier position must take the in cue, so no choice is double counted and none is missed. Every valid sheet of k pieces yields a valid sheet of k - 1 when the new piece's cues are deleted, so the map is a bijection and the counts multiply.

Algorithm

1. Start with sheets = 1, the single sheet for one piece.
2. For k from 2 to pieces, multiply sheets by k * (2k - 1).
3. Reduce modulo 1000000007 at every step.
4. Return sheets.

Complexity

Time O(n) — one multiplication per piece, 500 of them at the top of the range. Space O(1); a single running product.

Solution

"""The fly cue sheet — counting DP that inserts one pair of cues at a time."""

MOD = 1000000007


def solve(pieces):
    # Invariant: `sheets` is the number of legal cue sheets for the first k
    # pieces. Adding piece k+1 means choosing 2 of the 2(k+1) slots in the new
    # sheet — k+1 choose-pairs times (2k+1) — and the earlier slot must be the
    # in cue, so each choice of slots is exactly one new sheet.
    sheets = 1
    for k in range(2, pieces + 1):
        sheets = sheets * k % MOD
        sheets = sheets * (2 * k - 1) % MOD
    return sheets

TESTS = [
    ((2,), 6),
    ((3,), 90),
    ((1,), 1),          # one piece: in then out, the only sheet
    ((5,), 113400),
    ((10,), 850728840), # past the modulus, so the reduction is exercised
    ((500,), 764678010),
]

Pitfalls

• Multiplying by 2k * (2k - 1). That counts an ordered pair of slots, so every sheet is counted twice and pieces = 2 comes back as 24. Halve it, or write the factor as k * (2k - 1).
• Taking the modulus only at the end. The unreduced product for 500 pieces has thousands of digits; in a fixed-width integer language it overflows silently and the answer is noise. Reduce inside the loop.
• Seeding the loop at sheets = 0. The empty product is 1, not 0, and a zero seed makes every answer zero.

Variants

• Terrace climbs — the other counting recurrence, where the step is an addition rather than a multiplication.
• Motif in the weave — counting arrangements again, but the state is two indices instead of one.