You are not logged in. Please login at www.codechef.com to post your questions!

×

MRO - Editorial

1
1

PROBLEM LINK:

Practice
Contest

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".

asked 28 Dec '17, 14:42

admin's gravatar image

0★admin ♦♦
19.6k349497539
accept rate: 35%

edited 20 Feb, 16:49


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.

link

answered 16 Aug, 13:26

patadi123's gravatar image

0★patadi123
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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