wanderer question on codechef

could someone explain me the wanderer problem on codechef?

You can study tourist’s solution. It’s quite clean and understandable.

The problem basically asks you to find the number of ways to roam in a connected graph of N nodes, at the speed of 1 edge per second for K seconds. However, some Q constraints are also imposed on you each of which asks you to stay at node ai at bi th second.

The first step is obviously to sort the constraints with respect to their time demands and check if it asks you to stay at two different nodes at the same time instant. Since it is impossible, the answer is a straightaway ‘0’ in such a case.

Now, since the maximum value of K (<= 9000) is iterable, we can process 1s at a time. In other words, we can re-calculate the number of ways to reach each node with every passing second.
Suppose, the graph is:

alt text

Let us first try to find the number of ways to reach a node at time t without following any constraints.

Consider, you are standing at node v3 at time t. Suppose, you already know that you can reach v3, v1, v2, v4 from v1 (you must start from v1, according to the problem) in w3, w1, w2, w4 ways respectively. Obviously, from node v3, you can either move to v4, v1 or v2 at time (t + 1) or stay at v3. Thus, the ‘new’ number of ways to reach v3, v1, v2, v4 at time (t + 1) from v3 are w3, (w1 + w3), (w2 + w3), (w4 + w3). I hope you get this.

Now, the rest is really simple. At time 0, you are at node v1. That means, the number of ways to reach v1, v2, v3, v4… at time 0 are 1, 0, 0, 0… respectively. You can start your simulation with time from this base.

Now, when you encounter a time instant which asks you to stay at a particular node, what you can do is simply reset all other ‘number of ways’ values.

For example, if you’re given a constraint which asks you to stay at node ‘a’ at time instant ‘b’, then do the following:

  1. Simply ignore the constraint and simulate upto time instant b.
  2. Since the constraint does not allow you to stay in any other vertex other that vertex ‘a’, reset all the ‘number of ways’ values, except that of node ‘a’.
  3. Continue the simulation again from here for time instants (b + 1), (b + 2)… until you find another such constraint.

The final answer is the sum of the ‘number of ways’ values.

Expected time Complexity O(K * M).

2 Likes

please tell me the error in my solution ,i did similiar.Here is my solution

https://discuss.codechef.com/questions/144515/wanderer-question-on-codechef/144542 cool described!

Great topic. Thank you.

very interesting

Oh, it seems you forgot to mod the value by 1e9 + 7.
Here is the corrected code: https://www.codechef.com/viewsolution/22676045

@sarthankmanna please tell me the error in my solution.