Indian Computing Olympiad

Training Material

Range Queries→Artemis (IOI 2004)

Zeus gave Artemis, the goddess of the wilderness, a rectangular area for growing a forest. With the left side of the area as a segment of the positive y-axis and the bottom side as a segment of the positive x-axis, and (0,0) the left bottom corner of the area, Zeus told Artemis to only plant trees only on integer coordinate points in the area. Artemis liked the forest to look natural, and therefore planted trees in such a way that a line connecting two trees was never parallel to x-axis or y-axis. At times, Zeus wants Artemis to cut trees for him. The trees are to be cut as follows:

  1. Zeus wants at least a given number T of trees to be cut for him.

  2. To get a rectangular football pitch for future football success, Artemis is to cut all trees within a rectangular area, and no trees outside of it.

  3. The sides of this rectangular area are to be parallel to x-axis and y-axis.

  4. Two opposite corners of the area trees must be located on trees and therefore those corner trees are also cutstand in two opposite corners of the area (and are included in it).

As Artemis likes the trees, she wants to fulfill these conditions whilst cutting as few trees as possible. You are to write a program that, given information of on the forest and the minimum number T of trees to be cut, selects an area for cutting trees for Artemis.

Limits:

  • Grid is 64000 × 64000
  • Number of trees is 10000 (was 20000 in IOI, but this seems wrong!)
  • Memory is 16MB

Solution

Easy algorithm stores the number of trees from (0,0) to (i,j) for all trees (i,j), but this is not feasible given the memory limit.

Assume we are processing trees in ascending order of first coordinates. Fix a tree (x,y) for which we want to calculate the best rectangle with respect to all earlier trees to the left of (x,y). 

 |        (x',y)
 |------------------------o(x,y)
 |          |             |
 |          |             |
 |          |             |
 |          |             |
 |          |             |
 |          | (x',y')     |
 |----------o-------------|(x,y')
 |          |             |
 |          |             |
 |          |             |
 |          |             |
  --------------------------------------

Keep two linear arrays

  • For each 1 ≤ j ≤ y, V[j] = 1 if there is a tree at some (z,j)
  • For each 1 ≤ i ≤ x, H[i] = 1 if there is a tree at some (i,z)

Prefix sums for H[] and V[] tell us number of trees to the left of some i and below some j.

For each tree (x",y") to the left of (x,y), assume we have stored the number of trees between (0,0) and (x",y"). Call this Between(0,0,x",y").

We can then get the number of trees between (x',y') and (x,y) as

PrefixY(y) - [PrefixX(x') + PrefixY(y') - Between(0,0,x',y')]

We check if the number of trees in this rectangle is more than T and better than the best we know. If so, keep it, else throw it away.

In this way, after sorting the trees (N log N), we can process each tree in time N, so overall is N2. The space we use is proportional to N (for each tree (x,y) store Between(0,0,x,y)).


Problems related to