kstheking's blog

By kstheking, history, 5 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +21
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kstheking (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Great solution!!!

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Oh, thank you very much !

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  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.

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Do a simple dfs.