Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### oversolver's blog

By oversolver, history, 8 years ago,

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:

• +38

 » 8 years ago, # |   0
 » 8 years ago, # |   +8 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?
•  » » 4 years ago, # ^ |   -9
 » 8 years ago, # |   +3
 » 8 years ago, # | ← Rev. 3 →   +5 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
 » 8 years ago, # |   0 Auto comment: topic has been updated by oversolver (previous revision, new revision, compare).
 » 8 years ago, # | ← Rev. 2 →   +18 Largest subrectangle with different numbers 407D - Наибольшая подматрица 3
 » 8 years ago, # |   0 Largest "chess" submatrix: https://community.topcoder.com/stat?c=problem_statement&pm=13035
 » 8 years ago, # |   0 I'm looking for a problem finding subrectangle with largest sum in matrix on CodeForces. Is there any?
•  » » 8 years ago, # ^ |   +8 http://main.edu.pl/pl/archive/ontak/2013/zam — this one may be more interesting :)
•  » » » 8 years ago, # ^ |   +8
•  » » » » 8 years ago, # ^ |   0 Gentlemen, I've got pretty important exam on Monday...Nah, it can wait.
 » 8 years ago, # |   +3 Auto comment: topic has been updated by oversolver (previous revision, new revision, compare).
 » 8 years ago, # |   +13
 » 8 years ago, # |   +11 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.
•  » » 8 years ago, # ^ |   0 I've found this: http://link.springer.com/chapter/10.1007%2F978-3-540-74456-6_40
•  » » 8 years ago, # ^ | ← Rev. 3 →   +28 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)
•  » » » 8 years ago, # ^ |   +3 Thanks for the explanation! :)
 » 8 years ago, # |   +8