Sanath_kumar's blog

By Sanath_kumar, history, 2 months ago, In English

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 ?

 
 
 
 
  • Vote: I like it
  • -14
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you say what will be the time complexity for this approach ?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did it in O($$$n^{2}$$$ m).
      100924784

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        yes but O(m * n^2) does not satisfy this problems constraint right

        1<= n,m <=1000

        And I am sure that I remembered constraints correctly

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Yeah it will not work

          m*n^2 approach was passing half testcases only.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it -12 Vote: I do not like it

        Thanks for the solution.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 3   Vote: I like it +3 Vote: I do not like it

          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, # |
  Vote: I like it +18 Vote: I do not like it

I don't understand this. Some set has CF-Div2-B level questions whereas other set has subset convolutions (minimum subset with maximum OR).

»
2 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

My Implementation

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.