Count All Valid Pickup and Delivery Options
Hard · Dynamic Programming · Math · Dynamic Programming · Combinatorics
Problem
A courier handles n orders. Order i has two events: a pickup P_i and a delivery D_i. A route lists all 2n events in some order.
A route is valid when every order is delivered after it is picked up. Orders can interleave freely: P1 P2 D1 D2 is valid, D1 P1 ... is not.
Return the number of valid routes, modulo 10^9 + 7.
Examples
Input: n = 3 Output: 90
Of the 6! = 720 orderings of six events, each order is the right way round half the time: 720 / 2³ = 90.
Input: n = 2 Output: 6
P1 P2 D1 D2, P1 P2 D2 D1, P1 D1 P2 D2, P2 P1 D1 D2, P2 P1 D2 D1 and P2 D2 P1 D1.
Input: n = 1 Output: 1
The only valid route is P1 D1.
Constraints
- 1 <= n <= 500
Approaches
- Baseline: count by what is still to do — time O(n²), space O(n²)
Follow-up
The product equals (2n)! / 2^n: of all (2n)! orderings, each order is the right way round in exactly half. The use cases change the shape of an order: three steps that must happen in sequence, and pickups that must also follow the order numbers.
Related problems
Start free on Cariara · Coding problems · System design studio
