### Sanath_kumar's blog

By Sanath_kumar, history, 2 months ago, You will be given a matrix of n rows and m columns. In each cell the entry will be either 0 or 1.

Right angled isosceles triangle is defined as follow :

1. hypotenuse has to be parallel to the x axis

2. all cells inside and on the triangle should be 0

3. length of hypotenuse should be odd and >=3

Find Total number of right angled isosceles triangles which can be formed as described .

Constraints :

1<= test cases <=20

1<= n,m <=1000

SAMPLE INPUT :

[ 1 1 1 1

1 0 0 0

1 1 0 1 ]

SAMPLE OUTPUT :

1

Any ideas ?  Comments (14)
 » The problem mentioned by you is similar to this problem. You just have to calculate the answer for both cases, the one where the vertex is pointing upwards and the one where it is pointing downwards.
•  » » Can you say what will be the time complexity for this approach ?
•  » » » I did it in O($n^{2}$ m). 100924784
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   yes but O(m * n^2) does not satisfy this problems constraint right 1<= n,m <=1000And I am sure that I remembered constraints correctly
•  » » » » » Yeah it will not work m*n^2 approach was passing half testcases only.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   It can be solved in $O(n*m)$ by DP approach. You can take help from this solution.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   Thanks for the solution.
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   I had a different set and I couldn't solve any of my two questions :'(. One was Prime Path and the other was Reckon Strings. This is the 2nd question. I know that you might have made this comment in a funny manner but at least have the guts to come from your real ID to take a jibe at someone as it may produce bad image of someone.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   K
•  » » » » » » » ok
 » I don't understand this. Some set has CF-Div2-B level questions whereas other set has subset convolutions (minimum subset with maximum OR).
•  » » The desired complexity was different though.
 » 2 months ago, # | ← Rev. 2 →   I implemented it using DP in O(n*m). My Implementation#include using namespace std; long long function(int n,int m,vector mat){ vector> dp(n,vector(m)); long long ans = 0; for(int i = n-1;i >= 0 ;i--){ for(int j = 0;j < m;j++){ if(mat[i][j] == '1'){ dp[i][j] = -1; } else{ dp[i][j] = 0; } if(i < n-1 && j > 0 && j < m-1){ // cout< 0){ ans += dp[i][j]; } } } for(int i = 0;i < n ;i++){ for(int j = 0;j < m;j++){ if(mat[i][j] == '1'){ dp[i][j] = -1; } else{ dp[i][j] = 0; } if(i > 0 && j > 0 && j < m-1){ if(mat[i][j] == '0'){ dp[i][j] = min(min(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]) + 1; } } if(dp[i][j] > 0){ ans += dp[i][j]; } } } return ans; } The basic idea is bottom-up DP Approach. DP[i][j] gives me the maximum size of isosceles triangle that can be formed with that point as top-most tip.
•  » » Thanks