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

×

WNDR - Editorial

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.

This question is marked "community wiki".

asked 24 Jan, 01:34

watcher's gravatar image

7★watcher
35
accept rate: 0%

edited 29 Jan, 14:18

aryanc403's gravatar image

6★aryanc403
2.5k1516


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 ?

link

answered 28 Jan, 03:46

harshraj22's gravatar image

4★harshraj22
605
accept rate: 0%

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

(29 Jan, 14:14) ducpro6★

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??

(29 Jan, 14:21) aryanc4036★

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

(29 Jan, 15:39) ducpro6★

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

link

answered 13 Feb, 21:15

prakhar897's gravatar image

4★prakhar897
1
accept rate: 0%

@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) arjitkansal5★
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,678
×2,169
×366
×39

question asked: 24 Jan, 01:34

question was seen: 915 times

last updated: 14 Feb, 13:52