You are not logged in. Please login at www.codechef.com to post your questions!

×

MCO16105 - Editorial

PROBLEM LINK:

Practice Contest

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.

RELATED PROBLEMS:

asked 13 Nov '16, 21:38

zscoder's gravatar image

6★zscoder
62812
accept rate: 6%

edited 13 Jan '17, 15:16

admin's gravatar image

0★admin ♦♦
19.0k348495531

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,365
×3,155
×1,754
×809
×31
×2

question asked: 13 Nov '16, 21:38

question was seen: 732 times

last updated: 13 Jan '17, 15:16