RaceOrdering | Topcoder Archive

Problem Statement

You are trying to predict the outcome of a race between n runners, numbered from 0 to n - 1.You are given two int[]s, first and second. It is guaranteed that for all i, the runner numbered first[i] will always beat the runner numbered second[i]. Determine how many final orderings are possible, modulo 1,000,003. If the information is contradictionary, return 0. Runners are never tied.

Definition

Class:: RaceOrdering
Method:: countOrders
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int countOrders(int n, int[] first, int[] second)
(be sure your method is public)

Constraints

n will be between 1 and 30, inclusive.
first and second will each contain between 0 and 15 elements, inclusive.
first and second will contain the same number of elements.
Each element of first and second will be between 0 and n - 1, inclusive.
first[i] does not equal second[i] for all i between 0 and m - 1, inclusive, where m is the number of elements in first and second.

Examples

```
3
```
```
{1}
```
```
{2}
```
```
Returns: 3
```
Contestant 1 beat contestant 2, so the valid orders are 012, 102 and 120.
```
4
```
```
{0, 0}
```
```
{1, 2}
```
```
Returns: 8
```
Contestant 0 beat contestants 1 and 2, but there is no information on contestant 3. The valid orderings are 3012, 3021, 0312, 0321, 0132, 0231, 0123 and 0213.
```
10
```
```
{1, 2, 3}
```
```
{2, 3, 1}
```
```
Returns: 0
```
There is no way to satisfy this cycle.
```
30
```
```
{}
```
```
{}
```
```
Returns: 90317
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.