- Submission-Review You can find your submissions artifacts here. Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores.
- Other Details For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution.
OverviewYou want to create a maze to test the navigating ability of robot vacuum cleaners. The maze is to be designed on an NxN grid floor, whose cells are either empty ('.') or contain a wall ('#'). There are R robots and each robot must visit T target locations. In particular, each robot r begins in location Starts[r] and must visit every location given in Targets[r]. The robots do not need to return to their starting location at the end of their journey. The robots can only move through adjacent (horizontally or vertically) empty cells. The robots can see the entire maze and will choose the shortest path that visits all their target locations. Some paths of the robot may overlap and these are all counted towards the total distance. Your goal is to make the maze as hard as possible, ie., to maximize the total distance travelled by all the robots.
For example, here is a solution for seed=1. There are 2 robots (crosses) and each must visit 2 target locations (circles). The shortest path for each robot is shown with a different colour. Note that some paths may overlap - this is ok as robots do not interfere with each other.
InputYour code will receive as input the following values, each on a separate line:
- N, the size of the grid.
- R, the number of robots.
- T, the number of targets for each robot.
OutputYour code should write to output the following:
- On the first line, the number of cells in the maze, ie., N*N.
- N*N lines, each representing a single cell of the maze in row-major order. The cells must be either empty ('.') or a wall ('#').
ScoringThe scorer will compute the length of the shortest path required for each robot to visit its targets. The raw score will be the sum of all these lengths.
If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:
- Not outputing exactly N*N cells.
- Using characters other than '.' and '#'.
- Having any unreachable targets or starting locations blocked by walls.
Test Case GenerationPlease look at the generate() method in visualizer's source code for the exact details about test case generation. Each test case is generated as follows:
- The size of the grid N is chosen between 10 and 40, inclusive.
- The number of robots R is chosen between 1 and 6, inclusive.
- The number of targets per robot T is chosen between 2 and 6, inclusive.
- Starts and Targets are chosen to be distinct locations on the grid.
- All values are chosen uniformly at random.
- The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
- The compilation time limit is 30 seconds.
- There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
- The match is rated.
C#, Java, C++ and Python
Your submission must be a single ZIP file not larger than 500 MB, with your source code only.
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.
- Java Source Code - HardestMaze.java
- C++ Source Code - HardestMaze.cpp
- Python3.6 Source Code - HardestMaze.py
- C# Source Code - HardestMaze.cs
SAMPLE SUBMISSIONSHere are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions.
ToolsAn offline tester is available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.
OFFLINE TESTER / VISUALIZERIn order to use the offline tester/visualizer tool for testing your solution locally, you'll have to include in your solution the main method that interacts with the tester/visualizer via reading data from standard input and writing data to standard output.
To run the tester with your solution, you should run:
java -jar HardestMaze.jar -exec "<command>" -seed <seed>
Here, <command> is the command to execute your program, and <seed> is seed for test case generation.
If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\HardestMaze.exe" or "~/topcoder/HardestMaze".
In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder HardestMaze".
Additionally, you can use the following options:
- -seed <seed> Sets the seed used for test case generation, default is seed 1.
- -novis Turn off visualization.
- -debug Print debug information.
- -size <cell size> Use custom cell size, default is 30 pixels. If size is set to 0 then it will fit the visualizer window into the screen area.
- -N <N> Sets a custom grid size.
- -R <R> Sets a custom number of robots.
- -T <T> Sets a custom number of targets.
Custom parameters also accept ranges. For example -N 20,30 makes the grid size to be randomly chosen between 20 and 30 inclusive. Finally, you can print any debug information of your solution to standard error, and it will be forwarded to the standard out of the tester.
Marathon local testers also have other options, including running a range of seeds with a single command, running more than one seed at time (multiple threads), controlling time limit, saving input/output/error and loading solution from a file. The usage of these other options are described here.