BearGridRect | Topcoder Archive

Problem Statement

Bear Limak has a grid with N rows and N columns. Rows are numbered 0 through N-1, from top to bottom. Columns are numbered 0 through N-1, from left to right.

Limak is going to place N pawns on the grid. There must be exactly one pawn in each row, and exactly one pawn in each column.

There are M companies. Each of them bought one non-empty rectangle in Limak's grid. The i-th company bought a rectangle with coordinates r1[i], r2[i], c1[i], c2[i]. That is, the i-th company owns the cell in the intersection of the r-th row and the c-th column if and only if r1[i] ≤ r ≤ r2[i] and c1[i] ≤ c ≤ c2[i]. Of course, every cell belongs to at most one company. (I.e., it is guaranteed that the rectangles are disjoint.)

Every company wants some particular number of pawns in their rectangle. There must be exactly cnt[i] pawns on the rectangle owned by the i-th company.

You are given the int N and the int[]s r1, r2, c1, c2, and cnt. Help Limak and find any placement of pawns for which all the conditions are satisfied. Return a int[] X with N elements, defined as follows: For each i, there is exactly one pawn in row i, and X[i] is the column in which you'll find that pawn.

If there is no solution, return {-1} instead. (I.e., the return value is a int[] with one element, and the value of that element is -1.)

Definition

Class:: BearGridRect
Method:: findPermutation
Parameters:: int, int[], int[], int[], int[], int[]
Returns:: int[]
Method signature:: int[] findPermutation(int N, int[] r1, int[] r2, int[] c1, int[] c2, int[] cnt)
(be sure your method is public)

Constraints

N will be between 2 and 50, inclusive.
M will be between 1 and 50, inclusive.
Each of r1, r2, c1, c2 and cnt will contain exactly M elements.
Each element in cnt will be between 0 and N, inclusive.
For every i between 0 and M-1, inclusive, we will have 0 ≤ r1[i] ≤ r2[i] ≤ N-1.
For every i between 0 and M-1, inclusive, we will have 0 ≤ c1[i] ≤ c2[i] ≤ N-1.
Every cell belongs to at most one company.

Examples

```
5
```
```
{4, 0}
```
```
{4, 1}
```
```
{2, 1}
```
```
{4, 2}
```
```
{0, 2}
```
```
Returns: {1, 2, 4, 3, 0 }
```
The left drawing below shows rectangles owned by companies. There must be 0 pawns on a red rectangle, and there must be 2 pawns on a blue rectangle. The right drawing shows one of valid solutions.

{4, 0, 2}

{4, 1, 2}

{2, 1, 2}

{4, 2, 2}

{0, 2, 1}

Returns: {-1 }

```
3
```
```
{0}
```
```
{2}
```
```
{0}
```
```
{2}
```
```
{0}
```
```
Returns: {-1 }
```
There is one company and it owns all cells. They want 0 pawns on their rectangle. It's impossible because there must be three pawns in total.
```
4
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{0}
```
```
Returns: {1, 0, 2, 3 }
```

{0, 0, 1, 1}

{0, 0, 1, 1}

{0, 1, 0, 1}

{0, 1, 0, 1}

{0, 1, 1, 0}

Returns: {1, 0 }

{0, 0, 1, 1}

{0, 0, 1, 1}

{0, 1, 0, 1}

{0, 1, 0, 1}

{0, 1, 0, 1}

Returns: {-1 }

{0, 0, 1, 1}

{0, 0, 1, 1}

{0, 1, 0, 1}

{0, 1, 0, 1}

{1, 1, 1, 1}

Returns: {-1 }

{0, 0, 4}

{2, 3, 5}

{0, 5, 1}

{4, 5, 5}

{3, 1, 1}

Returns: {1, 2, 4, 5, 3, 0 }

```
3
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{2}
```
```
Returns: {-1 }
```

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.