Last Updated: 14 Sep, 2021
Number of Ways to Build Empire
Hard
Asked in company
The King is on a quest to conquer the entire world.
There are ‘N’ kingdoms in the world numbered from 0 to N-1. Each kingdom can only be reached from exactly one of the other kingdoms, except the ‘0th’ kingdom where the King lives. Also, it is possible to reach all other kingdoms from the 0th kingdom.
That is, the world is made up of a network of kingdoms in form of a tree rooted at zero. You are given an array ‘prevKingdom’ denoting that the ith kingdom can only be reached from the ‘prevKingdom[i]th’ kingdom, and prevKingdom[0] = -1.
The King initially lives in the 0th kingdom, but he wants to conquer all other kingdoms; he can only conquer a kingdom if all other kingdoms lying on the shortest path to the 0th kingdom have already been conquered.
Find the number of ways in which the King can conquer the entire world. As this number can be very big, return its modulo 109+7.
Note :
Two ways of conquering the world are considered different if the order in which the king conquered the kingdoms from 1 to N-1 are different. Refer to the example below for a better understanding.
For Example :
If N = 4, prevKingdom = { -1, 0, 0, 1 } , then the network of kingdoms is denoted as:
Then the King has 3 ways to conquer the world:
0 -> 1 -> 2 -> 3
0 -> 1 -> 3 -> 2
0 -> 2 -> 1 -> 3
All these 3 ways satisfy the constraint that before conquering any kingdom all the kingdoms on the shortest path to the 0th kingdom have been conquered, in other words: before conquering kingdom-3 the King must conquer kingdom-1.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the number of kingdoms.
The next line contains N integers, ‘prevKingdom[i]’ denoting that the ith kingdom can only be reached from the prevKingdom[i]^th kingdom.
Output Format :
For each test case, print a single integer denoting the number of ways the King can conquer the world.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
0 <= N <= 10000
0 <= prevKingdom[i] < N, and prevKingdom[0] = -1
Time limit: 1 sec
Approaches
This problem simply wants us to find the number of topological orderings of a directed tree rooted at 0.
Consider a case :
Where we have already precalculated answers for the subtree rooted at nodes 1 and 2.
- We have already calculated the ways to order nodes of the subtree rooted at nodes 1 and 2. Nodes numbered as 0 will always be visited before any of the nodes in the subtrees. So the answer of the tree rooted at 0 will be calculated by combining the answer of the subtree rooted at nodes 1 and 2.
- Let the ordering of subtree 1 be represented by an array1 of size equal to n1 and ordering of subtree 2 be represented by an array2 of size equal to n2, we can now simply combine array1 and array2 with a constraint that the relative ordering of elements in the original array1 should be not be changed and the same is applied for array 2 also. The number of different orderings we can achieve after combining two fixed arrays will be equal to (n1 + n2)! / ( (n1)! * (n2)! ).
- Now let us move a step further, if we know that we can arrange the elements in array1 in p1 ways and we can arrange the elements in array2 in p2 ways, then after combining array1 and array2, then we can say that the number of different ordering is equal to p1 * p2 * ( (n1 + n2)! / ( (n1)! * (n2)! ) ). This happens because after doing step-2, we can just internally permute elements of array1 in p1 ways and elements of array2 in p2 ways.
- After understanding the logic of combining two child nodes, we can extend the logic to multiple children: Simply start by taking any two children and combine them, now consider this combined result as a new child and combine all other remaining children with this result one by one.
After understanding this logic the question can simply be tackled by the dfs-algorithm.
Do note that some languages might require you to do inverse modulo calculations. Using Fermat's little theorem we can directly calculate the value of ( (a*b-1) % p ) as:
( a * ( b (p - 2) % p ) ) % p )
The steps are as follows :
- Precalculate the factorial of all numbers up to ‘N’.
- Initialize “adj” to store the tree in form of an adjacency list.
- Do depth-first search traversal by making an initial call from the root node. DFS call returns the answer and the number of nodes for the subtree rooted at the current node.
- If you reach a leaf node then return {1, 1}.
- Initialize “p” and “cnt” to store permutations and the number of nodes for the subtree rooted at the current node. Traverse all the child nodes and use the formula discussed above to calculate “p”. For each traversal update “cnt” so that it finally stores the number of nodes in the subtree.
- Finally, return the answer calculated for the root node.