BearGridRect

2016 TCO Algo Parallel 2C · 2016-03-24 · by Errichto

2016 TCO Algo Parallel 2C · 2016-03-24 · by Errichto · Brute Force

Show categories

Class Name: BearGridRect

Return Type: int[]

Method Name: findPermutation

Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>, vector<int>)

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.)

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.

5
{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 }

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

Submissions are judged against all 153 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BearGridRect with a public method vector<int> findPermutation(int N, vector<int> r1, vector<int> r2, vector<int> c1, vector<int> c2, vector<int> cnt) · 153 test cases · 2 s / 256 MB per case