TCO21 Regional Marathon - Lightning Marathon Match 128

Key Information

Register
Submit
The challenge is finished.

Timezone:Etc/UTC

Registration

Starts

Jul 27, 2021

16:54

Ends

Aug 05, 2021

12:58

Submission

Starts

Aug 02, 2021

13:38

Ends

Aug 05, 2021

13:45

Review

Starts

Aug 05, 2021

13:48

Ends

Aug 07, 2021

13:48

Winners Announced

Aug 07, 2021

13:48

Challenge Overview

Welcome to the TCO21 Regionals Marathon Match! The match is currently open for pre-registration. The match is a pat of the TCO21 Regional Events.

Here are all the rules and prizes information on the regional event.

Marathon Match Schedule and Phases

The Match will be open for submission on August 2, 09:00 UTC-4 (Topcoder Time). Problem statements will be available when the submission phase opens.

  • Registration Phase: July 27, 09:30 UTC-4 - August 5, 09:00 UTC-4
  • Submission Phase: August 2, 09:35 UTC-4 - August 5, 09:35 UTC-4
  • Final Testing: August 5, 09:00 UTC-4 - August 8, 09:00 UTC-4
  • Results Announcement: August 8, 10:00 UTC-4

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 NxN grid filled with coloured balls. Each ball has one of C colours. Each move you can swap two orthogonally adjacent balls. Your task is to minimize the number of moves to obtain exactly C 4-connected components. In other words, each colour should form a single 4-connected component.

Here is an example solution for seed=1:

animation

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.
  • N*N lines representing the grid in row-major order. The colour of the ball in row r and column c will be on line r*N+c. This is a value between 0 and C-1, inclusive.

Your solution needs to produce the following output, each on a separate line:

  • K, the number of moves.
  • K lines representing the moves. Each move must be formatted as "r1 c1 r2 c2" (without the quotes), where (r1,c1) and (r2,c2) are the locations of the swapped balls.

Scoring

The raw score is the number of moves performed. If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

  • Not formatting the moves correctly or using indices that are out of bounds.
  • Trying to swap balls that are not orthogonally adjacent.
  • Performing more than 2*N*N*N moves.
  • Not obtaining a grid with C 4-connected components.
  • 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 4 and 30, inclusive.
  • The number of colours C is chosen between 3 and 8, inclusive.
  • The colour of each grid cell is chosen between 0 and C-1, inclusive.
  • The grid generating process is repeated until there are more than C 4-connected components and all C colours are used.
  • All values are chosen uniformly at random.

Notes

  • Two locations are orthogonally adjacent if they differ only by one row or by one column.
  • A 4-connected component is a set of balls of one colour, such that there is a path of orthogonally adjacent moves from any ball to any other ball in the set.
  • 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 50 full submission (provisional) test cases. There will be 1000 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 BallSwaps.<appropriate extension>

Sample Submissions

Here are example solutions for different languages, modified to be executed with the visualizer. Note that this solution does not produce a valid final answer. 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

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

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.
  • -manual. Play manually using the mouse. Left click to select a ball and left click again to choose its neighbour to swap them. Clicking the same ball again deselects it.
  • -delay <delay> Sets the delay (in milliseconds) between visualizing consecutive simulation steps, default is 500.
  • -N <N> Sets a custom grid size.
  • -C <C> Sets a custom number of colours.

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. You can also play the game manually using the -manual parameter.

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.