PossibleOrders
SRM 154 · 2003-07-09 · by brett1479
SRM 154 · 2003-07-09 · by brett1479 · Dynamic Programming
Problem Statement
Problem Statement
Suppose you have num different objects and have been given some information about their ordering. The information will be given as a String[] facts whose elements will be of the form "A=B" where A and B are integers between 0 and num-1 inclusive. "0=8" means the 0th object is equal to the 8th object. Given these facts you will return the total possible number of distinct ways the objects could be ordered. For example:
num = 4
facts = {"0=2","1=3"}
Possible orderings: 0=2<1=3, 1=3<0=2, 0=1=2=3
In this case there are 3 possible orderings, so you would return 3. If no facts were given, there would be 75 possible orderings. As seen above, the orderings described here are total orderings. This means, for all pairs of objects, the ordering is specified (one is less than the other, or they are equal). Two orderings are the same if all pairs of objects in each ordering have exactly the same relationship.
num = 4
facts = {"0=2","1=3"}
Possible orderings: 0=2<1=3, 1=3<0=2, 0=1=2=3
In this case there are 3 possible orderings, so you would return 3. If no facts were given, there would be 75 possible orderings. As seen above, the orderings described here are total orderings. This means, for all pairs of objects, the ordering is specified (one is less than the other, or they are equal). Two orderings are the same if all pairs of objects in each ordering have exactly the same relationship.
Constraints
- facts will contain between 0 and 50 elements inclusive
- num will be between 2 and 17 inclusive
- Each element of facts will be formatted as (quotes for clarity) "A=B" where A and B are integers between 0 and num-1 inclusive A and B will have no extra leading zeros
Examples
0)
4
{"0=2","1=3"}
Returns: 3
From above.
1)
4
{}
Returns: 75
No facts.
2)
3
{"1=1"}
Returns: 13
Useless fact.
3)
3
{"1=2","2=1"}
Returns: 3
Redundant facts.
4)
5
{}
Returns: 541
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PossibleOrders with a public method long long howMany(int num, vector<string> facts) · 96 test cases · 2 s / 256 MB per case