Marathon Match 123

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

Jewels is a game where you must construct horizontal or vertical lines of the same type of jewel on a NxN grid. Each cell of the grid is one of C types of jewels. In each move you can swap any two jewels. Jewels are removed from the grid when they form a horizontal or vertical line of at least 3 matching jewels next to each other. Jewels above empty spaces fall down and can form more matching horizontal or vertical lines which will again be removed and the process repeats. Such an event is called a chain reaction. The more chain reactions you create, the more points you will score. Your task is to play the game for 1000 moves and remove as many jewels from the grid with as many chain reactions as you can.

Here is a partial animation of a solution for seed=1.

Input and Output

This is an interactive problem, so your code needs to interact with the tester for each move. Initially your code will receive as input the following values, each on a separate line:

• N, the size of the grid.
• C, the number of jewel types.
• N*N lines describing the grid in row-major order. Each line containing the 1-based jewel type. The first row is at the bottom and the last row at the top.

The following game loop repeats until the game terminates after 1000 moves:

• Your solution sends moves by writing a line to output. Your move should be formatted as "R1 C1 R2 C2" (without the quotes), which means that you want to swap the jewels at locations (R1,C1) and (R2,C2). These coordinates are 0-based. You cannot swap a cell with itself. Row 0 is at the bottom and Row N-1 at the top. Column 0 is on the left.
• The tester will then:
  • 1. Swap the two jewels.
  • 2. Set the number of chain reactions and move score to 0.
  • 3. Mark all the jewels that form part of a horizontal or vertical line with length greater than two. Increment your move score according to each line found (Scoring explained in the scoring section).
  • 4. Remove all the marked jewels.
  • 5. Let all the jewels fall down until no jewel can fall further. New jewels will also enter from the top.
  • 6. Increment the number of chain reactions if any jewels were marked.
  • 7. Goto step 3 until no jewels were removed.
  • 8. Multiply your move score by the number of chain reactions and add this to your total score.
• After each move you will receive an updated grid from the tester, with N*N lines describing the grid.
• On the next line the tester will provide you with "runtime" (without the quotes), where runtime is the total time spent in your solution in milliseconds.

Scoring

The raw score is the total score you achieved over all moves. The score of a single move is calculated by multiplying the sum of all line scores with the number of chain reactions for that move. If the length of a matching jewel line is L, then the line score will be (L-2)*(L-2). For example, 3 jewels in a row will score 1 point and 4 jewels will score 4 points.

If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

• Not formatting the moves correctly.
• Using coordinates that are out of bounds.
• Trying to swap a cell with itself.
• Not making exactly 1000 moves.

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 YOUR/MAX, where YOUR is your raw score and MAX is the largest 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 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 16, inclusive.
• The number of jewel types C is chosen between 5 and 10, inclusive.
• The jewel grid of 1000*N rows and N columns is randomly created. Your solution will only be able to see the lower N rows of the grid. A larger grid is created such that each test case has consistent new jewels falling in for each column.
• All values are chosen uniformly at random.

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