Indian Computing Olympiad

Sliding Window Algorithms→Garden (IOI 2005)

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.

Solution

---