Statistics

Problem Statement for "ThreeDChessRooks"

Problem Statement

A 3D chessboard is a C x C x C cube. Rows, columns and floors are each numbered from 0 to C-1, inclusive.

A rook in 3D chess moves like a rook in traditional chess, except now we have six possible cardinal directions instead of four. When moving a rook we choose one of those six directions and move the rook a positive number of steps in the chosen direction. During the move the rook can only traverse through empty cells. The rook may end its move in a cell that contains a chess piece of the opposite color; that piece is then captured by the rook and removed from the board.


You are given a collection of R (not necessarily distinct) cells of the 3D chessboard. The cells in the collection are numbered from 0 to R-1, inclusive. Cell i has coordinates (X[i], Y[i], Z[i]). In order to keep the input size small, only a prefix of the coordinates is actually given, the rest will be pseudorandom.


Consider the following interaction:

  1. Wanda selected an index i (0 <= i <= R-1) and placed a white rook into cell i.
  2. Boris selected an index j (0 <= j <= R-1, cells i and j are not the same cell) and placed a black rook into cell j.
  3. Wanda made a valid move with her rook without capturing Boris's rook.
  4. Boris made a valid move with his rook and captured Wanda's rook with that move.

Count all ordered pairs (i, j) for which the above interaction could take place. Return that count.


The arrays X, Y and Z are defined as follows: 

---------------------------------------------------------

Pseudocode:

L = length(XP)
for i = 0 to L-1:
    X[i] = XP[i]
    Y[i] = YP[i]
    Z[i] = ZP[i]

state = seed
for i = L to R-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    X[i] = state modulo C
    state = (state * 1103515245 + 12345) modulo 2^31
    Y[i] = state modulo C
    state = (state * 1103515245 + 12345) modulo 2^31
    Z[i] = state modulo C

---------------------------------------------------------

C++:

vector<int> X(R), Y(R), Z(R);

int L = XP.size();
for (int i=0; i<L; ++i) { X[i]=XP[i]; Y[i]=YP[i]; Z[i]=ZP[i]; }

long long state = seed;
for (int i=L; i<R; ++i) {
    state = (state * 1103515245 + 12345) % (1LL << 31);
    X[i] = state % C;
    state = (state * 1103515245 + 12345) % (1LL << 31);
    Y[i] = state % C;
    state = (state * 1103515245 + 12345) % (1LL << 31);
    Z[i] = state % C;
}

---------------------------------------------------------

Java:

int[] X = new int[R];
int[] Y = new int[R];
int[] Z = new int[R];

int L = XP.length;
for (int i=0; i<L; ++i) { X[i]=XP[i]; Y[i]=YP[i]; Z[i]=ZP[i]; }

long state = seed;
for (int i=L; i<R; ++i) {
    state = (state * 1103515245 + 12345) % (1L << 31);
    X[i] = (int)(state % C);
    state = (state * 1103515245 + 12345) % (1L << 31);
    Y[i] = (int)(state % C);
    state = (state * 1103515245 + 12345) % (1L << 31);
    Z[i] = (int)(state % C);
}

Definition

Class:
ThreeDChessRooks
Method:
count
Parameters:
int, int, int[], int[], int[], int
Returns:
long
Method signature:
long count(int C, int R, int[] XP, int[] YP, int[] ZP, int seed)
(be sure your method is public)

Notes

  • The reference solution does not depend on the input being pseudorandom.
  • Remember that during a valid move a rook must move by at least one cell. Leaving a rook in its current cell is not a valid move.

Constraints

  • C will be between 2 and 1,000,000, inclusive.
  • R will be between 1 and 100,000, inclusive.
  • XP will have between 0 and 100 elements, inclusive.
  • XP will have at most R elements.
  • YP and ZP will each have the same number of elements as XP.
  • Each element of XP, YP and ZP will be between 0 and C-1, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.

Examples

  1. 10

    4

    {0, 0, 0, 0}

    {0, 0, 0, 0}

    {2, 3, 5, 7}

    0

    Returns: 12

    We have a 10x10x10 cube. The collection contains four cells, their coordinates are (0,0,2), (0,0,3), (0,0,5) and (0,0,7). Clearly, Wanda can select any of these four cells and then Boris can select any of the remaining three, giving us 4*3 = 12 valid pairs (i,j). For example: Wanda selects i=1 and thus places the white rook at (0,0,3). Boris selects j=3 and thus places the black rook at (0,0,7). Wanda moves her rook to (0,0,6). Boris moves his rook to (0,0,6) and captures Wanda's rook.

  2. 10

    4

    {1, 1, 1, 1}

    {4, 4, 4, 4}

    {0, 0, 0, 0}

    0

    Returns: 0

    All four cells in this collection are identical. Regardless of which i Wanda chooses, Boris cannot choose any valid j.

  3. 10

    4

    {9, 2, 3, 4}

    {5, 6, 7, 8}

    {9, 0, 1, 9}

    0

    Returns: 2

    The only two pairs of indices that work for this collection are (0,3) and (3,0). For example, (0,3) works because this is one possible interaction: Wanda selects i=0 and places the white rook at (9,5,9). Boris selects j=3 and places the black rook at (4,8,9). Wanda moves her rook to (4,5,9). Boris moves his rook to (4,5,9) and captures Wanda's rook.

  4. 10

    10

    {9, 2, 3, 4}

    {5, 6, 7, 8}

    {9, 0, 1, 9}

    47474747

    Returns: 16

    The collection starts as in Example 2, but now we have additional rooks with pseudorandom coordinates. Complete collection: X = {9, 2, 3, 4, 8, 5, 2, 3, 0, 3} Y = {5, 6, 7, 8, 1, 8, 1, 2, 9, 0} Z = {9, 0, 1, 9, 8, 7, 6, 5, 4, 7}

  5. 3

    10

    {2, 1, 0}

    {1, 1, 2}

    {0, 0, 1}

    47474747

    Returns: 54

    Here we have additional rooks with pseudorandom coordinates. The arrays X, Y, Z look as follows: X = { 2, 1, 0, 2, 0, 0, 0, 0, 0, 1 } Y = { 1, 1, 2, 1, 2, 1, 1, 2, 1, 1 } Z = { 0, 0, 1, 1, 2, 2, 2, 1, 2, 2 }

  6. 10

    7

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

    {4, 7, 4, 7, 4, 7, 4}

    {2, 2, 2, 2, 2, 2, 2}

    42

    Returns: 24

    Note that we are counting pairs of indices, not pairs of cells. Here, each pair of indices (i, j) where i and j have a different parity works.

  7. 99

    8

    {47, 48, 49, 50, 50, 51, 52, 53}

    {12, 12, 12, 12, 12, 12, 12, 12}

    {12, 12, 12, 12, 12, 12, 12, 12}

    111

    Returns: 54

    Each of the 8*7 = 56 pairs of indices works, except for the pairs (3, 4) and (4, 3) which both represent the same cell. Boris cannot place the black rook into the cell that is, at that moment, occupied by Wanda's white rook.

  8. 1000000

    100000

    {}

    {}

    {}

    47

    Returns: 29858

  9. 9997

    100000

    {}

    {}

    {}

    457347

    Returns: 3000190

  10. 19997

    100000

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

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

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

    12523632

    Returns: 1499708

  11. 997

    100000

    {}

    {}

    {}

    235

    Returns: 30067022

  12. 7

    100000

    {}

    {}

    {}

    23523

    Returns: 3648404024

  13. 18

    100000

    {}

    {}

    {}

    644

    Returns: 1481401702

  14. 16

    100000

    {}

    {}

    {}

    2363427

    Returns: 0

  15. 17

    100000

    {}

    {}

    {}

    235235

    Returns: 1660146951

  16. 47

    100000

    {}

    {}

    {}

    235326

    Returns: 624633913

  17. 100

    99997

    {}

    {}

    {}

    23326673

    Returns: 287937018

  18. 2

    2

    {1, 1}

    {0, 1}

    {0, 0}

    0

    Returns: 0

  19. 3

    100000

    { }

    { }

    { }

    0

    Returns: 5925404289

  20. 3

    15

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

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

    {0, 0, 0, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1 }

    0

    Returns: 100

  21. 10

    2

    {0, 0 }

    {0, 0 }

    {0, 1 }

    0

    Returns: 1

  22. 10

    4

    {6, 6, 6, 6 }

    {8, 9, 0, 1 }

    {5, 5, 5, 5 }

    0

    Returns: 10

  23. 10

    10

    {0, 0 }

    {0, 1 }

    {0, 0 }

    1

    Returns: 15

  24. 2

    3

    {1, 1, 1 }

    {0, 0, 0 }

    {0, 0, 0 }

    0

    Returns: 0

  25. 3

    3

    {0, 1, 1 }

    {0, 0, 0 }

    {0, 0, 0 }

    0

    Returns: 2

  26. 1000000

    100000

    {9, 2, 3, 4 }

    {5, 6, 7, 8 }

    {9, 0, 1, 9 }

    123456789

    Returns: 29666

  27. 1000000

    100000

    {1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 20009, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534, 1, 2, 3, 545, 34, 33, 55, 33434, 6546, 34534 }

    {342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32, 342, 324, 5434, 234233, 45, 65, 343, 345, 34, 32 }

    {7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989, 7884, 39458, 39485, 93845, 93845, 9398, 93849, 98, 9839, 989 }

    2147483644

    Returns: 29916

  28. 4

    4

    {1, 0, 0, 0 }

    {0, 1, 0, 0 }

    {0, 0, 1, 0 }

    0

    Returns: 9

  29. 1000000

    100000

    {0, 0, 0, 0 }

    {0, 0, 0, 0 }

    {0, 0, 0, 0 }

    100000

    Returns: 29836

  30. 99

    8

    {47, 48, 49, 50, 50, 51, 52, 53 }

    {12, 12, 12, 12, 12, 12, 11, 12 }

    {12, 12, 12, 12, 12, 12, 12, 12 }

    111

    Returns: 54

  31. 5

    4

    {0, 0, 0, 0 }

    {0, 0, 0, 0 }

    {0, 1, 3, 4 }

    100

    Returns: 10

  32. 100

    2

    {0, 0 }

    {0, 0 }

    {98, 99 }

    0

    Returns: 1

  33. 2

    2

    {0, 0 }

    {0, 1 }

    {0, 1 }

    0

    Returns: 2

  34. 2

    3

    {1, 1, 1 }

    {1, 1, 1 }

    {1, 1, 1 }

    0

    Returns: 0

  35. 3

    2

    {1, 1 }

    {0, 1 }

    {1, 1 }

    312

    Returns: 1

  36. 2

    100000

    {1 }

    {0 }

    {1 }

    4

    Returns: 0

  37. 10

    7

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

    {4, 7, 4, 7, 4, 7, 4 }

    {2, 2, 2, 2, 2, 2, 2 }

    42

    Returns: 24

  38. 3

    2

    {1, 1 }

    {1, 2 }

    {1, 1 }

    0

    Returns: 1

  39. 99

    18888

    {47, 48, 49, 50, 50, 51, 52, 53 }

    {12, 12, 12, 12, 12, 12, 12, 12 }

    {12, 12, 12, 12, 12, 12, 12, 12 }

    111

    Returns: 10707083

  40. 2

    100000

    {1, 1 }

    {1, 1 }

    {1, 1 }

    12133

    Returns: 199996

  41. 3

    2

    {2, 2 }

    {2, 2 }

    {2, 1 }

    1

    Returns: 1

  42. 10

    2

    {0, 1 }

    {5, 5 }

    {5, 5 }

    0

    Returns: 1

  43. 99

    99999

    {47, 48, 49, 50, 50, 51, 52, 53 }

    {12, 12, 12, 12, 12, 12, 12, 12 }

    {12, 12, 12, 12, 12, 12, 12, 12 }

    111

    Returns: 299973041

  44. 999999

    99999

    {7 }

    {11 }

    {13 }

    31

    Returns: 30048

  45. 3

    3

    {0, 0, 0 }

    {0, 0, 0 }

    {0, 1, 2 }

    1

    Returns: 4

  46. 4

    2

    {1, 1 }

    {2, 2 }

    {0, 1 }

    0

    Returns: 1

  47. 4

    4

    {0, 0, 0, 0 }

    {0, 0, 0, 0 }

    {0, 1, 2, 3 }

    0

    Returns: 10

  48. 1000000

    100000

    {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2 }

    {0, 0, 1, 0, 0, 0, 0, 2, 0, 1, 1, 0, 2, 1, 0 }

    {0, 1, 0, 0, 0, 0, 1, 0, 2, 1, 1, 2, 2, 0, 1 }

    21412513

    Returns: 30204

  49. 987654

    100000

    {91119, 171717, 42442 }

    {42426, 666, 13374 }

    {123, 456, 789 }

    1234567

    Returns: 30246

  50. 5

    5

    {0, 0 }

    {0, 1 }

    {0, 0 }

    1

    Returns: 11

  51. 10

    100000

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

    {4, 7, 4, 7, 4, 7, 4 }

    {2, 2, 2, 2, 2, 2, 2 }

    42

    Returns: 2400025574

  52. 3

    2

    {0, 0 }

    {0, 0 }

    {0, 1 }

    0

    Returns: 1

  53. 5

    5

    {0, 0, 0, 0, 0 }

    {0, 0, 0, 0, 0 }

    {0, 1, 2, 3, 4 }

    1000

    Returns: 18

  54. 10

    100000

    {9, 2, 3, 4 }

    {5, 6, 7, 8 }

    {9, 0, 1, 9 }

    47474747

    Returns: 2399961304

  55. 10

    4

    {0, 0, 0, 1 }

    {0, 0, 1, 0 }

    {0, 1, 0, 0 }

    12345

    Returns: 9

  56. 2

    2

    {0, 1 }

    {0, 0 }

    {0, 1 }

    0

    Returns: 2

  57. 1000000

    100000

    {6, 5, 2 }

    {7, 3, 1 }

    {0, 4, 2 }

    5

    Returns: 30070

  58. 1000

    2

    {0, 0 }

    {0, 0 }

    {0, 1 }

    1

    Returns: 1

  59. 3

    2

    {0, 0 }

    {1, 1 }

    {1, 2 }

    0

    Returns: 1

  60. 100

    3

    {0, 0, 1 }

    {5, 5, 5 }

    {5, 5, 5 }

    0

    Returns: 2

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.
This problem was used for: