Subrectangles problems
Difference between en2 and en3, changed 69 character(s)
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(n^{2})$.↵

In given matrix of integers find subrectangle with largest sum. It can be solved in $O(n^3)$.↵

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

Here problems that i remembered:↵

 - [Count of subrects with max-min<=K](http://codeforces.net/gym/100570/problem/C)↵

 - [Count of subrects with ones<=K](http://codeforces.net/contest/364/problem/E)↵

 - [Largest arithmetic subrect](http://codeforces.net/gym/100523)↵

 - [Count of all zero-subrects](https://www.hackerrank.com/challenges/demidenko-farmer)↵

 - [Count of squares with exactly K stripes](http://acm.timus.ru/problem.aspx?space=1&num=2039)↵

 - [Largest subrect in 01-matrix with zero-perimeter](http://usaco.org/index.php?page=viewproblem2&cpid=600)↵


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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English oversolver 2016-02-18 16:05:08 69 new problem added
en2 English oversolver 2016-02-17 18:28:44 112
en1 English oversolver 2016-02-17 18:04:42 965 Initial revision (published)