WNDR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Div 1
Div 2

Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: 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[i-1][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_{i-1}) 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.
Tester’s solution can be found here.

2

Can anyone help me ?
I was thinking to do a dfs on each node and if the given conditions are not satisfied , return 0 else return 1 and the req result is the sum of all return values . for constraints , a better idea would be using unordered_map . Can anyone verify wether my idea is correct or not ?

3

And how the heck is this backtracking idea is gonna pass within the time limit…?

4

Let’s forget that this idea will take centuries to yet it will not complete.
But we can still verify that this idea is correct.

Why you want to use unordered_map any specific advantage??

5

Maybe he wants to save the path into a vector and unordered_map that vector to 1 :thinking:?

6

Can anyone explain why the complexity is O(n+m) and not O(n*m).

7

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