Find the minimum strength mustafa must have in the beginning so that he can cross N cells (Interview question)

This question was asked in an company coding round which unfortunately I was unable to solve, I am getting the glimpse that this question is based on greedy but cannot proceed further, anyone who has solution or algorithm please share it with me.

Problem Statement:

Mustafa wants to cross a dungeon. The dungeon has N cells, and in every cell, there are M monsters. To cross each cell he has to kill one monster, on killing the monster, he loses the strength equal to that of the monster and gains some confidence which adds up to his strength and he proceeds to the next cell. Mustafa can only kill a monster if his strength is greater than or equal to the strength of the monster. Help him find the minimum strength he must have in the beginning so that he can cross N cells.

Input format:

First two integers are N and M.
N X M matrix that represents energy required to kill monster in each cell.
N X M matrix that represents confidence gain by killing respective monsters.

Testcase:

Input:

Output:

Can this question be solved using Dynamic programming?

Solution 1:

Let us call Energy[N][M]) the energy needed to kill each monster, and Conf[N][M]the associated confidence.

Let us call Stren[N]the minimum energy that you will need to pass each cell.

We need to select the good monster at each step. The issue is that at first cell for example, you cannot make the good decision without considering all the next cells. A DP solution or a DFS one will certainly work. However, the complexity would be quite high.

The hint to use a greedy solution is correct, at the condition to start from the end.

At the last cell, the needed strength is easily calculated:

Strength[n-1] = min_i Energy[n-1][i]

The next strengths are then iteratively calculated, from back to the top:

Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i] + Strength[j+1]) For all j

Final result: Strength[0]

Complexity: linear O(NM). Impossible to do better as you have to consider each monster.

Some further explanations

Performing an iteration in reverse order is a classical trick, when you know the starting value, here Strength[N-1].

The key point is the recursive formula:

  Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i] + Strength[j+1])

This is the formula that one would apply with DP too, for example. Where does it come from?

For Cell j, the strength Strength[j] must fulfill two constraints.

You needed to kill one monster in the current Cell. Therefore, if monster i is selected, the the strength must verify
```
Strength[j][i] >= Energy[j][i]
```
After filling monster i, you need to keep enough strength, so that the remaining strength is higher that Strength[j+], in order to pass the next cells.
```
Remaining strength = Strength[j][i] - Energy[j][i] + Conf[j][i] >= Strength[j+1]
```

So, if monster i is selected, the minimum strength you must have, according to this criteria, is

  Strength[j][i] = Energy[j][i] - Conf[j][i] + Strength[j+1]

Having these two constraints for each monster i, then you can select the best one by minimizing the maximum of these two thresholds.

Solution 2:

Consider the given example:

Energy =  3 2 5
          8 9 1
          4 7 6

confi = 1 1 1
        1 1 1
        1 1 1

Now, initially we can't determine the strength required to pass the first row of monsters.

Therefore, we have to start from last row (as there are no further more rows left to pass).

Now, we calculate the minimum energy from the last row (i.e 4 in above e.g.) This minimum energy we can get from second last row, i.e after passing the second last row the strength remaining should be 4.

strength remaining = strength of second last row - energy + confi

  4            = str of second last row - energy[i] + confi[i]

str of second last row = min (4 + energy[i] - confi[i])

we have to consider the min strength as we have to output min strength.

Therefore, the strength of current row depends on the previous row.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<vector<int>>energy, confi;
    energy = {{3, 2, 5}, {8, 9, 1}, {4, 7, 6}};
    confi = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}};
    
    int n = 3; // no. of rows
    int m  = 3; // no. of columns
    
    int strength = INT_MAX;
    
    // calculate the min energy from the last row
    for(int i=0; i<m; i++)
         strength = min(strength, energy[n-1][i]);
    
    // start from the last second row
    for(int i = n-2; i>=0; i--){
        int temp_min = INT_MAX;
        for(int j = 0; j<m; j++){
            temp_min = min(temp_min, energy[i][j] - confi[i][j] + strength);
        }
        strength = temp_min;
    }
    cout<<strength;
    return 0;
}

Solution 3:

TL;DR

I notice that all solutions on this question so far failed this test case. If I am not mistaken, the answer should be 2.

I would like to point out that this problem is a modified version of the LeetCode Dungeon Game, you may check it out. The difference is that in this problem you don't have to look for the best path, there is only one path (i.e. cell_1 to cell_N). Also, in this problem, a cell contains both monsters and energy (in form of confidence), unlike the LeetCode problem that some cells contain monsters while others contain energy.

Without much ado, let me get into the solution. While solving any DP problem, I usually like using the framework explained here (sorry, it is for premium LeetCode users), I would recommend you check it out if you are interested.

Framework

Describe a recursive function or an array that answers the problem for a given state. The problem is asking for "the minimum strength required to fight from the cell_1 to cell_n". Therefore, we would use either a function dp(i) that returns the min strength required to fight from cell_i to cell n, or an array dp where dp[i] represents the min strength required to fight from cell_i to cell n.

