VampireTreeDiv2
SRM 674 · 2015-11-03 · by FatalEagle
Problem Statement
You are a genealogist specializing in family trees of vampires. Vampire family trees differ from human family trees. In particular, there are two ways how a vampire can be "born":
- A living human can be turned into a vampire (the technical term here is "sired") by an existing vampire. In this case we call the older vampire the master and the newly created vampire the servant of that master.
- Two existing vampires can have a vampire child. In this case we call the two original vampires parents and the new vampire their child. Note that there are no restrictions on the two parent vampires. In particular, their genders and their ancestry can be arbitrary. Any two vampires can have a child.
You are now studying one particular family of vampires. These vampires have all been created from a single vampire: the True Ancestor. This special vampire has no master and no parents. There are n vampires in the family. They are numbered 0 through n-1 in the order in which they were born, with vampire 0 being the True Ancestor.
You are given a description of the family tree in the
In this particular family it is pretty rare for two vampires to have a child. More precisely, there are at most 15 vampires with two parents each.
You would like to select a representative sample of vampires from this family. The sample must have the following properties:
- You need to select at least one vampire from each master/servant and also from each parent/child relationship.
- The total number of vampires in your sample must be as small as possible.
Find and return the number of ways in which you can select the sample, modulo 10^9+7.
Notes
- Please pay attention to the unusual time limit.
Constraints
- A will contain between 1 and 999 elements, inclusive.
- A and B will contain the same number of elements.
- There are no more than 15 elements of B that are not equal to -1.
- 0 <= A[i] <= i for all valid i.
- -1 <= B[i] <= i for all valid i.
- A[i] != B[i] for all valid i.
{0}
{-1}
Returns: 2
There are two vampires. The True Ancestor (vampire 0) is the master of vampire 1. As vampires 0 and 1 are in a master/servant relationship, we are required to select at least one of them. There are two valid samples. One of them is {0} and the other is {1}. The sample {0, 1} is not a valid sample because it contains too many vampires.
{0, 1}
{-1, 0}
Returns: 3
In this test case there are three vampires. As in Example 0, vampire 0 is the master of vampire 1. Then, vampires 1 and 0 are the parents of vampire 2. According to the problem statement: Vampires 0 and 1 are in a master/servant relationship, so we have to select at least one of them. Vampires 0 and 2 are in a parent/child relationship, so we have to select at least one of them. Vampires 1 and 2 are in a parent/child relationship, so we have to select at least one of them. Clearly, this means we have to select at least two vampires. On the other hand, we can easily verify that each of the 3 samples {0, 1}, {0, 2}, and {1, 2} is valid.
{0, 0, 2, 2}
{-1, -1, -1, -1}
Returns: 2
{0, 1, 2, 3}
{-1, -1, -1, -1}
Returns: 1
{0, 1, 1, 2, 1, 2, 2, 5, 7, 6, 5, 10, 6, 6, 12, 6, 6, 2, 8, 0, 16, 5, 8, 2, 14}
{-1, -1, -1, -1, 0, -1, -1, -1, 2, 7, 10, 11, 7, 9, -1, 5, -1, 15, 4, 7, 9, -1, 13, 6, 24}
Returns: 78
{0,1,0,3,0,5,0,7,0,9,0,11,0,13,0,15,0,17,0,19,0,21,0,23,0,25,0,27,0,29,0,31,0,33,0,35,0,37,0,39,0,41,0,43,0,45,0,47,0,49,0,51,0,53,0,55,0,57,0,59,0}
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
Returns: 73741818
The answer is 1073741825 mod 10^9+7 which is 73741818.
Submissions are judged against all 64 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class VampireTreeDiv2 with a public method int countMinSamples(vector<int> A, vector<int> B) · 64 test cases · 2 s / 256 MB per case