Story

Takahashi is developing a device that automatically adjusts the brightness of stage lighting.

This device can control the path of incoming light by placing mirrors, splitters, and absorbing blocks on a grid. Mirrors change the direction of light, splitters split light into two directions, and absorbing blocks make light disappear.

You are given in advance the sequence of brightness values that will be needed. Operate the objects on the grid and emit light so as to realize a sequence of brightness values as close to the target as possible.

Problem Statement

There is an N \times N grid. Let (0, 0) denote the coordinates of the top-left cell, and let (i, j) denote the coordinates of the cell located i cells downward and j cells rightward from there.

At most one object can be placed in each cell. The objects that can be placed are as follows.

• A mirror / connecting the lower-left and upper-right corners
• A mirror \ connecting the upper-left and lower-right corners
• A splitter Z connecting the lower-left and upper-right corners
• A splitter N connecting the upper-left and lower-right corners
• An absorbing block #

For the splitters Z and N, the direction of the diagonal stroke in the character corresponds to the direction of the splitter. A cell with no object placed in it is called an empty cell.

You may set the initial board freely. Setting the initial board does not count toward the number of operation turns.

There is a light emitter on the upper edge of cell (0, N/2). From this emitter, you can emit a light ray of intensity 1 and clarity 60 downward.

The emitted light ray travels on the board while changing its direction, intensity, and clarity as described below.

Empty cell: If a light ray enters an empty cell, it continues straight.

Absorbing block: If a light ray enters an absorbing block, that ray disappears.

Mirror: If a light ray enters a mirror, it is reflected and changes direction by 90 degrees. The direction of reflection is determined by the direction of the light ray immediately before entering the mirror and the orientation of the mirror, as shown in the following table.

Splitter: If a light ray enters a splitter and its clarity is positive, it splits into two rays: one that continues straight, and one that proceeds in the same direction as it would if it were reflected by a mirror with the same orientation as the splitter. Each of the two resulting rays has half the intensity of the incoming ray, and its clarity is smaller by 1 than that of the incoming ray.

On the other hand, if a light ray with clarity 0 enters another splitter, the light is scattered and causes an unintended effect on the device's output. The scattered ray is no longer tracked and is not added to the output value. For one emission, the sum of the intensities of all scattered rays is called the scattering value.

Output: If a light ray exits the grid, that ray is regarded as having been output. It may exit from any side of the grid. For one emission, the sum of the intensities of all light rays that exit the grid is called the output value.

Example

Solid lines represent mirrors, dashed lines represent splitters, and black cells represent absorbing blocks. Of the light emitted from the top, half is directly output outside the grid, and the remaining half enters the loop in the lower right. Of the light that enters the loop, half is absorbed, 1/4 is output outside the grid, and the remaining 1/4 enters the loop again. By repeating this process, the final output value becomes \frac{2}{3} - \frac{1}{3}\cdot 2^{-59}, and the scattering value becomes 2^{-60}.

After setting the initial board, you may perform the following operations for at most T turns.

• Place an object in an empty cell.
• Remove an object placed in a cell.
• Rotate one mirror or splitter. This swaps / with \, and swaps N with Z.
• Emit light.

You are given a target sequence of light intensities A_0, A_1, \ldots, A_{L-1}. You must perform the light emission operation exactly L times.

Let B_k be the output value obtained by the k-th light emission, and let R_k be the scattering value. Your goal is to make the error between A and B, as well as the total scattering value, as small as possible.

Supplement on the Output Value and Scattering Value

For boards containing loops formed by splitters, light rays may branch and circulate indefinitely. Even in such cases, it is possible to define the output value exactly by solving a system of linear equations. However, computations using real numbers may cause the score to change due to numerical errors.

Therefore, in this problem, each light ray has a clarity value, and the number of times it can pass through splitters is limited to at most 60. If a light ray with clarity 0 enters another splitter, that ray is scattered and is no longer tracked. Thus, the process for a single emission always terminates after a finite number of steps.

Also, for computation purposes, if we regard the incoming light as having intensity 2^{60}, then each pass through a splitter only halves the intensity, so all light-ray intensities can be handled as integers. The actual output value and scattering value are obtained by dividing the resulting integer values by 2^{60}, respectively.

from collections import defaultdict

# Directions: 0=up, 1=right, 2=down, 3=left
DI = [-1, 0, 1, 0]
DJ = [0, 1, 0, -1]

INITIAL_CLARITY = 60
UNIT = 1 << INITIAL_CLARITY


def reflect_dir(ch, d):
    if ch in ("/", "Z"):
        return [1, 0, 3, 2][d]
    if ch in ("\\", "N"):
        return [3, 2, 1, 0][d]
    raise ValueError("not a mirror or splitter")


def calc_B_R(board):
    """
    Returns (B, R) when light is emitted once on the current board.

    B is the output value, and R is the scattering value.
    Both are returned as integer values in units of 1 / 2^60.
    """
    n = len(board)
    memo = {}

    def advance(i, j, d):
        """
        Follow empty cells and mirrors until reaching outside the grid,
        an absorbing block, or a splitter.
        """
        path = []

        while True:
            key = (i, j, d)
            if key in memo:
                res = memo[key]
                break

            path.append(key)

            ch = board[i][j]

            if ch == "#":
                res = ("absorb", None)
                break

            if ch in ("Z", "N"):
                res = ("split", (i, j, d))
                break

            if ch == ".":
                nd = d
            elif ch in ("/", "\\"):
                nd = reflect_dir(ch, d)
            else:
                raise ValueError("invalid board character")

            ni = i + DI[nd]
            nj = j + DJ[nd]

            if not (0 <= ni < n and 0 <= nj < n):
                res = ("out", None)
                break

            i, j, d = ni, nj, nd

        for key in path:
            memo[key] = res

        return res

    cur = defaultdict(int)
    cur[(0, n // 2, 2)] = UNIT

    B = 0
    R = 0

    for clarity in range(INITIAL_CLARITY, -1, -1):
        nxt = defaultdict(int)

        for (i, j, d), amount in cur.items():
            kind, arg = advance(i, j, d)

            if kind == "out":
                B += amount

            elif kind == "absorb":
                pass

            elif kind == "split":
                if clarity == 0:
                    R += amount
                    continue

                si, sj, sd = arg
                half = amount // 2

                for nd in (sd, reflect_dir(board[si][sj], sd)):
                    ni = si + DI[nd]
                    nj = sj + DJ[nd]

                    if not (0 <= ni < n and 0 <= nj < n):
                        B += half
                    else:
                        nxt[(ni, nj, nd)] += half

        cur = nxt

    return B, R

Scoring

Let B_k be the output value obtained by the k-th light emission, and let R_k be its scattering value. Define the error E as follows.

\[ E = \sum_{k=0}^{L-1} \left(|A_k - B_k| + R_k\right) \]

Then, you obtain the following absolute score.

\[ 1 + \mathrm{round}(10^9 \times E) \]

The lower the absolute score, the better.

For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.

The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.

The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

Number of test cases

• Provisional test: 50
• System test: 2000. We will publish seeds.txt (sha256=09a07ffd9ee0e93469394a2cb36a22a9b4be312865de69d90d27198173124f04) after the contest is over.

About relative evaluation system

In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.

The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.