ESCARTST-EDITORIAL

editorial
1

Problem statement
Contest source

Author , Tester , Editorialist : Jashwanth

DIFFICULTY:

medium

PREREQUISITES:

DP

PROBLEM:

we are being asked to find the minimum health required to go from top left of the matrix to bottom right position.

EXPLANATION:

we make a new matrix ( dp matrix )

and fill it with following rules:

  • integer in any index position represents the minimum health required to go

    from that index position to the exit with health atleast 1

  • numbers in the dp matix equals

          max( down , right )  -  current corresponding number

  • negative value signifies that the person lacks that amount of health ,

    if he had that many health points ,

    he could reach the exit alive

  • positive value signifies that the next step has a poistive number to increase the health points,

    hence we can easily say that health required at that position is just 1 , as the next step is surely a positive number

    ie. for positive numbers , we replace it with one

    in other words , we use min( 1 , max(down,right)-grid[i][j] )
    -following this bottom up approach ,we finally reach dp[0][0] which is the

    minimum health at starting point to reach the exit alive

    which is the required answer

SOLUTION :

#include<time.h>

#include<vector>

#include<stdlib.h>

#include<iostream>

using namespace std;

int calculateMinimumHP(vector<vector<int>>& d) {
    vector<int> dp(d.size() + 1, 100000000);
    dp[d.size() - 1] = 1;
    for (int i = d[0].size() - 1; i >= 0; --i)
        for (int j = d.size() - 1; j >= 0; --j)
            dp[j] = max(1, min(dp[j + 1], dp[j]) - d[j][i]);
    return dp[0];   
}
int main()
{
int row,column;
cin>>row>>column;
vector<vector<int>> vec(row);
for(int i = 0; i < row; i++)
{  
    vec[i] = vector<int>(column);
    for(int j = 0; j < column; j++)
        cin>>vec[i][j];
}
cout<<calculateMinimumHP(vec);
}