Doesnt work for larger inputs


#1

Its showing that the solution doesnt work for larger inputs. I am using C++. I have tried using long as datatype.


#2

Same problem for me, I am almost 100% certain the code is correct, I have used long long as data type, set the initialization right, and even corrected the Bsearch limits, the code passes for correctness section but fails for large inputs.
It doesn’t let me change the return type of function to long long either, so maybe python code will pass but not c++, please check admin.


#3

The problem is not with your data type, time complexity or space complexity. Your solution approach must be wrong. The larger inputs are more strict. I was getting the same error. Found an error with the logic, changed it and it worked. My time and space complexity are both O(n^2). Consider the following case,

0 0 0 0 0 1
-1 -1 -1 -1 -1 1
-1 -1 -1 -1 -1 1
-1 -1 -1 -1 -1 1
-1 -1 -1 -1 1000 1

Does your logic still work? I had an issue with cases like above.

Hope this helps.


#4

Make sure that the Knight has at least 1 health point before entering any dungeon. This applies to all the dungeons including the starting dungeon. Test your code for

  1. [[1, 2]]
  2. [[2, 0, -1]]

#5

The mistake I got in my code when It showed fails for large test cases was I was not ensuring that the initial health cant be zero. Suppose you got a case when there is no requirement of initial health like
1 1 1
1 1 1
1 1 1
Here I was expecting the answer 0 and solved accordingly but the answer should be 1 since At any point It cant have health<=0 So My be you all have the same mistake.
I ran it on leetcode Then I got to know this test case.


#6

Hi i was stuck on the same cases
initial health should also non zero, in essence after solving the problem if you get initial health as zero return 1
ie return max(1,answer_you_got)

int Solution::calculateMinimumHP(vector<vector<int> > &A) {
  int row=A.size();
  int col=A[0].size();
  vector<vector<int>>dp(row,vector<int>(col));
  
  if(A[row-1][col-1]<=0)
      dp[row-1][col-1]=1+abs(A[row-1][col-1]);
      
  for(int j=col-2;j>=0;j--){
      dp[row-1][j]=max(0,dp[row-1][j+1]-A[row-1][j]);
      if(A[row-1][j]<=0){
          if(dp[row-1][j]==abs(A[row-1][j]))
              dp[row-1][j]++;
      }
  }
  
  for(int i=row-2;i>=0;i--){
      dp[i][col-1]=max(0,dp[i+1][col-1]-A[i][col-1]);
      if(A[i][col-1]<=0){
          if(dp[i][col-1]==abs(A[i][col-1]))
              dp[i][col-1]++;
      }
          
  }
  for(int i=row-2;i>=0;i--){
      for(int j=col-2;j>=0;j--){
          int l=max(0,dp[i+1][j]-A[i][j]);
          int r=max(0,dp[i][j+1]-A[i][j]);
          dp[i][j]=min(l,r);
          if(A[i][j]<=0){
              if(dp[i][j]==abs(A[i][j]))
                  dp[i][j]++;
          }
      }
  }
  return max(dp[0][0],1);
}