PROBLEM LINK:
Author: Rupesh Maity
Tester: Asim Krishna Prasad and Sarvesh Mahajan
Editorialist: Rupesh Maity
DIFFICULTY:
EASY
PROBLEM:
Given a sorted array of distances to visit and a few dependencies (right to left) on the order of visit and the final destination point, find the minimum distance required to cover all the array elements and finally reach the end point.
EXPLANATION:
Since the dependencies are from right to left, visiting all the shops in the way to the rightmost shop, then returning back to the leftmost non-visited shop and then going to the destination shop will surely cover all the shops. Notice that, you will have to pass through every shop atleast once and atmost thrice. So now, you have the general idea of how we are supposed to visit these shops.
We start by going right. We know that, if there is a non-visited shop towards the left, we will surely have to go back once to visit it. Why not save this back traversal until all the dependencies to your left have already been covered. That is, suppose there are dependencies (5, 9) and (7, 11), going from visiting the shops in this sequence (9, 5, 11, 7), will cover a total distance of (9+4+6+4 = 23), whereas visiting in this sequence (9, 11, 7, 5) gives us a total distance of (9+2+4+2 = 17). You see what we have done there, since ‘7’ is an unvisited shop but its dependency ‘11’ has not been visited yet, we dont want to go to 5, we can go back to 5 once the dependencies (remember, 7 can have more than one dependency) for 7 have been visited. So in short, what we are doing is just merging the intervals to form the smallest intervals which do not have any other dependency outside this interval.
For example, suppose we have dependencies (1, 7), (5, 8), (10, 11), the merged intervals will be (1, 8) and (10, 11). This can be visited in this order (8, 1, 11, 10) giving an answer (8+7+10+1=26). You might be wondering that, if we had visited in this order (8, 11, 10, 1), the total distance would have been equal to 21. I am explaining how we are merging the intervals. There may still be shops to the right which might need to be covered. That is, if the rightmost shop to be covered is at 20, then the order (8, 1, 11, 10, 20 = 36) gives a better answer than (8, 11, 10, 1, 20 = 40). Read the below part to understand how this plays an important role.
The only case left to be considered is the final shop to be visited (ice-cream shop given in the question). This shop is supposed to be visited last. If this shop is located after the rightmost shop, we can just directly visit it after visiting all other shops. But if it is located in between, we know that, we have to make a back traversal at the very end. Now, in the same way we saved this back traversal previously (as discussed earlier), we can do the same here. In the example above, suppose the goal is at 5, it doesn’t make sence to visit (8,1,11,10,5) giving total distance = 31. Instead, if we go in this order (8, 11, 10, 1, 5), we get a total distance = 25.
If you were not able to solve this question and are reading this editorial for hint, either the idea of visiting back to the left ‘only once’ has probably not striked you yet or you are handing the case of visiting the ice-cream shop differently. Think over it. Comment your queries below if you’re still facing problems.
Complexity: O(N)
Author’s Solution:
Author’s solution can be found here.