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 :

hypotenuse has to be parallel to the x axis

all cells inside and on the triangle should be 0

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 ?

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

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.

It can be solved in $$$O(n*m)$$$ by DP approach. You can take help from this solution.

Thanks for the solution.

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.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.

I implemented it using DP in O(n*m).

My ImplementationThe 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