2
$\begingroup$

I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.

https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum

Problem description:

Nikita has a family tree $T$ consisting of $N$ members number from $1$ to $N$. Each of the $N-1$ edges in the tree represents a directed relationship. Basically if there is an edge from member $A$ to $B$, it means $B$ was born before $A$. Now, Nikita knows that these $N$ members were born in last $M$ days and only $1$ person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the $N$ family members.

Since the required answer can be quite large, print it modulo $10^9+7$.

Editorial:

By now, you might have got the problem is all about finding the number of topological sortings in the randomly directed tree $T$.

Let randomly root the tree $T$ at any node say $1$. Lets calculate a $dp(i, j)$ denoting the number of topological sorts of subtree rooted at $i^{th}$ node such that $i^{th}$ node is placed at position. Assume that there are $X$ outgoing edges to the children from and $Y$ incoming edges. Note that all the $X$ children has to be placed on the left and all the $Y$ children has to be placed on the right side of $i^{th}$ in a valid topological sort.

Now lets calculate another $dp(i, j)$ for those $X$ nodes. Similiarly, we will do for $Y$ nodes. Here $dp(i, j)$ denotes the number of ways of filling $j$ spaces using topological sorts of subtrees rooted at $X_1, X_2, \cdots X_i$ such that $X_1, X_2, \cdots X_i$ is placed in $j$ spaces. Note that to compute this $dp$, we can use the $DP$ already calculated at these children nodes.

$$dp(i, j) = \sum_{1 \le k \le |S_i|} \left( nCr(j, k) \times dp(i-1, j-k) \times \sum_{1\le l \le k} DP(i, l) \right)$$

Note that this $\sum_{1\le l \le k} DP(i, l)$ is just a prefix sum and can be precomputed.

Now, for $X$ nodes basically you have computed $dp_j$, number of filling up $j$ spaces using subtrees of $X$ nodes such that $X_1, X_2, \cdots X_x$ is included. Lets call this $dp$ as $left[]$ and similary call the $dp$ for $Y$ nodes as $right[]$.

$$DP(i, j) = \sum_{1\le k < j} nCr(j-1, k) \times {left}_k \times nCr(a, b) \times {right}_{a-b}$$

Where $a = SZ_i - j$, $b = SZ_x - k$ and $SZ_i$ denotes the size of subtree rooted at $i^{th}$ node & $SZ_x$ denotes the sum of sizes of all subtrees rooted at all those $X$ nodes.

In the editorial section, it is claimed that the time complexity of the solution is $O(N^2)$. However, the problem is actually about finding all the topological sortings of a DAG, which to my knowledge is a NP-hard problem.

I believe that the added constraint that the number of edges is equal to $N-1$ simplifies the solution, and I couldn't think of any other possibility.

Could anyone kindly validate the solution?

$\endgroup$
1
$\begingroup$

First, the problem is about counting, not finding, all the topological sorts (though it is still hard for general DAGs). Second, the constraint that the graph is a tree makes this problem much simpler.

Consider a node $n$ with $k$ children $n_1,\ldots,n_k$. Suppose the subtrees rooted by $n_1,\ldots,n_k$ are respectively $T_1,\ldots,T_k$, the sizes of $T_1,\ldots,T_k$ are respectively $s_1,\ldots,s_k$, and the numbers of topological sorts of the members in $T_1,\ldots,T_k$ are respectively $c_1,\ldots,c_k$, then the number of topological sorts of the members in the tree rooted by $n$ is

$$\frac{(n_1+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}c_1c_2\cdots c_k.$$

Using the formula above, you can compute the number of topological sorts of the members in each subtree from bottom to top. This results in an $O(N^2)$ algorithm.

$\endgroup$
  • 1
    $\begingroup$ The formula that you have given works only for trees in which EVERY NODE HAS ONLY ONE PARENT. However, in this case, there could be multiple parents of a single node. I think what the question-setter means by trees is that there is at most one directed path between any two nodes. There is a test case in which a node is shown to have multiple parents. $\endgroup$ – Siddharth Joshi Sep 13 '18 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.