Find the minimum distance to travel through a road having hills [Interview Question]

Problem Statement: Alansh has to travel through a road having hills of different heights. Also each hill has a cave to pass through it, to avoid travelling extra distance of a hill. Alansh wants to travel through this road by taking at most K caves, so that he has to travel minimum distance. However, if Alansh has taken cave i, he cannot take i+1 cave.

So, help Alansh to travel minimum distance using at most K number of caves. Also there’s no limit to distance travelled through road and cave. This distance is not counted.

Example 1:

Input: 
a = {10, 12, 11, 18}
K = 2
Output: 21
Explanation: 
Taking the cave through hills 12 and 18, gives the minimum distance to travel ie. 10+11 = 21

Optimal Substructure

An optimal solution to problem contain optimal solution to subproblems. To consider all caves, 2 cases for every cave arises:

  1. Cave is taken in optimal path
  2. Cave is not taken in optimal path

Approach

Now let’s modify the problem to this: Find the maximum distance travelled through the hills that could be avoided. Now this problem is same as Knapsack problem. However if the condition: if cave i is taken, he cannot take i+1 cave, hadn’t been there, this could have been solved by the same approach as Knapsack problem.

But to solve this problem with this additional constraint, we need to maintain an additional array val[n][K] to check if the previous cave was taken in this optimal solution of the subproblem.

After finding the maximum distance travelled through the hills that could be avoided, we could find our solution as:

Minimum distance travelled = total distance through all hills – maximum distance through hills

Code Implementation

//
//  main.cpp
//  Modified Knapsack
//
//  Created by Himanshu on 29/10/18.
//  Copyright © 2018 Himanshu. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;

int solve(vector<int> a, int K) {
    int n = (int)a.size(), totalDistance = 0;
    int dp[n+1][K+1], caveTaken[n+1][K+1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= K; j++) {
            dp[i][j] = 0;
            caveTaken[i][j] = -1;
        }
    }
    
    for (int i = 0; i < n; i++) {
        totalDistance = totalDistance + a[i];
    }
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= K; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i-1][j];
                // If optimal solution include current cave
                if (dp[i-1][j] < (a[i-1] + dp[i-1][j-1])) {
                    // If current optimal solution
                    // include previous cave
                    if (caveTaken[i-1][j-1] != -1) {
                        if (i > 1) {
                            dp[i][j] = max(dp[i-1][j], a[i-1] + dp[i-2][j-1]);
                            if (dp[i][j] != dp[i-1][j]) {
                                caveTaken[i][j] = i-1;
                            }
                        }
                    } // If current optimal solution doesn't include
                      // previous cave
                    else {
                        dp[i][j] = a[i-1] + dp[i-1][j-1];
                        caveTaken[i][j] = i-1;
                    }
                }
            }
        }
    }
    
    return (totalDistance - dp[n][K]);
}

int main(int argc, const char * argv[]) {
    vector<int> a = {4, 8, 5, 2, 6, 3, 7, 11, 13, 10};
    int K = 3;
    cout<<"Minimum distance to travel: "<<solve(a, K)<<endl;
    return 0;
}

Here’s a working example:

https://ideone.com/QfB0Yr

Leave a Reply

Your email address will not be published.