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.
433D - Nanami's Digital Board
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?
https://cp-algorithms.com/dynamic_programming/zero_matrix.html#toc-tgt-3
maximum sum
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
Auto comment: topic has been updated by oversolver (previous revision, new revision, compare).
Про максимальный периметр
Про подматрицы с суммой в данном диапазоне
Largest subrectangle with different numbers 407D - Largest Submatrix 3
Largest "chess" submatrix: https://community.topcoder.com/stat?c=problem_statement&pm=13035
I'm looking for a problem finding subrectangle with largest sum in matrix on CodeForces. Is there any?
http://main.edu.pl/pl/archive/ontak/2013/zam — this one may be more interesting :)
also: http://www.spoj.com/problems/MINES4/
Gentlemen, I've got pretty important exam on Monday...
Nah, it can wait.
Auto comment: topic has been updated by oversolver (previous revision, new revision, compare).
372B - Counting Rectangles is Fun
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.
I've found this: http://link.springer.com/chapter/10.1007%2F978-3-540-74456-6_40
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)
Thanks for the explanation! :)
problem from IOI 2006