PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
Sliding Window, Binary Search, Dynamic Programming
PROBLEM:
Given a binary grid, find the number of subrectangles which contains at least l 1s and at most r 1s.
QUICK EXPLANATION:
There are many ways to solve this problem. The key is to note that m is small, so we can consider all pairs of rows i and j so that the upper row of the subrectangle is i and the bottom row of the subrectangle is j. It also helps to note that we can split the problem into two parts, calculating the number of subrectangles with at most r 1s and the number of subrectangles with at most l - 1 1s, and subtracting the results.
EXPLANATION:
The first subtask is simple. One can just iterate through all possible subrectangles and for each subrectangle, count the number of 1s in it. Since there are O(n^{2}m^{2}) subrectangles and O(nm) time is needed to count the number of 1s in each subrectangle, this solution works in O(n^{3}m^{3}) time.
The second subtask is just a slight improvement over the first. We can use a simple trick to count the number of 1s in each subrectangle in O(1). Let dp[i][j] denote the number of 1s in the subrectangle with opposite corners (1, 1) and (i, j). The values of dp can be calculated by dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + cnt[i][j], where cnt[i][j] = 1 if there is a 1 in square (i, j). This dp can be calculated in O(mn). Now, the same solution in the first subtask works in O(n^{2}m^{2}).
For the last subtask, one have to optimize the solution. Consider all pairs of rows i and j so that the upper row of the subrectangle is i and the bottom row of the subrectangle is j. We’ll count the number of valid subrectangles in O(n), which will give us a grand total of O(m^{2}n), which is fast enough.
To do so, let’s create a new array A, containing n elements. Each element k denotes the number of elements in column k from rows i to j. Each subrectangle now corresponds to a subsegment of this array. We want to find the number of subsegments with sum at least l and at most r. This is a standard problem and can be solved in various ways. One possible way is to iterate through all possible start points from left to right, and keep incrementing the endpoint until the sum becomes larger than r. Then, when we go to the next start point, we start from the last endpoint, instead starting over from the beginning. This way, we can count the number of subsegments with sum \le r in O(n). Repeat this to count the number of subsegments with sum \le l - 1. The answer is obtained by subtracting these two results. Thus, the whole solution works in O(m^{2}n).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.