RookAttacks
TCO19 Wildcard Fun Round · 2019-08-16 · by misof
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
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
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.
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}
47
0
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.
5
{1, 1, 1, 1, 0, 2, 3, 4}
{0, 4, 3, 1, 2, 2, 2, 2}
{1, 1, 1, 1, 1, 1, 1, 1}
47
0
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
{}
{}
{}
4747
0
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.
11
{}
{}
{}
42
5497
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.
Submissions are judged against all 96 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RookAttacks with a public method vector<long long> classify(int D, vector<int> R0, vector<int> C0, vector<int> T0, int seed, int steps) · 96 test cases · 2 s / 256 MB per case