I'm struck how to find DP recurrence for:

You are given a binary square matrix M of size nxn. We define a (p,q, l)-triangle of M, where p >= 1, q >= 1, L >= 1, p+L >= n+1, and q+L >= n+1, as the set of elements M[i, j] satisfying p =< i < p+L, q =< j < q+L, and i+ j < p+q+L. Design an algorithm to find the largest (p,q, l)-triangle of M (“largest” means l is maximized) such that all its elements are “1”

EDIT: I added the original problem as requested:

enter image description here


I think I need to check first if:

element equal 1,

if so, check the element to its left, element in its top and element diagonally if equals "1"

if so increment the result,

but not sure how to put this into recurrence.

  • 1
    $\begingroup$ Suppose p=q=1, L=2k. Suppose also that there is a (1,1,2k)-triangle. Draw it and think about what happens when you decompose it into a square of side length k and two new triangles. Next step is to generalize for odd lengths and general (p,q). $\endgroup$ – VashTheStampede Dec 21 '20 at 19:05
  • $\begingroup$ The condition $p+L\ge n+1$ is somewhat misleading since the largest index for the index $i$ in $M[i,j]$ is $n$. Did you mean $p+L=n+1$? $\endgroup$ – John L. Dec 22 '20 at 5:00
  • 1
    $\begingroup$ Can you add a reference to the original problem? Even if it is not in English, it is great to see the original version. I can then write code to check my answer. $\endgroup$ – John L. Dec 22 '20 at 5:05
  • 1
    $\begingroup$ I don't think @VashTheStampede's suggestion will lead to a simple, fast DP algorithm. I suggest: Ask yourself what triangles must exist "locally" if there is a triangle of size $L$ with bottom-rightmost point at $(i,j)$. Using this directly would enable an $O(n^4)$-time algorithm, but that can be sped up to $O(n^2)$ by representing this information in a "compressed" way: If you know there is a size-$L$ triangle with bottom-right corner at $(i,j)$, you also know there is a size-$(L-1)$ triangle there, etc. $\endgroup$ – j_random_hacker Dec 23 '20 at 1:19
  • 1
    $\begingroup$ @j_random_hacker my idea is quadratic with the right precomputation. In fact, if expressed as top-down dp it can be done in O(n^2) without any precomp :) I think I also catch your solution and indeed it needs some precomputation (on longest column/diagonal of 1s). If I am wrong I would like to read an answer once the OP has solved the problem! $\endgroup$ – VashTheStampede Dec 25 '20 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.