Test MM 2 - Test MM 2

Problem Statement

DISCLAIMER:

• This is a test match. It means things can go wrong. We will surely try to fix everything as soon as possible, but please be aware that issues are possible. If you noticed an issue, please report it to us (contest@topcoder.com).
• Testing of solutions is performed on VMs. It means that there exists certain variability between how much time the same algorithm can take to execute. We've done some tests and most of the time everything is fairly stable, but rarely we were seeing ~5% or even ~10% runtime differences. In theory, larger differences are also possible, we can't provide any guarantees here. If you notice that the same code runs with more than 10% different runtimes, we would be very interested to hear such information -- please email it to contest@topcoder.com.

There is a square board separated into NxN square cells. Rows of the board are numbered 0 to N-1 (top to bottom). Columns are numbered 0 to N-1 (left to right). Originally all cells of the board are empty.

You are given a String S that contains N*N characters. You need to place its characters (in the same order as they go within the string) to board's cells according to the following rules:

• The first character can be placed into any cell.
• Each next character can be placed into any empty cell that is adjacent (by side) to the cell where the previous character was placed.

In other words, you need to place the given string into the board so that it forms a Hamiltonian path.

Once all characters are placed, we will calculate C -- the number of connected components on the board. A connected component is a maximal (by inclusion) set of cells such that there exists a path between any two cells of this set. A path between X and Y is a sequence of cells that starts at X and ends at Y such that all cells (including X and Y) contain the same character and each two consecutive cells are adjacent (by side).

Your goal in this task is to minimize the value of C.

You will need to implement the method placeString. Its input is the string S. The return value must be an int[] containing N*N + 1 elements. First two elements are the row and the column where you place the first character. Each of the next N*N - 1 elements should be the direction (relative to the current cell) where you place the next character. 0 means right, 1 means up, 2 means left and 3 means down.

For each test case we will calculate your raw and normalized scores. If we were unable to receive solution from you (due to time limit, memory limit, crash, invalid return value, etc.), then both your raw and normalized scores are 0. Otherwise, the raw score will be equal to the value of C in your solution. The normalized score for each test is 1,000,000.0 * BEST / YOUR, where BEST is the lowest positive score currently obtained on this test case (i.e., considering the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases.

Test cases are generated as follows. N is selected uniformly, at random, between 30 and 100. A parameter A (alphabet size) is chosen uniformly, at random, between 3 and 5. Each character in S is selected uniformly and independently, at random, as one of first A letters of English alphabet. Only lowercase letters are used.

An offline tester/visualizer is available.

Definition

Notes

Examples