Connection Status:
Competition Arena > ChessboardPuzzle

ChessboardPuzzle

2017 TCO Semi 2 · 2017-03-31 · by cgy4ever

2017 TCO Semi 2 · 2017-03-31 · by cgy4ever · Graph Theory
Class Name: ChessboardPuzzle
Return Type: int[]
Method Name: solve
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, string, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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
0)
{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,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.

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

3)
{1,99}
{10,99}
{1,90}
{10,99}
"BB"
{0}
{1}
{160}
Returns: { }

This time there is no solution.

4)
{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}.

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

Coding Area

Language: C++17 · define a public class ChessboardPuzzle with a public method vector<int> solve(vector<int> xMin, vector<int> xMax, vector<int> yMin, vector<int> yMax, string color, vector<int> a, vector<int> b, vector<int> d) · 170 test cases · 2 s / 256 MB per case

Submitting as anonymous