ChessboardPuzzle | Topcoder Archive

Problem Statement

We have a huge chessboard that has exactly 10^9 rows and exactly 10^9 columns. Both rows and columns are numbered from 1 to 10^9. The cell (x, y) is white if x+y is even and black if x+y is odd.

You have n pawns, numbered 0 through n-1. Your task is to place each of the pawns onto some cell of the board. The placement must satisfy all the constraints specified below. Note that we use (x[i], y[i]) to denote the coordinates chosen for pawn i.

For each pawn you are given a rectangle that has to contain the pawn. More precisely, the coordinates of pawn i must satisfy xMin[i] <= x[i] <= xMax[i] and yMin[i] <= y[i] <= yMax[i].
For each pawn you are given the color of its cell: if color[i] is 'B', you must place pawn i onto a black cell, and if color[i] is 'W', pawn i must be placed onto a white cell.
You are given m distance constraints: for each valid j, the Manhattan distance between the cells containing pawns a[j] and b[j] must be d[j] or less.

Remember that the Manhattan distance between cells (x1, y1) and (x2, y2) is |x1-x2| + |y1-y2|. Note that it is allowed to place multiple pawns onto the same cell.

If there is no valid solution, return an empty int[]. Otherwise, return a int[] with 2n elements: {x[0], y[0], x[1], y[1], ..., x[n-1], y[n-1]}. If there are multiple valid solutions, you may return any one of them.

Definition

Class:: ChessboardPuzzle
Method:: solve
Parameters:: int[], int[], int[], int[], String, int[], int[], int[]
Returns:: int[]
Method signature:: int[] solve(int[] xMin, int[] xMax, int[] yMin, int[] yMax, String color, int[] a, int[] b, int[] d)
(be sure your method is public)

Constraints

n will be between 1 and 100, inclusive.
m will be between 0 and 500, inclusive.
xMin, xMax, yMin, yMax will contain exactly n elements.
color will contain exactly n characters.
Each element in xMin, xMax, yMin, yMax will be between 1 and 1,000,000,000, inclusive.
For each i, 0 <= xMax[i] - xMin[i] <= 1,000.
For each i, 0 <= yMax[i] - yMin[i] <= 1,000.
Each character in color will be 'B' or 'W'.
a, b and d will contain exactly m elements.
Each element in a will be between 0 and n-1, inclusive.
Each element in b will be between 0 and n-1, inclusive.
Each element in d will be between 0 and 2,000,000,000, inclusive.

Examples

```
{100}
```
```
{100}
```
```
{1000}
```
```
{1002}
```
```
"B"
```
```
{}
```
```
{}
```
```
{}
```
```
Returns: {100, 1001 }
```
Pawn 0 must be placed within the rectangle that contains the cells (100, 1000), (100, 1001), and (100, 1002). Pawn 0 must be placed onto a black cell. Only one of those three cells is black.
```
{1,1}
```
```
{1000,1000}
```
```
{1,1}
```
```
{1000,1000}
```
```
"BW"
```
```
{0}
```
```
{1}
```
```
{0}
```
```
Returns: { }
```
The only distance constraint specifies that pawns 0 and 1 must be in the same cell (as their Manhattan distance must be 0 or less). However, that is impossible because pawn 0 must be placed onto a black cell while pawn 1 must be placed onto a white cell.
```
{1,90}
```
```
{10,99}
```
```
{1,90}
```
```
{10,99}
```
```
"WW"
```
```
{0}
```
```
{1}
```
```
{160}
```
```
Returns: {10, 10, 90, 90 }
```
This is the only valid solution for this test case. For any other placement of pawns 0 and 1 within their rectangles the distance between the two pawns would be greater than 160.

{1,99}

{10,99}

{1,90}

{10,99}

"BB"

{0}

{1}

{160}

Returns: { }

This time there is no solution.

{2,4,8}

{2,6,8}

{1,1,1}

{9,9,9}

"WBW"

{1,1}

{0,2}

{3,3}

Returns: {2, 4, 5, 4, 8, 4 }

There are other solutions like {2, 8, 5, 8, 8, 8}.

{119270675,661036141,317802047,403448932,516377554,917798582,738592034,95318547,358245697,220768564}

{119271675,661037141,317803047,403449932,516378554,917799582,738593034,95319547,358246697,220769564}

{60896622,105824826,454680381,383505417,621850974,716617755,938547748,707367052,422848281,549512986}

{60897622,105825826,454681381,383506417,621851974,716618755,938548748,707368052,422849281,549513986}

"BBWBWBWBWW"

{7,7,6,7,1,0,9,1,2,1,4,8,4,2,1,6,4,4,8,2}

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

{831730738,506575093,890185433,670422563,867555377,600926681,590114259,692089649,2,1167259822,496187812,357134557,538911257,861933913,692089654,1496972489,538911260,660684742,264141842,72275753}

Returns: {119271671, 60897618, 661036148, 105825819, 317802549, 454680879, 403449932, 383506417, 516378052, 621851474, 917798582, 716617755, 738592038, 938547752, 95319047, 707367552, 358246199, 422848783, 220769064, 549513486 }

{1,1000000000}

{1,1000000000}

{1,1000000000}

{1,1000000000}

"WW"

{0,0,1,0,1}

{0,0,0,1,1}

{0,0,2000000000,2000000000,1000000000}

Returns: {1, 1, 1000000000, 1000000000 }

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.