PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM
PRE-REQUISITES:
Dynamic Programming
PROBLEM:
K+2 (K<101) cities with id 0,1,…K+1. You start from city 0 to reach city K+1 visiting some cities from set {1,2,3…K} in increasing order of id in between. While coming back from city K+1 to city 0 you visit the rest of unvisited cities in decreasing order of id’s. Given the cost matrix(ie. distance between each pair of city), you have to find the minimum time in which whole trip can be finished.
EXPLANATION:
We use dynamic programming. Let’s see how we’ll choose our states. One thing we can clearly see is that, we’ll traverse over cities and we have two options: visit current city while going from 0 to K+1 or while coming back.
Now, our cost will depend on which city we visited before current city.
So, in our dp state we store (current_node, lasta, lastb), lasta and lastb denote the largest id of cities in both sets.
So, let’s define the recurrences:
f(current_node, lasta, lastb)=min(
//visit current_node while going from 0 to K+1
f(current_node-1, current_node, lastb),
//visit while going from K+1 to 0
f(current_node-1, lasta, current_node)
Complexity: O(K^3) (worst case).
IMPLEMENTATION:
Recursively implement the dp(with memoisation). See editorialist’s detailed solution for implementation details.