Problem Statement |
| | You are exploring a maze represented by an S x S board of cells (which wraps around horizontally and vertically). Each cell either is empty (a hole) or contains a tile - a wildcard or a number between 1 and N, inclusive.
You start on a random tile with a number greater than 1 on it. In one step you can move from your current tile to a tile vertically or horizontally adjacent to it. Your goal is to visit tiles with numbers 1, 2, ..., N, in that order. You can visit tiles with other numbers out of order, but visiting those tiles does not count toward the goal. Furthermore, after you've visited a tile with a number K on it for the first time, the tiles with numbers K+2, K+3, ..., N will be destroyed once you step on them, until you visit a tile with a number K+1 on it (this tile is not destroyed).
Wildcard tiles are special: when you step on a wildcard tile while looking for a tile with a number K on it, the wildcard tile becomes a tile with the number K and counts toward your goal. After that this tile behaves like a regular tile with the number K and is not updated again.
-
If there are several tiles with a number K on them in the maze, visiting any one of them (or a wildcard tile instead of any of them) will count toward your goal.
-
You can stand on a cell with a hole only if you have just destroyed the tile which used to be there by stepping on it. You can never enter cells with holes.
-
It is guaranteed that for each of the numbers 1, 2, ..., N there is at least one tile with this number on it in the maze.
-
It is not guaranteed that the maze is laid out so that it is actually possible to visit all numbers up to N following these rules.
An animated solution for seed 0 is available.
Implementation
Your solution should implement a single method getPath. It gives you the following information about the problem:
-
int[] numbers gives you the layout of the maze. numbers[R * S + C] gives you the contents of the tile in row R and column C: 0 denotes a hole, -1 denotes a wildcard, numbers 1 through N denote tiles with numbers on them. You can figure out S as a square root of the size of this array, and N as the maximal number in this array.
-
ints playerRow and playerCol give you the row and column coordinates of the cell on which you start (row and column indexes are 0-based). You are guaranteed that this cell is not a hole, not a wildcard tile and not a tile with a "1" on it.
-
double power gives you a number between 0.0 and 2.0 which is used to calculate the final score (see "Scoring" section for details).
The return from this method will describe the path you want to take through the maze. i-th character of your return is the instruction for your i-th step:
-
'U' to decrement row coordinate (if the row coordinate is 0, it becomes S-1 due to wrap around; other coordinates behave similarly),
-
'D' to increment row coordinate,
-
'L' to decrement column coordinate,
-
'R' to increment column coordinate,
-
any other character is ignored, and you stay in place.
You will also stay in place if following the instruction would take you to a hole.
You can use at most 4 * N * S steps in your path.
Scoring
The raw score for a test case is calculated as follows. If your solution failed to produce valid return (crashed, timed out, or returned too many steps), the raw score for that test case will be -1. Otherwise, the score starts with 0. Each time you reach a goal tile with number X on it, the score is incremented by X * (sum of the numbers on all tiles destroyed between visiting tiles with numbers X-1 and X). Once the simulation is over, the score is multiplied by ((last number reached) / N)^power to produce your final raw score. Note that the tiles destroyed after you hit the last goal number you'll hit on your path don't affect your score.
The normalized score for each test case (except the failed ones) is YOUR/MAX, where MAX is the maximal score any competitor got on this test case (considering only the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases, multiplied by 1,000,000.
Tools
An offline tester is available here. Please refer to its source code for exact implementation of test case generation and simulation. |
| |
Definition |
| | | Class: | VanishingMaze | | Method: | getPath | | Parameters: | int[], int, int, double | | Returns: | String | | Method signature: | String getPath(int[] numbers, int playerRow, int playerCol, double power) | | (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. |
| |
Constraints |
| - | The size of the maze S will be chosen between 10 and 40, inclusive. |
| - | The maximal number in the maze N will be chosen between S and S*S/4, inclusive. |
| - | The number of holes in the maze will be chosen between 0 and (S*S-N)/5-1, inclusive. |
| - | The number of wildcards in the maze will be chosen between 0 and (S*S-N)/10-1, inclusive. |
| - | power will be chosen between 0.0 and 2.0. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
S = 10
N = 10
Number of holes = 16
Number of wildcards = 5
1 -1 10 8 3 8 0 7 0 6
10 8 0 9 4 3 8 6 9 9
2 10 6 7 0 9 10 4 4 10
2 3 7 6 10 2 10 2 3 6
0 10 6 8 6 10 6 9 0 2
0 1 9 9 5 2 1 0 0 2
10 0 10 1 7 0 5 3 1 -1
7 6 0 6 7 -1 9 2 0 7
2 1 10 3 7 9 10 0 2 7
-1 3 0 0 8 8 -1 7 9 1
Starting position = (5, 4)
(N_reached/N) power = 1.0358000035609753
" | |
|
| 1) | |
| | | Returns:
"seed = 2
S = 20
N = 46
Number of holes = 21
Number of wildcards = 30
29 43 2 28 5 5 17 5 36 13 38 38 41 11 43 -1 18 27 23 33
38 -1 -1 40 46 40 11 2 28 11 28 41 0 40 0 27 18 16 9 46
25 28 29 3 34 37 28 25 14 33 35 22 2 24 18 24 40 42 16 37
16 3 30 45 26 42 9 27 40 29 19 38 31 -1 0 32 14 32 43 23
12 0 17 10 29 -1 30 19 3 12 35 21 32 1 40 5 6 35 8 10
4 -1 5 -1 21 15 7 12 31 19 0 41 0 30 41 32 30 30 21 42
11 34 45 3 25 10 0 34 14 0 2 20 34 1 28 -1 41 7 13 8
-1 7 -1 42 34 3 26 24 0 33 21 8 -1 28 41 14 44 -1 13 35
46 23 26 20 20 41 -1 38 0 10 0 10 46 6 0 39 39 0 17 0
41 13 27 8 -1 7 10 16 20 23 1 31 -1 17 10 -1 8 18 -1 40
40 27 13 28 29 23 22 31 38 39 37 33 26 18 30 35 6 0 34 26
42 18 5 0 37 10 1 43 33 9 24 41 10 24 27 26 1 3 30 35
2 -1 17 23 9 19 0 22 36 45 44 29 17 27 7 25 42 9 0 29
2 11 40 12 45 19 35 33 -1 37 19 -1 15 19 37 26 4 38 13 11
15 31 15 42 5 -1 38 9 27 19 41 20 15 35 39 40 0 45 37 39
12 19 11 1 43 41 1 6 11 41 10 2 8 0 24 -1 4 40 0 21
28 17 7 38 6 16 -1 46 -1 45 1 -1 30 1 31 45 -1 29 46 2
10 36 21 38 25 19 19 14 24 2 16 10 1 4 26 16 33 15 36 17
18 17 10 -1 37 1 35 34 39 24 5 10 -1 35 4 38 44 -1 32 37
6 14 37 3 37 34 -1 9 8 44 26 18 26 2 4 1 14 30 11 27
Starting position = (10, 7)
(N_reached/N) power = 0.841405813260715
" | |
|
| 2) | |
| | | Returns:
"seed = 3
S = 40
N = 400
Number of holes = 212
Number of wildcards = 118
Starting position = (8, 21)
(N_reached/N) power = 1.1857291871831783
" | |
|
| 3) | |
| | | Returns:
"seed = 4
S = 29
N = 193
Number of holes = 88
Number of wildcards = 48
Starting position = (27, 0)
(N_reached/N) power = 1.7339253218996868
" | |
|
| 4) | |
| | | Returns:
"seed = 5
S = 12
N = 14
Number of holes = 13
Number of wildcards = 7
Starting position = (1, 4)
(N_reached/N) power = 1.2751332639898507
" | |
|
| 5) | |
| | | Returns:
"seed = 6
S = 27
N = 144
Number of holes = 29
Number of wildcards = 5
Starting position = (6, 23)
(N_reached/N) power = 0.5147963952705361
" | |
|
| 6) | |
| | | Returns:
"seed = 7
S = 13
N = 15
Number of holes = 21
Number of wildcards = 6
Starting position = (11, 1)
(N_reached/N) power = 0.10782186106024416
" | |
|
| 7) | |
| | | Returns:
"seed = 8
S = 31
N = 205
Number of holes = 108
Number of wildcards = 3
Starting position = (7, 19)
(N_reached/N) power = 1.1319264884042914
" | |
|
| 8) | |
| | | Returns:
"seed = 9
S = 27
N = 156
Number of holes = 27
Number of wildcards = 43
Starting position = (5, 14)
(N_reached/N) power = 1.469377068995855
" | |
|
| 9) | |
| | | Returns:
"seed = 10
S = 35
N = 121
Number of holes = 180
Number of wildcards = 71
Starting position = (22, 1)
(N_reached/N) power = 1.1086841728533303
" | |
|
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.
