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

×

CL16BF - Editorial

PROBLEM LINK:

Practice
Contest

Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Soumik Sarkar

DIFFICULTY:

MEDIUM

PREREQUISITES:

Directed Acyclic Graph, Topological Sort, Dynamic Programming

PROBLEM:

Given a DAG (directed acyclic graph) with N nodes and M edges, the problem requires one to find the number of different paths that exist from a given node P to another node Q.

QUICK EXPLANATION:

The first step is to toposort the given graph. If dp[u] be the number of paths from node u to node Q. Then dp[u] = summation of dp[v] for all v for each edge directed from u to v. We obtain dp[u] for each node u in the graph in reverse topological order. Then dp[P] is the required answer.

EXPLANATION:

Let $f(u)$ be the number of ways one can travel from node $u$ to node $Q$. Naturally, $f(P)$ is our required answer. $f(Q) = 1$ here, since there is just one way of travelling from $Q$ to $Q$, by not moving! We can observe that $f(u)$ depends on nothing other than the $f$ values of all the nodes it is possible to travel to from $u$. This makes sense because the number of ways we can travel from $u$ to $Q$ is the sum of all the ways we can travel from $v_1$, $v_2$, $v_3$... $v_n$ to $Q$ where $v_1$ to $v_n$ are all the nodes that can be directly travelled to from node $u$. Thus we have the formulation $$ f(u) = \sum f(v) \, for\, all\, v\ \mid \ an\, edge\ u\, \rightarrow v\ exists$$

Thus, our trivial function would look something like

function f(u)
    if u equals Q
        return 1
    sum = 0
    for each edge u→v
        sum = sum + f(v)
    return sum

The check statement "u equals Q" is our base case. When we reach our destination, we return 1 as mentioned above.
This approach however, is too slow to be of use. Each function call branches out into further calls, and that branches into further calls, until each and every path is explored once. The problem with this approach is that we calculate the same $f(u)$ again and again each time the function is called with argument $u$.

Since this problem exhibits both overlapping subproblems and optimal substructure, dynamic programming is applicable here.

In order to evaluate $f(u)$ for each $u$ just once, we must make sure to evaluate $f(v)$ for all $v$ that can be visited from $u$ before evaluating $f(u)$. This condition is satisfied by reverse toposorted order of the nodes of the graph. Check out this Wiki article for more about topological sort.
Kahn's algorithm for toposorting a DAG is provided below

L = empty list
D = array of indegrees for each node
S = list of all nodes u with D[u] = 0
while S is not empty repeat
    remove a node u from S
    append u to the end of L
    for each edge u→v
        D[v] = D[v] - 1
        if D[v] equals 0
            add v to S

The next step is to use dynamic programming to calculate our $f$ values. We also need to make sure to store the values modulo 109+7.

dp = array to store f values
set dp[u] = 0 for each node u
dp[Q] = 1
for each node u in revere order of L
    for each edge u→v
        dp[u] = dp[u] + dp[v]
        dp[u] = dp[u] % 1000000007

The last step is to print the value of dp[P].

Complexity of this approach is $O(N+M)$.

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 14 Oct '16, 23:19

meooow's gravatar image

5★meooow ♦
5.5k411
accept rate: 47%

edited 07 Jun, 17:31

admin's gravatar image

0★admin ♦♦
17.4k347487515

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:

×12,340
×1,934
×1,321
×967
×18
×14
×1

question asked: 14 Oct '16, 23:19

question was seen: 582 times

last updated: 07 Jun, 17:31