IOI '16 - Kazan, Russia

Aliens

Our satellite has just discovered an alien civilization on a remote planet. We have already obtained a low-resolution photo of a square area of the planet. The photo shows many signs of intelligent life. Our experts have identified n points of interest in the photo. The points are numbered from 0 to n − 1. We now want to take high-resolution photos that contain all of those n points.

Internally, the satellite has divided the area of the low-resolution photo into an m by m grid of unit square cells. Both rows and columns of the grid are consecutively numbered from 0 to m − 1 (from the top and left, respectively). We use (s, t) to denote the cell in row s and column t. The point number i is located in the cell (r_i, c_i). Each cell may contain an arbitrary number of these points.

Our satellite is on a stable orbit that passes directly over the main diagonal of the grid. The main diagonal is the line segment that connects the top left and the bottom right corner of the grid. The satellite can take a high-resolution photo of any area that satisfies the following constraints:

• the shape of the area is a square,
• two opposite corners of the square both lie on the main diagonal of the grid,
• each cell of the grid is either completely inside or completely outside the photographed area.

The satellite is able to take at most k high-resolution photos.

Once the satellite is done taking photos, it will transmit the high-resolution photos of each photographed cell to our home base (regardless of whether that cell contains some points of interest). The data for each photographed cell will only be transmitted once, even if the cell was photographed several times.

Thus, we have to choose at most k square area that will be photographed, assuring that:

• each cell containing at least one point of interest is photographed at least once, and
• the number of cells that are photographed at least once are minimized.

Your task is to find the smallest possible total number of photographed cells.

You should implement one operation take_photos:

• take_photos(n, m, k, r[], c[])
  • n: the number of points of interest,
  • m: the number of rows (and also columns) in the grid,
  • k: the maximum number of points the satellite can take,
  • r and c: two arrays of length n describing the coordinates of the grid cells that contain points of interest. For 0 ≤ i ≤ n − 1, the i-th point of interest is located in the cell (r_i, c_i),
  • your program should output the smallest possible total number of cells that are photographed at least once (given that the photos must cover all points of interest).

Input Format

The input will be given in the following format:

• Line 1: space-separated integers n, m and k
• Line 2 + i (0 ≤ i ≤ n − 1): space-separated integers r_i and c_i.

Output Format

Your output should be in the following format:

• Line 1: a single integer denoting the minimum possible number of cells that must be photographed

Sample Input 1

5 7 2
0 3
4 4
4 6
4 5
4 6

Sample Output 1

25

Explanation 1

In this example we have a 7×7 grid with 5 points of interest. The points of interest are located in four different cells: (0, 3), (4, 4), (4, 5) and (4, 6). You may take at most 2 high-resolution photos.

One way to capture all five points of interest is to make two photos: a photo of the 6×6 square containing the cells (0, 0) and (5, 5), and a photo of the 3×3 square containing the cells (4, 4) and (6, 6). If the satellite takes these two photos, it will transmit the data about 41 cells. This amount is not optimal.

The optimal solution uses one photo to capture the 4×4 square containing cells (0, 0) and (3, 3) and another photo to capture the 3×3 square containing cells (4, 4) and (6, 6). This results in only 25 photographed cells, which is optimal.

Note that it is sufficient to photograph the cell (4, 6) once, even though it contains two points of interest.

The example is shown in the figures below. The leftmost figure shows the grid that corresponds to the sample input. The middle figure shows a suboptimal solution in which 41 cells are photographed. The rightmost figure shows the optimal solution.

Sample input 2

2 6 2
1 4
4 1

Sample Output 2

16

Explanation 2

Here we have 2 points of interest located symmetrically: in the cells (1, 4) and (4, 1). Any valid photo that contains one of them contains the other as well. Therefore, it is sufficient to use a single photo.

The figures below show this sample and its optimal solution. In this solution the satellite captures a single photo of 16 cells.

Subtasks

For all subtasks, 1 ≤ k ≤ n.

1. (4% of points) 1 ≤ n ≤ 50, 1 ≤ m ≤ 100, k = n,
2. (12% of points) 1 ≤ n ≤ 500, 1 ≤ m ≤ 1000, for all i such that 0 ≤ i ≤ n − 1, r_i = c_i,
3. (9% of points) 1 ≤ n ≤ 500, 1 ≤ m ≤ 1000,
4. (16% of points) 1 ≤ n ≤ 4000, 1 ≤ m ≤ 1 000 000,
5. (19% of points) 1 ≤ n ≤ 50 000, 1 ≤ k ≤ 100, 1 ≤ m ≤ 1 000 000,
6. (40% of points) 1 ≤ n ≤ 100 000, 1 ≤ m ≤ 1 000 000.

All Submissions
Best Solutions

Point Value: 40 (partial)
Time Limit: 2.00s
Memory Limit: 2048M
Added: Aug 10, 2017

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I don't think 2048 MB is the correct memory limit? 

According to [url=http://ioinformatics.org/locations/ioi16/contest/day2/day2_notice.pdf]the official statement[/url], it is.