Media.net Interview question — Help needed

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

This is a question asked in Media.net interview, I have been thinking along the lines of Dijkstra but trying to be greedy in Dijkstra can end up giving no solutions, so I can't come up with a clear way of solving it

Problem: Given a graph in which each node represents a city. Some cities are connected to each other through bidirectional roads. The length of each road is also given. Some of the cities have hotels. Given a start city and a destination city and a value K which represents the maximum distance that can be travelled by a person in one day, find the minimum number of days in which the person can reach his destination (or tell if it is impossible for the given K). (Note : If the distance travelled in one day is exceeding K, the person can rest in the city which has a hotel in it, if there is no hotel in that city this implies you have to choose another path. Next day, the person can start from that city and the distance travelled get reset to 0).
(The last statement was confusing for me, perhaps it means something along if the intended distance exceeds K you have to reset your distance by resting in a city with hotel)

How would you go about solving this one?

start dfs from start_city if current_city == destination city then dp[current_city] = 0; return; iterate through all cities with hotels which have distance <= K from current_city if next_city is not visited then dfs(next_city) if dfs of next_city is not running then dp[current_city] = min(dp[current_city],1+ dp[next_city])

Comments (15)

Show archived | Write comment?

rembocoder

4 years ago, # |

← Rev. 3 →

If I get this right, they just mean that you can not go a distance more than K without resting.

I only know how to find if the end is reachable in O(M log N) time. I don't know if it is possible to find the shortest distance in that time (finding it in O(N M log N) is trivial).

First run the Dijkstra starting from every hotel at once. Than for every city I know which hotel is the closest and the distance to this hotel. Let's call the closest hotel array "closest[v]" and the distance array "dist[v]".

Now the graph is divided into zones. Each zone is a set of vertices for which the same hotel is the closest.

Now I want to know which hotel is reachable from which. I go through every edge that connects two vertices a and b which lie in different zones. Suppose the length of the edge is len. Then if dist[a] + dist[b] + len is no more than K, I can add an edge between closest[a] and closest[b] in the hotel reachability graph.

Now if any two hotels are reachable from each other, I can consider the path between them and prove that they will end up in the same connectivity component in the hotel reachability graph. However I can not find the shortest path between them because it can pass through some other zones.

Now I just need to run Dijkstra from start vertice and from end vertice to find which hotels are reachable from them and determine if there are two hotels reachable from start and from end that lie in the same component.

→ Reply

kstheking

4 years ago, # ^ |

← Rev. 2 →

Thanks for the reply, but it's not more than K edges, but the total distance covered till now, so if the person has travelled 5 and 7 and the next edge is 8 but K is 13 he can't travel to here because 12 + 8 > 13 Which means he should have rested somewhere along the path which would have reduced this cumulative total he has walked and then he might have crossed this edge

Yes, my solution still works, I just made a mistake in the first sentence.

Greatest789

Great solution!!!

But it still does not count the minimal distance. I am not sure if it possible to do it faster than O(M N log N). Maybe some red guy will tell us.

Thank you for your replies. Thanks to your comments I was able to figure out an Idea. Its time complexity is O(MlogN*numberOfDays) where M is edges N are vertices
Can you please verify this
Let's look at the last step of the algorithm, if we reach the destination it will be from some hotel/source which is <= K far away. So we run dijkstra to find all hotels/source which are in range <= K. If the source belongs to this set we found, then we have an answer.
If it doesn't then that means we absolutely have to rest for one day. If we are going to rest for one day, Let's again find all the hotels/source which could be the second last resting point. To find them we simply run dijkstra from all the hotels we found in last step, and then again if we have the source in this set, we have answer or else we repeat.
This process will repeat as many times as are the days to reach the source. Therefore time complexity being that of Dijkstra multiplied by number of days. If the set doesn't change after an iteration which means we can't move further and the source can never be reached.
To optimize it a little bit we can, not check adjacent vertices of vertex whose distance value already exceeded K because they won't give any profitable answers.
Maybe this approach can be optimized further or a better solution exists

Your solution runs in O(N M log N), because you will do Dijkstra from every hotel in the worst case scenario.

Can you write about the worst case please?
If the resting nodes are comparatively lower then for worst case it will run a few times dijkstra if it finds one node per iteration,
if resting nodes are comparatively higher then for worst case to have only one resting node found in every iteration the rest of the nodes will have to be at >K distance, because of optimization they will be ignored and the dijkstra won't run fully. So in cases like where nodes are chained together at K distance apart in one long chain and each one of them is resting node. This won't take much time
One more possible optimization to this can be ignoring previously found hotels

You run Dijkstra from the endpoint. You find that every hotel is reachable in distance K, but the startpoint isn't. So you have to run another Dijkstra from every hotel in order to find where you will get the minimal distance.

Yes you are correct, but the question just asks what is the minimum days required to reach at destination, so in this case if after running multi source dijkstra on all those hotels we found if we get to source in K distance, we'll say it takes two days. As the exact information of how many days and how many steps isn't required, only minimum days

Oh shit, I really can't read. Sorry. I will think one more time a bit later then.

Oh, thank you very much !

So, if I understand your solution, we just run Dijkstra from endpoint, find reachable hotels, then run Dijkstra from all of them at once, find the hotels reachable only in two days, run Dijkstra from all of them at once and so on. Seems fine, works in O(D M log N), where D is the number of days.

Chand-

3 years ago, # |

Can't we do something like this?

assume that starting and destination cities also has hotel. First run the Dijkstra starting from every city with hotel once.(Time O(V * E logV))

Use 1D dp where dp[i] is minimum days required to reach from ith city to destination city. So our answer will be dp[start_city]

So time O(V * V)

So total time O(VElog V + VV)

3 years ago, # ^ |

rembocoder can you please verify this?

kstheking's blog