PROBLEM LINK:Author: Michael Nematollahi PREREQUISITES:DP PROBLEM:You're given an undirected graph with $N$ vertices and $M$ edges and a positive integer $K$. You're also given $Q$ constraints of the form $(a_i, b_i)$. A walk is defined as a sequence of vertices in which every two adjacent vertices are the same or are connected by an edge. Your task is to calculate the number of walks of length $K+1$ that start at vertex $1$ and in which for each $i$ from $1$ to $Q$, the $(b_i+1)^{th}$ vertex is $a_i$. QUICK EXPLANATION:Sort the constraints given in the input based on time. Solve the problem for each consecutive pair and multiply the results to get the answer. To solve the problem for a pair of consecutive constraints, define $dp[i][v]$ to be equal to the number of walks of length $i$ that start at the first constraint and end at $v$. EXPLANATION:First, check that no constraint tells you to be on a vertex other than $1$ after $0$ seconds. Then, check that no two constraints tell you to be on two different vertices after the same amount of time. If one of these is the case, the answer is obviously $0$. Now we're ready to solve the problem. For the sake of simplicity, add the constraint $(1, 0)$ to the constraints. Then, sort the constraints based on time. It's easy to see that now we can solve the problem for every two consecutive constraints and multiply the results to get the answer to the original problem. To solve the problem for two consecutive constraints like $(a_1, b_1)$ and $(a_2, b_2)$, we need to calculate the number of walks of length $b_2  b_1$ that start at $a_1$ and end at $a_2$. Let's define $dp[i][v]$ as the number of walks of length $i$ that start at $a_1$ and end at $v$. Here's how to calculate this dp array: 1_ The base case is $dp[0][a_1] = 1$. 2_ $dp[i][v] = \sum_{for\hspace{1mm} each\hspace{1mm} vertex\hspace{1mm} u\hspace{1mm} adjacent\hspace{1mm} to\hspace{1mm} v)} dp[i1][u]$ The answer for this consecutive pair would be $dp[b_2  b_1][a_2]$ After finding the answer for the consecutive constraints, we need to find the number of ways we can continue our walk from the last constraint. This can easily be done using the same dp array. The complexity of calculating the dp array for a consecutive pair of constraints is of $O((b2  b1) \times (N + M)$. Since the sum of $(b_i  b_{i1})$ is equal to $K$, the total complexity of the solution is $O(K \times (N+M))$. To see the implementation, refer to the setter's solution. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 24 Jan, 01:34

Can anyone explain why the complexity is O(n+m) and not O(n*m). answered 13 Feb, 21:15
@prakhar897 If you know why the complexity of DFS or BFS is O(n+m) and not O(n*m), for more than obvious reason, You should be able to answer your question as well.
(14 Feb, 13:52)
