Marathon Match 80 - Marathon Match 80

Problem Statement

IMPORTANT: This problem is used for two simultaneous matches: TCO'13 Marathon Round 2 and Marathon Match 80. You can compete in TCO'13 R2 only if you are eligible for TCO'13 and haven't advanced from TCO'13 R1. You can compete in MM 80 if you are not eligible for TCO'13, have advanced from TCO'13 R1 or just would like to skip TCO'13 R2 by some reason. Competing in both matches is not allowed. Doing so will lead to disqualification. Note that registration does not count as competing. In order to be considered a competitor, you need to make at least one submit (example or full).

There is a square board separated into NxN square cells. Initially each cell contains a single mirror which is a segment that connects its two opposite corners. If a mirror connects top right and bottom left corners, it is denoted with letter 'L'. If it connects top left and bottom right corners, then it is denoted with 'R'.

The original state of the board will be given to you as a String[] board. Each element contains N characters and represents a single row. The characters are mirrors in that row listed left to right. The rows are given in the top to bottom order. Consider an example:

Such board would be represented as {"LLLR", "RLRR", "LLLL", "RRRL"}.

By some reason you are not comfortable with all those mirrors and you want to destroy them. You've got a laser which can be used to cast rays. A ray is cast from outside of the board perpendicular to one of its side and so that it intersects (enters) this side exactly at the middle of some cell. The ray moves straight until it hits a mirror. Then it is reflected by physics laws and the mirror is instantly destroyed (even before the ray is able to exit the given cell). The process continues in this fashion and ends when the ray exits the board. Here is an example:

Let's number the rows (top to bottom) and columns (left to right) with numbers 0 to N-1. Let's also assume there are imaginary rows -1 (above row 0) and N (below row N-1), as well as columns -1 (to the left of column 0) and N (to the right of column N-1). Then the ray follows the following rote in (row, column) coordinates: (4, 2) - (3, 2) - (3, 1) - (2, 1) - (2, 2) - (1, 2) - (1, 1) - (4, 1). Note that when the ray reaches cell (1, 1), the mirrors at (2, 1) and (3, 1) are already destroyed, so the ray will just exit the board after getting reflected at (1, 1).

Since your goal is to destroy all mirrors, you will continue casting rays until all of them are destroyed. For example, you can cast a second ray as follows:

After that all mirrors are destroyed, so you're done.

The task is to achieve the goal using as small number of rays as possible. Your score will be equal to N/R (exact division), where R is the number of rays you used. Your overall score is the sum of scores on all test cases.

You will need to implement the method destroy. It takes board as the input in the format described above. The return value needs to be an int[] containing 2*R elements. The elements 2*i and 2*i+1 must represent the row and the column of the starting cell of the i-th ray. We assume that each ray starts in some imaginary row or column as in pictures above. Note that the order of elements in return value is important. For the example above, the return value would be {4, 2, -1, 1}.

The return value is allowed to contain at most 2*N*N elements, otherwise your score for the test case will be 0. It will also be 0 in case of other failures such as exceeding time or memory limit, returning result in invalid format or not being able to destroy all mirrors.

Test cases are generated as follows. N is selected uniformly, at random, between 50 and 100. Then each of the N*N cells is independently generated as 'L' with 50% probability and as 'R' otherwise.

An offline tester/visualizer is available.

Definition

Notes

Examples