This way, dp(0) or dp[0] represent the solution to the problem. Note that the recursive function, dp(i) is used for Top-Down approach whereas, the array, dp[i] is used for Bottom-up approach, also known as Tabulation approach.

NB: There is no single way to solving DP problems. For example, you may decide to use dp[i][j] to represent the min strength required from cell_i to cell_n when jth monster of cell_i is fought. However, I choose not include the monster selection at each cell in the dp state definition because the best monster can be selected at each cell via a simple linear search.

Define a recurrence relation to represent the transition logic between states. Below are steps that describe how we can move from one state to another.

Assuming we are at the cell_i, we want to calculate dp(i).
-Let next_state = dp[i+1] (next_state >= 0). This is because, at cell_i, optimal selection of monster to fight depends on (or affects) future selections at later cells.
-Also, let min_strength represents the minimum strength required to optimally fight a monster in the current cell (i.e. cell_i).

We want to iterate through the energies require to fight monsters and update the min_strength as we go. At the end, we will assign min_strength to dp(i). Thus, for each Energy[i][j] (i.e. j=1,...,m), we take steps i through iv.

i. initial_strength = Energy[i][j]: this is the minimum energy required to fight the current monster.

ii. future_strength = next_state - Confidence[i][j] : Let's use our current confidence towards future fights. future_strength denotes how much energy we need to prepare for future fights. If the current confidence is not enough, future_strength will be positive, which signifies energy we must have before going for the future fights. However, if the current confidence is enough, future_strength will be 0 or negative, This means that only the current confidence is sufficient to complete future fights. Thus. future_strength = max(future_strength, 0)

iii. total_strength = future_strength + initial_strength : this is the total energy/strength we must posses in order to complete the fights from the current cell (i.e. cell_i) to the end, if the jth monster is fought.

iv. min_strength = min(min_strength, total_strength): We need to keep track of minimum strength over all j.

v. The solution is dp(0) or dp[0].

The last thing we need is base cases so that our recurrence relation knows when to stop. The base cases are often found from clues in the problem description or found using logical thinking. In this problem, every state depends on the state after it (i.e. dp[i] depends on dp[i+1]). If so, which state does the state at the last cell (i.e. cell_n) depend on? Sure, dp[n] depends on the dp[n+1], which does not exist. Since the state dp[n+1] does not exist, we can assume that 0 strength is required to fight from dp[n+1].
Thus our Base Case is dp[n+1] = 0 or dp(n+1) = 0.

CODE IMPLEMENTATION IN JAVA

A. TOP-DOWN ,Time complexity: O(N*M), Space Complexity: O(N) (due to the recursion call stack). N = number of cells, M = number of monsters.
This approach is usually the most intuitive approach in most DP problems. Most times, Memoization or caching is used to improve time complexity. However, in this problem, there is only one path, so memoization is not necessary.

  private static int topDown(int cell, int[][] energy, int[][] confidence){
       //BASE CASE
       if(cell == energy.length)return 0;

       //current state depends on next states
       int nextState = topDown(cell +1, energy, confidence);

       //variable to hold min energy required from the current cell
       int minStrength = Integer.MAX_VALUE;

       for(int j = 0; j< energy[cell].length; j++){
           //we must have at least energy[cell][j] to fight this monster,
           int required = energy[cell][j];

           //Use the current confidence towards future fights
           int futureStrength = nextState - confidence[cell][j];

           //Notice that if futureStrength <=0, it means confidence gained here
           //is enough to finish the subsequent fights
           futureStrength = Math.max(futureStrength, 0);

           //total strength required to from cell i to the end if monster j is chosen
           int totalStrength = required + futureStrength;
           minStrength = Math.min(minStrength, totalStrength);
       }
       return minStrength;
   }

B. BOTTOM-UP, Time Complexity: O(N*M), Space Complexity: O(1).
Note that no extra space is used in this approach, this is because every state only depends on the one immediately after it, thus a simple variable can be used to keep track of the states.

private static int bottomUp(int[][] energy, int[][] confidence){
        int n = energy.length, m = energy[0].length;

        //base case
        int nextState = 0;

        for(int cell = n-1; cell>=0; cell--){

            //variable to hold min energy required from the current cell
            int minStrength = Integer.MAX_VALUE;

            for(int j = 0; j < energy[cell].length; j++){
                //we must have at least energy[cell][j] to fight this monster,
                int required = energy[cell][j];

                //Use the current confidence towards future fights
                int futureStrength = nextState - confidence[cell][j];

                //Notice that if futureStrength <=0, it means confidence gained here
                //is enough to finish the subsequent fights
                futureStrength = Math.max(futureStrength, 0);

                //total strength required to fight from cell i to the end if monster j is chosen
                int totalStrength = required + futureStrength;
                minStrength = Math.min(minStrength, totalStrength);
            }
            nextState = minStrength;
        }
        return nextState;
    }

Find the minimum strength mustafa must have in the beginning so that he can cross N cells (Interview question)

Solution 1:

Solution 2:

Solution 3:

Related

Recent Posts