PROBLEM LINK:Author: Vaibhav Tulsyan PROBLEMCompute number of DAGs with $N$ nodes that satisfy the following properties:
Two ways are different if at least one node has a different set of ancestors. EXPLANATIONOne of the most important parts to solving this problem is parsing the problem statement carefully and reducing it to the problem mentioned above. Reduction to the graphtheoretic version makes the problem much more tractable. I'll provide some intuition about how to go about this problem before describing the formal approach. It's always a good idea to doodle on paper for problems like these to gain more insight. It's clear that for $N = 1$, the answer is $1$. For $N = 2$, the answer will also be $1$ in order to satisfy constraint $B$. For $N = 3$, the answer is $3$, as we can have the following DAGs defined by these set of edges:
Now let's search for some recursive structure. Since we want to satisfy constraint $C$, we can consider adding the nodes one by one from $1, 2, \cdots, N$, ensuring at each step that we satisfy constraint $B$. Note that adding in this natural order is key here as it implicitly handles constraint $C$. Define $f(n)$ to be the number of valid DAGs with $n$ nodes. How can we relate $f(n)$ to $f(n  1)$? To answer this, first lets recap what we know about the DAGs considered by $f(n  1)$:
How can we extend these DAGs to valid DAGs with $N$ nodes? It turns out that this is quite simple to do. We just need to add an edge from at least one node from the set $\{1, 2, 3, \cdots, N  1\}$ to $N$ in order to satisfy both properties $B$ and $C$. The number of ways to do this is equal to the number of nonempty subsets of $\{1, 2, 3, \cdots, N  1\}$ which is given by $2^{N  1}  1$. Therefore, the recurrence we're looking for is $f(n) = f(n  1) \cdot (2^{N  1}  1)$. That's it! We now have the simplest of recurrences for $f(n)$, and we can precompute them using DP in $O(n)$ time, and then answer each test case in $O(1)$. The code will look as follows:
AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 28 Dec '17, 14:42

Is it possible to write the answer in python without exceeding the time limit.
Even this short code is exceeding the time limit. answered 16 Aug, 13:26
