oversolver's blog

Subrectangles problems
By oversolver, history, 9 years ago, In English

Hi people! I interested in problems with template name "Count of subrectangles" or "Best subrectangle" in rectangle. For example some well-known problems:

In given matrix of zeros and ones find subrectangle that contains only zeros and has largest area. It can be solved in O(n2).

In given matrix of integers find subrectangle with largest sum. It can be solved in O(n3).

Can you give me links or just statements on similar problems?

Here problems that i remembered:

Please, gimme other problems, any links in contests or archives:) I will add it here later.

  • Vote: I like it
  • +38
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

433D - Nanami's Digital Board

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

For the given matrix of 0's and 1's we can find a whole array c[n][n] in O(n2), where c[i][j] denotes the number of subrectangles of size i × j with 0's only. And it's not so hard. The description in Polish (use google translate) — link. Does anybody know about the description in English?

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

maximum sum

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

On Serbian contest and some Codechef Lunchtime round I saw task: find subrecetangle with maximum sum divisble by K. In both tasks expected complexity was O(n^3).

EDIT: Constrains for task from Serbian contest N,M (matrix dimensions) <= 250, K<=10^6.

I found task from lunchtime, it is a little different than previous one, but If i remember good with pretty similar idea for solving Codecef Lunchtime Count Rec

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by oversolver (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Largest subrectangle with different numbers 407D - Largest Submatrix 3

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Largest "chess" submatrix: https://community.topcoder.com/stat?c=problem_statement&pm=13035

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm looking for a problem finding subrectangle with largest sum in matrix on CodeForces. Is there any?

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by oversolver (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

372B - Counting Rectangles is Fun

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Finding 3 disjoint squares of size KxK with maximum total sum. M, N <= 1500. Here.

I would like to know the solution or at least some hints to this problem.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've found this: http://link.springer.com/chapter/10.1007%2F978-3-540-74456-6_40

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +28 Vote: I do not like it

    Full solution:

    The problem is equal to dividing the grid to 3 parts, then taking the best KxK square in each part.
    The ways of dividing the grid:

    1) The first way (the one on the left):
    By dividing the grid this way, each of the resulting parts will contain at least one corner of the original grid. Therefore, we can precalculate for every corner the best KxK square between this corner and (i, j).
    I will consider the case of the top left corner:
    Let b[i][j] be the sum of the values of the best KxK square that lies between (1, 1) and (i, j).
    b[i][j] = 0 (if min(i, j) < k)
    b[i][j] = max(max(b[i][j - 1], b[i - 1][j]), sum[i][j]) (sum[i][j] is the sum of values in the KxK square whose bottom right corner is at (i, j)

    2) The second way (the one on the right):
    In order to precalculate the best KxK square in each part (I will consider the horizontal case):
    For each row i, find best[i], the best KxK square which has it's bottom side on row #i.

    Let pre[i][j] be the sum of values in the best KxK square which lies completely between row i and row j.
    pre[i][j] = 0 (if j - i < k)
    pre[i][j] = max(pre[i][j - 1], best[j])

    Now, you can try all possible ways of dividing the grid, and for each way, calculate the answer in O(1).
    Total Complexity: O(nm)

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

problem from IOI 2006

→ Reply