Problem Statement |
| | The City covers the surface of a torus-shaped planet. It has only two types of buildings: black and white. All buildings of the same color are identical. The buildings are arranged in a square grid of SxS square blocks, each block contains exactly one building, and there are streets between each pair of horizontally or vertically adjacent blocks.
You find yourself at one of the crossroads of the city. You don't know which crossroads it is. Fortunately, you have a map of the City, and you can walk around looking at the buildings. Unfortunately, the map you have is outdated; some of the buildings in the city have been painted a different color since it was printed, so the City you see differs from the map.
Your task is to figure out at which crossroads you started.
Implementation Details
Your code must implement one method whereAmI(String[] map, int W, int L, int G). This method will be called once; it will give you the (outdated) map of the City as a String[], with black and white buildings denoted as 'X' and '.', respectively, and constants used in scoring (see Scoring section). The return value of this method is an integer, and it will be ignored during scoring. From this method you can call the following library functions of class Actions:
-
look() allows you to look around you when you're standing at a crossroads. You'll see four buildings immediately adjacent to this crossroads, which will be returned to you as a String[] with 2 rows and 2 columns. The orientation of this piece is the same as of the big map you're given initially. This method returns you the actual colors of the buildings, which might not match their colors on the map you're given!
-
walk(int[] shift) allows you to walk to a different crossroads. shift is a int[] with exactly two elements, shift[0] and shift[1] are distances you want to walk along vertical and horizontal axis, respectively. Both elements of shift must be between -S+1 and S-1, inclusive (remember that the map wraps around both horizontally and vertically). This method will return -1 if the call was invalid (provided invalid parameters or involved too much walking) and 0 in normal case.
-
guess(int[] coord) allows you to make a guess about the coordinates of the crossroads at which you've started your journey on the map. coord is a int[] with exactly two elements, coord[0] and coord[1] are coordinates of your guess along vertical and horizontal axis, respectively. Both elements of coord must be between 0 and S-1, inclusive. This method returns 1 if your guess is correct, 0 if it's incorrest, or -1 if the call was invalid (coordinates out of range or too many guesses).
A crossroads with coordinates (R, C) is located in the top left corner of the building in row R and column C. Thus, crossroads with coordinates (0, 0) is the top left corner of the map.
Your solution is allowed to make at most S^2 calls to each of look() and guess() functions, and to walk a Manhattan distance of at most 16*S^2 blocks in walk() functions.
Scoring
For each test case we will calculate your raw and normalized scores.
If your solution failed to figure out your starting position on the map (timed out, didn't make a correct guess, did too many library function calls etc.), raw score for this test case will be -1. Otherwise, raw score will be the total cost of your journey: W * (total Manhattan distance walked) + L * (number of look() calls) + G * (number of incorrect guesses done).
The normalized score for each test (except those that failed and scored a -1) is 1,000,000.0 * BEST / YOUR, where BEST is the lowest raw score currently obtained 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.
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. That page also contains links to useful information.
|
| |
Definition |
| | | Class: | WanderingTheCity | | Method: | whereAmI | | Parameters: | String[], int, int, int | | Returns: | int | | Method signature: | int whereAmI(String[] map, int W, int L, int G) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Note that the map you've been given in whereAmI method differs from the map you're observing with look calls! |
| - | 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. |
| - | The match is rated. |
| |
Constraints |
| - | The size of the map S will be between 50 and 500, inclusive. |
| - | W will be between 1 and 10, inclusive. |
| - | L will be between 0.5S and S, inclusive. |
| - | G will be between 0.5S2 and S2, inclusive. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
S = 20
X.X.X.X.X.X.X.X.X.X.
....................
....................
XX.XXX.XXX.XXX.XXX.X
X.X.X.X.X.X.X.X.X.X.
....................
....................
XX.XXX.XXX.XXX.XXX.X
X.X.X.X.X.X.X.X.X.X.
....................
.................X..
XX.XXX.XXX.XXX.XXX.X
X.X.X.X.X.X.X.X.X.X.
....................
....................
XX.XXX.XXX.XXX.XXX.X
X.X.X.X.X.X.X.X.X.X.
..........X.........
....................
XX.XXX.XXX.XXX.XXX.X
Cost of walking W = 9
Cost of look() L = 19
Cost of guess() G = 258
" | |
|
| 1) | |
| | | Returns:
"seed = 2
S = 40
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X.........X....X....X
...............X........................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
..........................X.............
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
..............................X.........
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
....X....X....X....X....X....X....X....X
........................................
Cost of walking W = 5
Cost of look() L = 25
Cost of guess() G = 1019
" | |
|
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |
| 6) | |
| | |
| 7) | |
| | |
| 8) | |
| | |
| 9) | |
| | |
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.