PROBLEM LINK:
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.