RaceOrdering
SRM 371 · 2007-10-13 · by bmerry
SRM 371 · 2007-10-13 · by bmerry · Dynamic Programming, Graph Theory, Simple Math
Problem Statement
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.
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
4)
2
{0}
{1}
Returns: 1
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RaceOrdering with a public method int countOrders(int n, vector<int> first, vector<int> second) · 65 test cases · 2 s / 256 MB per case