A garden is arranged as a rectangular grid of squares. Each square contains a number of roses. We want to hire two gardeners to take care of the roses. Each gardener is expected take care of exactly K roses, where K is a fixed number. Each gardener wants to work on a rectangular patch. To avoid the gardeners interfering with each other, they should work on with both patches disjoint (though it is permissible for the two rectangles to share a common boundary). Each rectangular patch comes with a cost, which is the perimeter of the patch. The aim is to find two non overlapping rectanglular patches, each containing exactly K roses, so that the total cost of the two patches is minimal. (If the two rectangles share a portion of the boundary, this is to be counted in the perimeter of both rectangles).
Here the number of rows and columns is ≤ 250, number of roses ≤ 5000, K ≤ 2500.
It is not sufficient to greedily find one rectangle of minimum perimeter and then search for the second one. In the minimum cost pair, neither rectangle may be of minimum size overall.
Observation
If we take two non-overlapping rectangles, they can always be separated by a vertical or horizontal line.
--------------------- -----------------------
| . | | ------- |
| -- . | | | | |
| | | . ----- | | | | |
| | | . | | | | ------- |
| -- . | | | |.......................|
| . | | | | --------------- |
| . ----- | | | | |
| . | | --------------- |
--------------------- -----------------------
Thus, we can try all possible ways of splitting the original rectangle using either horizontal or vertical line. For each split, we have to find the single best rectangle in each part.
In this way, we have reduced the problem from jointly identifying two rectangles with minimum cost to that of finding one minimum cost rectangle within a given rectangle.
How can we systematically enumerate all rectangles?
Assume we are using fixed height rectangles. Systematically choose each row of the garden to be the "base row". For each choice of base row, check each band that uses this base row. Symmetrically, fix a base column for vertical bands.
---------------------
| |
|---------------------|
| |
| Band of height k |
| |
|=====================|Base row
| |
| |
---------------------
This still requires us to calculate the number of roses in a given rectangle. How can we do this efficiently without actually adding up all values within the rectangle?
Calculate number of roses for special kind of rectangles, which start at top left corner of the original rectangle.
1 2 3 4 5 6 7 8 9 ... m
-----------------------------------
1 | | | | | | | | | | ... | |
-----------------------------------
2 | | | | | | | | | | ... | |
-----------------------------------
3 | | | | | | | | | | ... | |
-----------------------------------
. | | | | | | | | | | ... | |
. -----------------------------------
. | | | | | | | | | | ... | |
-----------------------------------
n | | | | | | | | | | | | |
-----------------------------------
Count(i,j) is the number of roses in the rectangle whose top left corner is (1,1) and bottom right corner is (i,j). We can compute Count(i,j) if we know the neighbouring values:
-------------------------------
| . . |
| . . |
| . . |
|......(i-1,j-1) ----- (i-1,j) |
| | | |
| | | |
|....... (i,j-1) ----- (i,j) |
| |
-------------------------------
Now, given a rectangle with top left corner (u,v) and bottom right corner (x,y), the count of this rectangle is:
-------------------------------
| . . |
| . . |
| . . |
|.. (u,v) --------- (u,y) |
| | | |
| | | |
| | | |
| | | |
|.. (x,v) --------- (x,y) |
| |
-------------------------------
Now, sitting on base row i we want to compute the best K-rose rectangle whose bottom edge is on i and whose top edge is on row i-k.
---------------------
| |
|---------------------|
| |
| Band of height k |
| |
|=====================|Base row
| |
| |
---------------------
For this, we use the sliding window technique from the Empty Plot problem.
---------------------
| |
|--l-----r------------|
| . . |
| . . |
| . . |
|=====================|Base row
| |
| |
---------------------
Given l and r, we can find the number of roses in this rectangle, using the counts we have calculated. This is really a one dimensional sliding window problem. If the count in the rectangle defined by l and r is less than or greater than K we expand/contract the window as before. If the count is exactly K, we compute the perimeter and note it down.
In this way, we can compute the best rectangle sitting on base row i as the minimum among all best rectangles whose top row ranges from 1 to k-1. For each top row, the sliding window takes time N. There are M rows above i, so this takes MN time.
Similarly, we can find all rectangles whose top row is the base row i and bottom row varies from i+1,…,M.
We do this for every base row, so this takes time M times MN = M2N overall.
In a similar way, we fix base columns and find the best rectangles to the left and right. This takes N times MN = N2M overall.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky