Problem Statement |
| | Prizes
- 1st Place: $1,000
- 2nd Place: $750
- 3rd Place: $500
- 4th Place: $250
You are given the coordinates of N chess queens placed on an infinite chess board. Your goal is to make some valid moves to rearrange the queens so that in the end no two queens threaten each other (i.e., no two queens share the same row, column or diagonal).
The coordinates of the queens are given as int[]s queenRows and queenCols of the same length N. You have to return the list of moves as a String[]. You can use at most 8*N moves. Each element of your return should be formatted as "INDEX ROW COL"; the corresponding move will move queen INDEX (0-based) from its current position to a cell with coordinates (ROW, COL). Each move must be a valid chess queen move: the queen can be moved any number of unoccupied squares in a straight line vertically, horizontally or diagonally.
Scoring
Your raw score for a test case will be the sum of Chebyshev distances between starting cell and end cell of each move, and your goal is to minimize it. If your return was invalid (had too many moves, used invalid moves or resulted in a pair of queens threatening each other), your raw score for a test case will be 0. Your overall score will be the sum of MIN/YOUR over all test cases, where YOUR is your raw score on a test case, and MIN is the smallest score achieved by anyone on that test case (test cases on which you scored 0 don't contribute to the sum).
Test case generation
Each test case is generated as follows:
- number of queens N is chosen uniformly, at random, between 8 and 100, inclusive.
- queens are placed randomly in squares of SZ x SZ area, where SZ is chosen uniformly at random between sqrt(N) and 2 * sqrt(N).
Tools
An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation. |
| |
Definition |
| | | Class: | MovingNQueens | | Method: | rearrange | | Parameters: | int[], int[] | | Returns: | String[] | | Method signature: | String[] rearrange(int[] queenRows, int[] queenCols) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes. |
| - | There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. |
| - | The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. |
| - | There are 10 example test cases and 100 full submission (provisional) test cases. |
| |
Examples |
| 0) | |
| | | Returns: "Seed = 1
Number of queens = 8
(3,0) (0,1) (1,1) (0,3) (1,2) (4,2) (0,4) (2,3) " | |
|
| 1) | |
| | | Returns:
"Seed = 2
Number of queens = 41
(3,11) (0,11) (4,10) (4,8) (9,3) (4,1) (4,6) (10,6) (9,1) (9,7)
(5,6) (6,2) (9,10) (10,8) (2,2) (2,1) (0,8) (6,7) (8,8) (7,3)
(9,0) (6,4) (1,5) (0,10) (4,0) (11,3) (0,9) (11,6) (10,1) (0,5)
(8,3) (1,3) (9,4) (1,8) (7,6) (5,8) (8,2) (3,2) (0,0) (4,4)
(5,3) " | |
|
| 2) | |
| | | Returns:
"Seed = 3
Number of queens = 18
(2,3) (0,4) (2,1) (1,3) (1,4) (0,0) (4,4) (2,4) (4,2) (1,2)
(3,1) (2,2) (2,0) (0,1) (1,0) (4,0) (3,4) (3,2) " | |
|
| 3) | |
| | | Returns:
"Seed = 4
Number of queens = 89
(1,2) (4,6) (7,6) (9,4) (14,0) (9,5) (5,5) (8,0) (4,0) (5,11)
(8,8) (17,1) (3,11) (9,7) (9,2) (13,0) (1,1) (14,13) (11,17) (0,15)
(1,15) (2,4) (3,0) (5,16) (12,5) (16,17) (12,0) (13,17) (1,12) (6,10)
(2,13) (14,12) (11,15) (6,11) (6,15) (17,13) (12,11) (17,16) (10,12) (6,3)
(1,14) (0,6) (5,4) (10,14) (0,4) (4,13) (10,13) (15,5) (15,12) (3,3)
(9,16) (11,9) (11,7) (7,4) (0,10) (3,16) (5,8) (16,2) (13,16) (9,6)
(4,9) (5,12) (6,9) (13,3) (16,8) (0,12) (17,8) (4,11) (10,1) (4,1)
(11,6) (7,16) (10,17) (7,5) (7,15) (8,13) (12,15) (13,11) (1,11) (0,8)
(2,9) (7,0) (14,7) (17,10) (7,11) (15,1) (11,12) (1,3) (5,13) " | |
|
| 4) | |
| | | Returns:
"Seed = 5
Number of queens = 10
(3,5) (0,3) (1,0) (4,0) (4,3) (0,4) (0,1) (4,4) (5,4) (2,0)
" | |
|
| 5) | |
| | | Returns:
"Seed = 6
Number of queens = 56
(9,7) (0,7) (1,8) (0,3) (3,9) (9,8) (2,0) (1,5) (4,9) (3,7)
(7,10) (6,8) (2,4) (8,8) (5,1) (6,5) (5,8) (4,7) (0,5) (2,3)
(7,6) (4,2) (4,0) (10,5) (10,10) (9,0) (10,2) (7,3) (7,2) (2,5)
(0,10) (8,5) (10,4) (0,2) (6,9) (2,10) (6,3) (8,2) (3,5) (7,0)
(5,4) (3,4) (7,1) (0,0) (8,7) (1,1) (1,2) (4,5) (3,10) (6,10)
(1,0) (8,9) (8,6) (4,8) (3,3) (6,4) " | |
|
| 6) | |
| | | Returns:
"Seed = 7
Number of queens = 11
(3,0) (0,5) (0,0) (2,4) (4,1) (3,1) (5,3) (1,3) (2,3) (5,5)
(0,2) " | |
|
| 7) | |
| | | Returns:
"Seed = 8
Number of queens = 60
(3,4) (3,7) (0,12) (4,13) (8,12) (0,9) (7,13) (0,5) (5,0) (5,6)
(1,5) (7,1) (12,11) (13,8) (10,0) (4,10) (3,10) (11,8) (6,2) (13,10)
(8,2) (5,8) (1,2) (1,0) (3,0) (9,7) (1,9) (6,9) (8,7) (8,9)
(7,10) (12,12) (11,1) (7,0) (9,1) (6,3) (3,6) (4,2) (4,8) (13,11)
(6,13) (9,8) (4,12) (8,11) (12,13) (10,6) (10,2) (5,5) (8,6) (7,2)
(6,0) (7,6) (9,4) (8,5) (3,5) (6,11) (2,7) (9,0) (5,10) (9,10)
" | |
|
| 8) | |
| | | Returns:
"Seed = 9
Number of queens = 87
(3,6) (9,0) (5,8) (0,12) (4,1) (5,6) (6,13) (8,0) (7,4) (6,8)
(3,12) (13,13) (12,5) (9,11) (4,4) (0,3) (1,3) (10,9) (10,5) (6,1)
(2,0) (0,5) (2,4) (5,10) (1,11) (2,11) (10,2) (12,13) (11,7) (0,7)
(11,9) (9,7) (6,7) (10,13) (8,11) (5,12) (13,4) (2,10) (11,8) (11,0)
(11,5) (8,10) (7,5) (3,7) (3,2) (11,2) (12,0) (13,11) (5,13) (1,8)
(7,10) (8,1) (6,11) (8,8) (4,2) (7,9) (9,1) (11,11) (7,13) (8,6)
(9,8) (4,7) (2,12) (12,1) (8,4) (2,7) (10,4) (2,3) (3,9) (13,1)
(1,13) (6,10) (7,12) (5,7) (11,3) (9,4) (9,6) (10,8) (4,3) (3,8)
(0,8) (0,1) (7,11) (2,6) (10,10) (7,0) (6,4) " | |
|
| 9) | |
| | | Returns:
"Seed = 10
Number of queens = 33
(3,0) (8,0) (7,6) (5,5) (7,1) (1,3) (1,1) (1,2) (5,7) (3,4)
(2,3) (5,3) (2,1) (4,2) (8,4) (3,2) (2,2) (3,5) (0,8) (7,0)
(7,2) (1,6) (4,8) (8,6) (7,7) (2,8) (6,0) (4,1) (0,7) (5,0)
(3,6) (6,5) (5,6) " | |
|
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)2020, TopCoder, Inc. All rights reserved.