CoverSquare | Topcoder Archive

Problem Statement

We have a square in the plane. The sides of the square are parallel to the coordinate axes. The bottom left corner of the square is (0, 0), and its top right corner is (s, s).

The square is feeling cold, so we have to cover it with blankets. We have a supply of different square blankets with total area at least 3*s^2. Cover the square completely. Some blankets may overlap each other. Some blankets may lay partially outside the square, but each blanket must be used and each blanket must at least partially cover the square. Additionally, we require that their sides must be parallel to coordinate axes and their vertex coordinates must be integers.

You are given the side length of each blanket in the int[] blankets. Return a int[] of the form {x0, y0, x1, y1, x2, y2, ...}, where (xi, yi) is the bottom left corner of the area that should be covered by blanket i. A solution always exists, and any valid solution will be accepted.

Definition

Class:: CoverSquare
Method:: cover
Parameters:: int, int[]
Returns:: int[]
Method signature:: int[] cover(int s, int[] blankets)
(be sure your method is public)

Constraints

s will be between 1 and 10^6, inclusive.
blankets will have between 1 and 500 elements, inclusive.
Each element of blankets will be between 1 and 10^6, inclusive.
The total area of blankets will be at least three times the area of the cold square.

Examples

```
10
```
```
{9, 9, 9, 9}
```
```
Returns: {0, 0, 1, 0, 1, 1, 0, 1 }
```
We can place the four blankets to match the four corners of the square we are covering.
```
100
```
```
{90, 90, 90, 90}
```
```
Returns: {-30, -50, 60, -50, 60, 40, -30, 40 }
```
Another valid solution for essentially the same situation as in example 0. This time, the blankets are sticking a bit outside the square so that each part of the square is only covered once.

{1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1}

Returns: {0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 2, 2, 0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 2, 2, 0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 2, 2 }

We have a surplus of blankets. In the example output we use them to cover the entire square three times. Remember that each blanket must at least partially overlap the square, so make sure you do not place the extra ones outside.

{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9}

Returns: {0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 4, 4, 0, 0 }

```
100000
```
```
{180000}
```
```
Returns: {0, 0 }
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.