Up and Down
Time limit8sMemory limit512 MB
Count permutations of 1..N whose up-sequence and down-sequence (nearest larger/smaller distance to the right) match the given arrays; N is at most 17.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Backtracking, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
A permutation of the set of numbers {1, . . . , N} is a reordering of these numbers in which each number appears exactly once. For a permutation we define its up-sequence and down-sequence as follows.
- Up-sequence [u1, . . . , uN]: ui is the smallest positive integer k such that ai < ai+k. If no such number exists, then ui = N + 1 − i.
- Down-sequence [d1, . . . , dN]: di is the smallest positive integer k such that ai > ai+k. If no such number exists, then di = N + 1 − i.
For example, for the permutation [1, 4, 3, 2, 6, 5], the up-sequence is [1, 3, 2, 1, 2, 1] and the down-sequence is [6, 1, 1, 3, 1, 1].
In general, more than one permutation shares the same up-sequence and down-sequence. For the example above, the permutations [1, 5, 4, 2, 6, 3] and [1, 5, 3, 2, 6, 4] share the same up-sequence and down-sequence.
You must count the number of permutations corresponding to a given up-sequence and down-sequence.
Input
The input consists of a series of data sets.
Each set has three lines. The first line contains a positive integer N (N ≤ 17). The next two lines contain N integers each; the first of these lines is an up-sequence and the second is a down-sequence. The integers are separated by spaces.
The input ends with a line containing a single zero. This line is not processed.
Output
For each set, print one line with the number of possible permutations corresponding to the given up-sequence and down-sequence.