TopCoder problem "RaceOrdering" used in SRM 371 (Division I Level Three)



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

0)
    
3
{1}
{2}
Returns: 3
Contestant 1 beat contestant 2, so the valid orders are 012, 102 and 120.
1)
    
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.
2)
    
10
{1, 2, 3}
{2, 3, 1}
Returns: 0
There is no way to satisfy this cycle.
3)
    
30
{}
{}
Returns: 90317

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7703

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10787&pm=7703

Writer:

bmerry

Testers:

PabloGilberto , Yarin , ivan_metelsky

Problem categories:

Dynamic Programming, Graph Theory, Simple Math