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:
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:
- Simply ignore the constraint and simulate upto time instant b.
- 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’.
- 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
Great topic. Thank you.
very interesting
Oh, it seems you forgot to mod the value by 1e9 + 7.
Here is the corrected code: CodeChef: Practical coding for everyone
@sarthankmanna please tell me the error in my solution.