×

# MRO - Editorial

Author: Vaibhav Tulsyan
Tester: Misha Chorniy
Editorialist: Animesh Fatehpuria

# PROBLEM

Compute number of DAGs with $N$ nodes that satisfy the following properties:

• There is exactly $1$ source node numbered $1$. Let's call this constraint $A$.
• Nodes $2, 3, \cdots, N$ are reachable from $1$. Let's call this constraint $B$.
• $[1, 2, 3, \cdots, N]$ is a valid topological order of the DAG. Let's call this constraint $C$.

Two ways are different if at least one node has a different set of ancestors.
Constraint: $1 \le N \le 10^5$.

# EXPLANATION

One 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 graph-theoretic 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:

• $E = \{1 \rightarrow 2, 2 \rightarrow 3\}$
• $E = \{1 \rightarrow 2, 1 \rightarrow 3\}$
• $E = \{1 \rightarrow 2, 1 \rightarrow 3, 2 \rightarrow 3\}$

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)$:

• It's a valid DAG with $N - 1$ nodes.
• All nodes are reachable from $1$. (Constraint $B$ is satisfied)
• $[1, 2, 3, \cdots, N - 1]$ is a valid topological order. (Constraint $C$ is satisfied)

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:

pw2[0] = 1; // Precompute Powers of 2
for (int i = 1; i < MAXN; ++i) {
pw2[i] = pw2[i - 1] * 2 % MOD;
}
f[1] = 1; // Precompute f(n) using the recurrence derived above
for (int i = 2; i < MAXN; ++i) {
f[i] = 1LL * f[i - 1] * (pw2[i - 1] + MOD - 1) % MOD;
}
int t; cin >> t;
while (t--) {
int n; cin >> n;
cout << f[n] << endl; // Answer each test case in O(1)
}


# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

19.6k349497539
accept rate: 35%

 0 Is it possible to write the answer in python without exceeding the time limit. def perms(): for i in range(2, 10**5): p.append((p[i-1]*2 + 1) % mod) f.append(f[i-1]*p[i-1] % mod) mod = 1000000007 p = [0, 1] f = [None, 1] for t in range(int(input())): n = int(input()) perms() print(f[n])  Even this short code is exceeding the time limit. answered 16 Aug, 13:26 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,182
×3,673
×2,020
×75
×14
×4

question asked: 28 Dec '17, 14:42

question was seen: 555 times

last updated: 20 Feb, 16:49