RookAttacks | Topcoder Archive

Problem Statement

This problem has a nonstandard time limit: 3 seconds.

You have a square chessboard with D rows and D columns. Both rows and columns are numbered from 0, and the square in row r, column c is denoted (r,c).

Some rooks are already placed onto the chessboard: For each valid i, there is a rook at (R0[i], C0[i]). The color of this rook is T0[i], where 0 means white and 1 means black. You will add up to steps additional rooks as described below.

Once you have placed all the rooks, look at the empty cells. We say that a rook A attacks an empty cell B if and only if:

A and B share the same row or the same column.
If there are any other cells between A and B (in the row/columm they share), these cells must all be empty.

Let E[w][b] be the number of empty cells that are attacked by exactly w white and b black rooks. Return a int[] with 25 elements: element 5*w + b of the return value should be E[w][b].

In order to generate the full input, run the following pseudocode:

for i = 0 .. length(R0)-1:
    add a rook at (R0[i], C0[i]) with color T0[i]

state = seed
for i = 0 .. steps-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    r = state % D
    state = (state * 1103515245 + 12345) modulo 2^31
    c = state % D
    state = (state * 1103515245 + 12345) modulo 2^31
    t = state div 2^30

    if cell (r,c) is still empty:
        add a rook at (r, c) with color t

Definition

Class:: RookAttacks
Method:: classify
Parameters:: int, int[], int[], int[], int, int
Returns:: long[]
Method signature:: long[] classify(int D, int[] R0, int[] C0, int[] T0, int seed, int steps)
(be sure your method is public)

Constraints

D will be between 1 and 10^9, inclusive.
R0 will have between 0 and 100 elements, inclusive.
C0 will have the same number of elements as R0.
T0 will have the same number of elements as R0.
Each element of R0 will be between 0 and D-1, inclusive.
Each element of C0 will be between 0 and D-1, inclusive.
Each element of T0 will be between 0 and 1, inclusive.
The rooks described by R0 and C0 will be placed on distinct cells.
seed will be between 0 and 2^31 - 1, inclusive.
steps will be between 0 and 99,900, inclusive.

Examples

```
8
```
```
{2}
```
```
{5}
```
```
{0}
```
```
47
```
```
0
```
```
Returns: {49, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
```
A standard 8x8 chessboard with a single white rook at (2,5). There are 14 empty cells attacked by a single white rook and 49 cells that are not attacked at all.

1000000000

{0, 0, 999999999, 999999999}

{0, 999999999, 0, 999999999}

{0, 0, 0, 1}

Returns: {999999996000000004, 0, 0, 0, 0, 0, 1999999996, 0, 0, 0, 1999999996, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

Four rooks in the corners of the largest possible chessboard. Three are white, one is black.

{1, 1, 1, 1, 0, 2, 3, 4}

{0, 4, 3, 1, 2, 2, 2, 2}

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

Returns: {0, 0, 16, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

The cell (1, 2) is attacked by four black rooks. Each other empty cell is attacked by two black rooks.

984567245

{}

{}

{}

Returns: {969372659926890025, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

A huge empty board.

```
10
```
```
{5}
```
```
{0}
```
```
{1}
```
```
3
```
```
7
```
```
Returns: {24, 30, 7, 0, 0, 19, 11, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
```
The pseudocode attempts to place the following additional rooks: r c t ----- 2 1 0 5 0 0 0 9 1 9 8 1 4 9 1 7 8 0 4 9 0 The white rook at (5,0) will not be placed because one of the initial rooks is already there. The white rook at (4,9) will not be placed because earlier a black rook was placed into the same cell.

{}

{}

{}

Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

The whole chessboard is full.

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.