Marathon Match 158

Marathon MatchData Science
Register
Submit a solution
The challenge is finished.
DetailsRegistrants48

Challenge Overview

Important Links

  • 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.

Overview

You are given an N*N grid, where each cell is either a wall or a token from one of C colours. Each turn you can select a pair of orthogonally adjacent tokens and change them to a specific colour provided by the colourMap. The colourMap F maps a pair of colours (c1, c2) to a new colour c3. The colourMap has the following properties:

  • Symmetric: F(c1, c2) = F(c2, c1).
  • Identity mapping: F(c, c) = c.
  • If c1!=c2 then c3 will be different from c1 and c2.

Your task is to change every token in the grid to a single colour in the fewest number of turns. It is guaranteed that this is always possible. In particular, you need to minimise the score given by (T + N*A), where T is the number of turns taken and A is the number of tokens in the final grid that do not have the majority colour.

Here is an example solution for seed=1. Walls are shown in gray.

seed1.gif

Input and Output

Your code will receive as input the following values, each on a separate line:

  • N, the grid size.
  • C, the number of colours.
  • C*C lines representing the colourMap in row-major order. Entry in row i and column j represents F(i, j). It is guaranteed that F(i, j) respects the properties described above.
  • N*N lines representing the starting grid in row-major order. Each cell is either a wall (-1) or a token colour between 0 and C-1, inclusive.

You must output a sequence of moves, formatted as follows:

  • M, number of moves.
  • M lines representing the moves, each formatted as "r1 c1 r2 c2" (without the quotes), indicating that you want to select the adjacent tokens located at (r1, c1) and (r2, c2). All locations are 0-based.

Scoring

The raw score is the total points obtained from your sequence of moves. If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

  • Using fewer than 0 moves or more than N*N*N moves.
  • Using an invalid move format.
  • Trying to select walls or using locations outside the grid.
  • Not selecting orthogonally adjacent locations.
  • Exceeding the time limit.

If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is MIN/YOUR, where YOUR is your raw score and MIN is the smallest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalized to 100.

Test Case Generation

Please look at the generate() method in the visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

  • The grid size N is chosen between 8 and 30, inclusive.
  • The number of colours C is chosen between 3 and 7, inclusive.
  • The wall probability P is chosen between 0 and 0.2, inclusive.
  • Generate the colourMap. Set F(c, c) to c. For F(c1, c2) select a random colour c3, such that it is different from c1 and c2. Make the map symmetric, so that F(c1, c2) = F(c2, c1). The generation process is repeated until every colour c3 can be produced from some pair (c1, c2).
  • Generate the starting grid. Paint the grid with a random target colour. With probability P change each cell to a wall. This process is repeated until all the tokens form a single connected component. Now perform moves in reverse. For 100 iterations, go through all pairs of adjacent tokens in a random order and if they have the same colour c3 then change them to colours c1 and c2, where F(c1, c2) = c3. If there are multiple such pairs (c1, c2) then select a random pair.
  • All values are chosen uniformly at random.

Notes

  • Two locations (r1, c1) and (r2, c2) are orthgonally adjacent if |r1-r2| + |c1-c2| = 1.
  • 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.

Languages Supported

C#, Java, C++ and Python

Submission Format

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.

Make sure you name your Source Code file as Kaleidoscope*.<appropriate extension>*

Sample Submissions

Here are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions:

Tools

An 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.

Downloads

Offline Tester / Visualizer

Your solution should interact with the tester/visualizer by reading data from standard input and writing data to standard output.

To run the tester with your solution, you should run:

java -jar tester.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\Kaleidoscope.exe" or "~/topcoder/Kaleidoscope".
In case your compiled solution is to be run with the help of an interpreter, for example, if your program is in Java, the command will be something like "java -cp C:\TopCoder Kaleidoscope".

Additionally you can use the following options:

  • -seed <seed> Sets the seed used for test case generation, default is seed 1.
  • -debug. Print debug information.
  • -novis. Turns off visualisation.
  • -pause. Starts the visualizer in paused mode. See more information below.
  • -delay <delay> Sets the delay (in milliseconds) between visualizing consecutive simulation steps, default is 10.
  • -noanimate. Only show the final state, no intermediate steps.
  • -manual. Play the game manually. Use the left mouse click to select cells and the right mouse click to undo moves.
  • -showMajority. Highlights the tokens that have the majority colour.
  • -N <N> Sets a custom grid size.
  • -C <C> Sets a custom number of colours.
  • -P <P> Sets a custom wall probability.
  • -finalColour <F> Sets a custom final colour.

The visualizer works in two modes. In regular mode, steps are visualized one after another with a delay specified with the -delay parameter. In paused mode, the next move will be visualized only when you press any key. The space key can be used to switch between regular and paused modes. The default starting mode is regular. You can use the -pause parameter to start in paused mode.

Marathon local testers have many useful 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 options are described here.

ID: 30375819