Marathon Match 118

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
• Sample Submissions / Tester / Source Files are now also available in the Download Section on the top right. This section will only be visible once you have registered for the match.
• Starting from this match, marathon local testers 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.

Overview

You and your friends decided to have some fun and went to a night club where there is a nice dance floor, made of color LED tiles. Each time a person steps on a dance floor tile, that tile changes its color. For the first song of the night, your group will try to make an impressive performance, following a pre-determined choreography and leaving in the end the dance floor as "pretty" as possible.

Details

The dance floor is a grid with N x N tiles. Each tile has a known circular sequence of distinct C colors. It returns to the first color of the sequence after C changes.

During the music each dancer needs to make exactly S steps. In each step, a dancer is allowed to move to one of the adjacent tiles (up, down, left or right) or stay on the same tile. If a dancer moves, the tile he/she moved to will change to its next color. Otherwise, if a dancer stays on the same tile, there will be no effect on the tile color. More than one dancer can be on the same tile at the same time. If more than one dancer move to the same tile at the same step, it will change colors multiple times, one for each dancer that landed on it.

Your group has D dancers in total, and each of them will need to follow his/her own choreography. The choreography is a sequence of (X,Y) positions in the dance floor that a particular dancer needs to be at step T. The first position of the choreography is the initial position of the dancer (T = 0) and the last position is exactly at the end of the music (T = S). There is always enough time to move from one position to the next one. In fact, sometimes there is some extra time between positions, so dancers can choose a different path and still follow their choreography. It is mandatory to follow the whole choreography, and failing to be at one of the choreography positions at the specified time makes the solution invalid.

As you and your friends are not only great dancers but also Topcoders, the dance floor final configuration is considered prettier when it has fewer 4-connected components of each color. 4-connected components are groups of tiles with the same color, which are connected to each other through 4-neighbor connectivity (vertically or horizontally adjacent tiles). Your goal is to minimize the score, which is the sum of the squared number of 4-connected components of each color. For example, if there are 3 colors (red, green and blue), and the final configuration of the dance floor has 1 red 4-connected component, 2 blue and 4 green, your raw score is 1^2 + 2^2 + 4^2 = 21.

Here is an example solution for seed = 7. The white arrows indicate the next choreography position for each dancer.

Input

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

• N, the size of the dance floor.
• C, the number of colors.
• D, the number of dancers.
• S, the number of steps (music duration).

The following N*N lines will have the color sequences for each dance floor tile, one tile in each line, in row-major order (first all tiles from the first row of the dance floor, then tiles from the second row, and so on):

• C characters corresponding to the permutation of colors for that dance floor tile. Colors are numbered from 0 to C - 1 and the initial tile's color is the first color of the sequence.

And finally 2*D lines will contain the choreography information. Two lines for each dancer:

• The number of positions P in his/her choreography.
• 3 * P space-separated numbers, containing coordinates and time of each choreography position: x1 y1 t1 x2 y2 t2 ... xP yP tP.

Output

Your code should write to output the following:

• On the first line, the number of steps S.
• S lines, each with D characters, representing the move for each dancer: 'U' for up (decreases Y coordinate), 'D' for down (increases Y coordinate), 'R' for right (increase X coordinate), 'L' for left (decreases X coordinate) and '-' for staying on the same position.

Scoring

After S steps, the dance floor's final configuration of colors is evaluated. For each color the number of 4-connected components is computed, and your raw score is the sum of squared number of components of each color. If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

• Not using exactly S moves for each dancer.
• Illegally formatted moves or moves that are out of bounds.
• Failing to follow the choreography, not being in the specified position at the specified time.

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 visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

• The size of the dance floor N is chosen between 8 and 50, inclusive.
• The number of colors C is chosen between 2 and 6, inclusive.
• The number of dancers D is chosen between 2 and 10, inclusive.
• The number of steps S is chosen between 50 and 1500, inclusive.
• A margin parameter M is chosen between 0 and 15, inclusive.
• For each tile, its sequence of colors, which is a random permutation of C colors.
• For each dancer, his/her choreography. Each position is chosen randomly. The first time is always zero. Other times are chosen between (tprev + distance) and (tprev + distance + M), inclusive, where tprev is the time of the previous position for that dancer, distance is the Manhattan distance between the current position and the previous one, and M is the margin parameter mentioned above. The last position is adjusted so it is exactly at the end of the music (S steps). Consecutive positions in a dancer's choreography are distinct.
• 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