 # NUMPATH - Editorial

Author: Vineet Paliwal
Tester: Roman Rubanenko
Editorialist: Jingbo Shang

Medium

### PREREQUISITES:

Dynamic Programming, Suffix Sum, Fenwick Tree

### PROBLEM:

Given a Directed-Acyclic-Graph (DAG) G = (V, E) in which node i has edges to nodes in [i + 1, i + N[i]], find how many paths are there between S[i] and T.

### EXPLANATION:

This DAG is really special and the order of 1 … V is exactly same as its topo order in which edges are only existed from previous nodes to their later ones.

Use F[i] to state the number of different paths starting from node i to node T.

    Initially F[T] = 1, F[others] = 0.


The transmission can be described as following:

    For i = T - 1 downto 1
F[i] = \sum_{v = i + 1} ^ {i + N[i]}


To speed up this transmission procedure, we can use a Fenwick Tree to get the sum. But we can achieve it in a simpler way as following, using suffix sum.

    suffixSum[] = 0;
suffixSum[T] = 1;
For i = T - 1 downto 1
F[i] = G[i + N[i]];
G[i] = G[i + 1] + F[i]


To answer each query, just directly output the F[S[i]]. Therefore, the time complexity is O(N + Q) in total.

### AUTHOR’S AND TESTER’S SOLUTIONS:

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

4 Likes

http://www.codechef.com/viewsolution/7049475

Can anyone suggest how to reduce time? I am exceeding the time limit. I am working with C.

I just discovered that test cases aren’t strong enough.

For example,
https://www.codechef.com/viewsolution/66821748

submission above can be edited to have p(n+1) instead of p(n+2) in the initializer.

If you do that edit, the code fails on test case below because p[8+2+1] is accessed and can be != 0.

10 9
2 3 4 1 0 3 2 2 0 0
9
1
2
3
4
5
6
7
8
9