May 2020

May 28, 2020

TopCoder MM118 : DanceFloor

Approach 焼きなまし法を使いました。

評価：問題のスコア*10000 + (10000 - 面積最大の色の面積)

問題のスコアを使った場合より、約1%良くなった。(5/29 追記)

近傍：ランダムに経路（進む方向の列）を選んで、2点swap, 1点insert, 複数shuffle, 余分な経路の削除、追加、変更

いろいろ試したけど狭い範囲の方が良くて、連続する2点のswapを多く使った。
4方向見て、同じ色が3方向以上ある場合は、色を変化させないようにすると、約10%良くなった(provisional 40点にちょっと届かないくらい、10倍高速化しても50点)。(5/30 追記)

高速化：焼きなましで受理しないときに、「4-Conected Component の状態を巻き戻す」で3倍くらい

前計算系の高速化も試していたけど間に合わなかった。

Example scores:
1) 5.0
2) 19552.0
3) 432.0
4) 11922.0
5) 4.0
6) 34.0
7) 3.0
8) 28.0
9) 50.0
10) 450.0

感想

私が見た一番小さいスコアは２だったけど、上位は１とか出しているんだろうか？

スコア１を確認できた。(5/29 追記)

焼きなまし法がうまくいく問題で、焼きなまし法を使って負けるパターンは、

焼きなまし法よりいい方法があった

TSP：3opt + kick, Guided Local Search
Vertex Coloring：Tabu Search
Graph Golf：GA
...

いい評価関数があった

GraphReconstruction
...

いい近傍があった

CrystalLighting
...

高速化で負けた
その他

だと思うけど、今回はどれだろうか？高速化で負けていると思うけど、大差なのでその他もありえそう。

評価関数だった(5/30 追記)

Source Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class DanceFloor {
    private final int N;
    private final int numColors;
    private final int numDancers;
    private final int numSteps;
    private final int[][][] rxcxorderToColors;
    private final int[][] dancerXpointToStep;

    private static final int[] dr = { -1, 0, 0, 1, 0, };
    private static final int[] dc = { 0, -1, 1, 0, 0, };
    private final int[][] rxcToCount;
    private final int[][] dancerXstepToRxc;
    private final int[][] dancerXstepToRxc0;
    private final int[][] bestDancerXstepToRxc;

    static final XorShift rng = new XorShift(System.nanoTime());
    static final Watch watch = new Watch();
    private SAState sa = new SAState();
    private double score;
    private double bestScore = 1e18;

    private FourConnectedComponent[] colorToComponents;

    private InitializedIntArray diffCounts;
    private IntSetUseInitializedIntArray changedRNcs;

    public DanceFloor(int N, int C, int D, int S, String[][] tileColors, int[][] marks) {
        this.N = N;
        this.numColors = C;
        this.numDancers = D;
        this.numSteps = S;
        this.rxcxorderToColors = new int[N][N][numColors];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                for (int i = 0; i < numColors; i++) {
                    this.rxcxorderToColors[r][c][i] = tileColors[r][c].charAt(i) - '0';
                }
            }
        }
        dancerXstepToRxc = new int[numDancers][numSteps + 1];
        dancerXstepToRxc0 = new int[numDancers][numSteps + 1];
        bestDancerXstepToRxc = new int[numDancers][numSteps + 1];
        rxcToCount = new int[N][N];
        this.dancerXpointToStep = new int[numDancers][];
        for (int dancer = 0; dancer < numDancers; dancer++) {
            int numPoints = marks[dancer].length / 3;
            dancerXpointToStep[dancer] = new int[numPoints];
            for (int point = 0; point < numPoints; point++) {
                int c = marks[dancer][3 * point + 0];
                int r = marks[dancer][3 * point + 1];
                int step = marks[dancer][3 * point + 2];
                dancerXpointToStep[dancer][point] = step;
                dancerXstepToRxc[dancer][step] = (r << 8) | (c);
                dancerXstepToRxc0[dancer][step] = (r << 8) | (c);
            }
        }
        colorToComponents = new FourConnectedComponent[numColors];
        for (int color = 0; color < numColors; color++) {
            colorToComponents[color] = new FourConnectedComponent(N);
        }

        diffCounts = new InitializedIntArray(0, N * N);
        changedRNcs = new IntSetUseInitializedIntArray(N * N);

        Utils.debug("size", N, "Color", C, "Dancer", D, "Step", S, "tileColors.length", tileColors.length, "marks.length", marks.length);
    }

    public String[] run() {
        solve();
        return makeSolution();
    }

    private void solve() {
        greedy();
        sa.startTemperature = score * 0.001;
        SA();
    }

    private void greedy() {
        for (int dancer = 0; dancer < numDancers; dancer++) {
            int numPoints = dancerXpointToStep[dancer].length;
            for (int point = 1; point < numPoints; point++) {
                int startStep = dancerXpointToStep[dancer][point - 1];
                int startRxc = dancerXstepToRxc[dancer][startStep];
                int startR = r(startRxc);
                int startC = c(startRxc);

                int endStep = dancerXpointToStep[dancer][point];
                int endRxc = dancerXstepToRxc[dancer][endStep];
                int endR = r(endRxc);
                int endC = c(endRxc);

                int r = startR;
                int c = startC;
                int step = startStep + 1;
                int numFreeSteps = (endStep - startStep) - (Math.abs(startR - endR) + Math.abs(startC - endC));
                for (; step <= startStep + numFreeSteps / 2; step++) {
                    if (Math.abs(startR - endR) < Math.abs(startC - endC)) {
                        if (startR < endR) {
                            if (r - 1 >= 0) {
                                r--;
                            } else {
                                break;
                            }
                        } else {
                            if (r + 1 < N) {
                                r++;
                            } else {
                                break;
                            }
                        }
                    } else {
                        if (startC < endC) {
                            if (c - 1 >= 0) {
                                c--;
                            } else {
                                break;
                            }
                        } else {
                            if (c + 1 < N) {
                                c++;
                            } else {
                                break;
                            }
                        }
                    }
                    dancerXstepToRxc[dancer][step] = rxc(r, c);
                    rxcToCount[r][c]++;
                }
                for (; step <= endStep; step++) {
                    boolean change = true;
                    if (distance(startR, endC, N / 2, N / 2) < distance(endR, startC, N / 2, N / 2)) {
                        if (r < endR) {
                            r++;
                        } else if (r > endR) {
                            r--;
                        } else if (c < endC) {
                            c++;
                        } else if (c > endC) {
                            c--;
                        } else {
                            if (step + 1 <= endStep) {
                                if (Math.abs(startR - endR) < Math.abs(startC - endC)) {
                                    if (endR > 0) {
                                        r--;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        r++;
                                    } else {
                                        r++;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        r--;
                                    }
                                } else {
                                    if (endC > 0) {
                                        c--;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        c++;
                                    } else {
                                        c++;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        c--;
                                    }
                                }
                            } else {
                                change = false;
                            }
                        }
                    } else {
                        if (c < endC) {
                            c++;
                        } else if (c > endC) {
                            c--;
                        } else if (r < endR) {
                            r++;
                        } else if (r > endR) {
                            r--;
                        } else {
                            if (step + 1 <= endStep) {
                                if (Math.abs(startR - endR) < Math.abs(startC - endC)) {
                                    if (endR > 0) {
                                        r--;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        r++;
                                    } else {
                                        r++;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        r--;
                                    }
                                } else {
                                    if (endC > 0) {
                                        c--;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        c++;
                                    } else {
                                        c++;
                                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                                        rxcToCount[r][c]++;
                                        step++;
                                        c--;
                                    }
                                }
                            } else {
                                change = false;
                            }
                        }
                    }
                    dancerXstepToRxc[dancer][step] = rxc(r, c);
                    if (change) {
                        rxcToCount[r][c]++;
                    }
                }
            }
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                colorToComponents[getColor(r, c)].add(r, c);
            }
        }

        score = calculateScore2();
        Utils.debug("greedy", "score", score, "time", watch.getSecondString());
    }

    private int distance(int r, int c, int r2, int c2) {
        return Math.abs(r - r2) + Math.abs(c - c2);
    }

    private double calculateScore2() {
        double score = 0;
        int maxArea = 0;
        for (int color = 0; color < numColors; color++) {
            int count = colorToComponents[color].numComponents();
            int area = colorToComponents[color].area();
            score += count * count;
            maxArea = Math.max(maxArea, area);
        }
        return score * 10000 + 10000 - maxArea;
    }

    private void SA() {
        double second = (int) watch.getSecond();
        sa.init();
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 8) - 1)) == 0) {
                sa.update();

                if (sa.isTLE()) {
                    loadBest();
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%4.0f", score), String.format("%4.0f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());
                    break;
                }

                if (watch.getSecond() > second) {
                    second++;
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%4.0f", score), String.format("%4.0f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());
                }
            }

            mutate();
        }
        Utils.debug("SA", "score", score, "time", watch.getSecondString());
    }

    private void mutate() {
        double random = 104 * rng.nextDouble();
        if (random < 1) {
            changePathShuffle();
        } else if (random < 2) {
            changePathInsert();
        } else if (random < 3) {
            changePathStopOrMove();
        } else if (random < 4) {
            changePathSwap();
        } else if (random < 104) {
            changePathSmall();
        }
    }

    private void changePathSmall() {
        int dancer = (int) (numDancers * rng.nextDouble());
        int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());

        int startStep = dancerXpointToStep[dancer][point];
        int endStep = dancerXpointToStep[dancer][point + 1];
        int numSteps2 = endStep - startStep;
        if (numSteps2 <= 1) {
            return;
        }

        int step = startStep + (int) ((numSteps2 - 1) * rng.nextDouble());
        int rxc0 = dancerXstepToRxc[dancer][step];
        int r0 = r(rxc0);
        int c0 = c(rxc0);

        assert step + 2 <= endStep;
        int rxc2 = dancerXstepToRxc[dancer][step + 2];
        int r2 = r(rxc2);
        int c2 = c(rxc2);
        int rxc1 = dancerXstepToRxc[dancer][step + 1];
        int r1 = r(rxc1);
        int c1 = c(rxc1);

        int direction1 = getDirection(r0, c0, r1, c1);
        int direction2 = getDirection(r1, c1, r2, c2);
        if (direction1 == direction2) {
            return;
        }

        int r4 = r0 + dr[direction2];
        int c4 = c0 + dc[direction2];
        if (!isValid(r4, 0, N) || !isValid(c4, 0, N)) {
            return;
        }
        if (direction1 == 4 || direction2 == 4) {
            sa.accept(0);
            dancerXstepToRxc[dancer][step + 1] = rxc(r4, c4);
            dancerXstepToRxc[dancer][step + 2] = rxc(r4 + dr[direction1], c4 + dc[direction1]);
        } else {

            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].save();
            }

            colorToComponents[getColor(r1, c1)].remove(r1, c1);
            rxcToCount[r1][c1]--;
            colorToComponents[getColor(r1, c1)].add(r1, c1);

            dancerXstepToRxc[dancer][step + 1] = rxc(r4, c4);

            colorToComponents[getColor(r4, c4)].remove(r4, c4);
            rxcToCount[r4][c4]++;
            colorToComponents[getColor(r4, c4)].add(r4, c4);

            double deltaScore = calculateScore2() - score;

            if (sa.accept(deltaScore)) {
                score += deltaScore;
                saveBest();
            } else {
                rxcToCount[r1][c1]++;
                dancerXstepToRxc[dancer][step + 1] = rxc(r1, c1);
                rxcToCount[r4][c4]--;
                for (int color = 0; color < numColors; color++) {
                    colorToComponents[color].load();
                }
            }
        }
    }

    private void changePathSmall0() {
        int dancer = (int) (numDancers * rng.nextDouble());
        int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());

        int startStep = dancerXpointToStep[dancer][point];
        int startRxc = dancerXstepToRxc[dancer][startStep];
        int startR = r(startRxc);
        int startC = c(startRxc);

        int endStep = dancerXpointToStep[dancer][point + 1];
        int numSteps2 = endStep - startStep;
        if (numSteps2 <= 1) {
            return;
        }

        int[] directions = new int[numSteps2];
        for (int step = startStep + 1; step <= endStep; step++) {
            int rxc0 = dancerXstepToRxc[dancer][step - 1];
            int r0 = r(rxc0);
            int c0 = c(rxc0);

            int rxc = dancerXstepToRxc[dancer][step];
            int r = r(rxc);
            int c = c(rxc);

            int direction = getDirection(r0, c0, r, c);

            directions[step - (startStep + 1)] = direction;
        }

        int index = (int) ((numSteps2 - 1) * rng.nextDouble());
        if (directions[index] == directions[index + 1]) {
            return;
        }

        {
            int swap = directions[index];
            directions[index] = directions[index + 1];
            directions[index + 1] = swap;
        }

        for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            r += dr[d];
            c += dc[d];
            if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                return;
            }
        }

        for (int color = 0; color < numColors; color++) {
            colorToComponents[color].save();
        }

        changedRNcs.clear();
        diffCounts.clear();
        for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            if (d < 4) {
                r += dr[d];
                c += dc[d];
                int rNc = r * N + c;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, 1 + diffCounts.get(rNc));
            }

            int rxc2 = dancerXstepToRxc[dancer][step];
            int r2 = r(rxc2);
            int c2 = c(rxc2);
            if (getDirection(r1, c1, r2, c2) < 4) {
                int rNc = r2 * N + c2;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                r1 = r2;
                c1 = c2;
            }
        }

        for (int i = 0; i < changedRNcs.size(); i++) {
            int rNc = changedRNcs.get(i);
            int diffCount = diffCounts.get(rNc);
            if (diffCount == 0) {
                continue;
            }
            int r = rNc / N;
            int c = rNc % N;
            colorToComponents[getColor(r, c)].remove(r, c);
            rxcToCount[r][c] += diffCount;
            colorToComponents[getColor(r, c)].add(r, c);
        }

        double deltaScore = calculateScore2() - score;

        if (sa.accept(deltaScore)) {
            score += deltaScore;

            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                dancerXstepToRxc[dancer][step] = rxc(r, c);
            }
        } else {
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                rxcToCount[r][c] -= diffCount;
            }

            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].load();
            }
        }
    }

    private void changePathShuffle() {
        int dancer = (int) (numDancers * rng.nextDouble());
        int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());

        int startStep = dancerXpointToStep[dancer][point];
        int startRxc = dancerXstepToRxc[dancer][startStep];
        int startR = r(startRxc);
        int startC = c(startRxc);

        int endStep = dancerXpointToStep[dancer][point + 1];
        int numSteps2 = endStep - startStep;
        if (numSteps2 <= 1) {
            return;
        }

        int[] directions = new int[numSteps2];
        for (int step = startStep + 1; step <= endStep; step++) {
            int rxc0 = dancerXstepToRxc[dancer][step - 1];
            int r0 = r(rxc0);
            int c0 = c(rxc0);

            int rxc = dancerXstepToRxc[dancer][step];
            int r = r(rxc);
            int c = c(rxc);

            int direction = getDirection(r0, c0, r, c);

            directions[step - (startStep + 1)] = direction;
        }

        int from = (int) ((numSteps2 - 0) * rng.nextDouble());
        int to = (int) ((numSteps2 - 1) * rng.nextDouble());
        if (to >= from) {
            to++;
        }
        if (from > to) {
            int swap = from;
            from = to;
            to = swap;
        }

        shuffle(directions, from, to);

        for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            r += dr[d];
            c += dc[d];
            if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                return;
            }
        }

        for (int color = 0; color < numColors; color++) {
            colorToComponents[color].save();
        }

        changedRNcs.clear();
        diffCounts.clear();
        for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            if (d < 4) {
                r += dr[d];
                c += dc[d];
                int rNc = r * N + c;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, 1 + diffCounts.get(rNc));
            }

            int rxc2 = dancerXstepToRxc[dancer][step];
            int r2 = r(rxc2);
            int c2 = c(rxc2);
            if (getDirection(r1, c1, r2, c2) < 4) {
                int rNc = r2 * N + c2;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                r1 = r2;
                c1 = c2;
            }
        }

        for (int i = 0; i < changedRNcs.size(); i++) {
            int rNc = changedRNcs.get(i);
            int diffCount = diffCounts.get(rNc);
            if (diffCount == 0) {
                continue;
            }
            int r = rNc / N;
            int c = rNc % N;
            colorToComponents[getColor(r, c)].remove(r, c);
            rxcToCount[r][c] += diffCount;
            colorToComponents[getColor(r, c)].add(r, c);
        }

        double deltaScore = calculateScore2() - score;

        if (sa.accept(deltaScore)) {
            score += deltaScore;

            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                dancerXstepToRxc[dancer][step] = rxc(r, c);
            }

            saveBest();
        } else {
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                rxcToCount[r][c] -= diffCount;
            }

            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].load();
            }
        }
    }

    private void changePathInsert() {
        int dancer = (int) (numDancers * rng.nextDouble());
        int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());

        int startStep = dancerXpointToStep[dancer][point];
        int startRxc = dancerXstepToRxc[dancer][startStep];
        int startR = r(startRxc);
        int startC = c(startRxc);

        int endStep = dancerXpointToStep[dancer][point + 1];
        int numSteps2 = endStep - startStep;
        if (numSteps2 <= 1) {
            return;
        }

        int[] directions = new int[numSteps2];
        for (int step = startStep + 1; step <= endStep; step++) {
            int rxc0 = dancerXstepToRxc[dancer][step - 1];
            int r0 = r(rxc0);
            int c0 = c(rxc0);

            int rxc = dancerXstepToRxc[dancer][step];
            int r = r(rxc);
            int c = c(rxc);

            int direction = getDirection(r0, c0, r, c);

            directions[step - (startStep + 1)] = direction;
        }

        int from = (int) ((numSteps2 - 0) * rng.nextDouble());
        int to = (int) ((numSteps2 - 1) * rng.nextDouble());
        if (to >= from) {
            to++;
        }
        if (from < to) {
            int direction = directions[from];
            for (int i = from; i < to; i++) {
                directions[i] = directions[i + 1];
            }
            directions[to] = direction;
        } else {
            int direction = directions[from];
            for (int i = from - 1; i >= to; i--) {
                directions[i + 1] = directions[i];
            }
            directions[to] = direction;
        }

        for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            r += dr[d];
            c += dc[d];
            if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                return;
            }
        }

        for (int color = 0; color < numColors; color++) {
            colorToComponents[color].save();
        }

        changedRNcs.clear();
        diffCounts.clear();
        for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            if (d < 4) {
                r += dr[d];
                c += dc[d];
                int rNc = r * N + c;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, 1 + diffCounts.get(rNc));
            }

            int rxc2 = dancerXstepToRxc[dancer][step];
            int r2 = r(rxc2);
            int c2 = c(rxc2);
            if (getDirection(r1, c1, r2, c2) < 4) {
                int rNc = r2 * N + c2;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                r1 = r2;
                c1 = c2;
            }
        }

        for (int i = 0; i < changedRNcs.size(); i++) {
            int rNc = changedRNcs.get(i);
            int diffCount = diffCounts.get(rNc);
            if (diffCount == 0) {
                continue;
            }
            int r = rNc / N;
            int c = rNc % N;
            colorToComponents[getColor(r, c)].remove(r, c);
            rxcToCount[r][c] += diffCount;
            colorToComponents[getColor(r, c)].add(r, c);
        }

        double deltaScore = calculateScore2() - score;

        if (sa.accept(deltaScore)) {
            score += deltaScore;
            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                dancerXstepToRxc[dancer][step] = rxc(r, c);
            }
            saveBest();
        } else {
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                rxcToCount[r][c] -= diffCount;
            }

            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].load();
            }
        }
    }

    private void changePathSwap() {
        int dancer = (int) (numDancers * rng.nextDouble());
        int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());

        int startStep = dancerXpointToStep[dancer][point];
        int startRxc = dancerXstepToRxc[dancer][startStep];
        int startR = r(startRxc);
        int startC = c(startRxc);

        int endStep = dancerXpointToStep[dancer][point + 1];
        int numSteps2 = endStep - startStep;
        if (numSteps2 <= 1) {
            return;
        }

        int[] directions = new int[numSteps2];
        for (int step = startStep + 1; step <= endStep; step++) {
            int rxc0 = dancerXstepToRxc[dancer][step - 1];
            int r0 = r(rxc0);
            int c0 = c(rxc0);

            int rxc = dancerXstepToRxc[dancer][step];
            int r = r(rxc);
            int c = c(rxc);

            int direction = getDirection(r0, c0, r, c);

            directions[step - (startStep + 1)] = direction;
        }

        int index = (int) ((numSteps2 - 0) * rng.nextDouble());
        while (directions[index] == 4) {
            index = (int) ((numSteps2 - 0) * rng.nextDouble());
        }
        int index2 = -1;
        for (int i = index + 1; i < directions.length; i++) {
            if (directions[i] != 4 && directions[i] != directions[index]) {
                index2 = i;
                break;
            }
        }
        if (index2 == -1) {
            return;
        }

        {
            int swap = directions[index];
            directions[index] = directions[index2];
            directions[index2] = swap;
        }

        for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            r += dr[d];
            c += dc[d];
            if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                return;
            }
        }

        for (int color = 0; color < numColors; color++) {
            colorToComponents[color].save();
        }

        changedRNcs.clear();
        diffCounts.clear();
        for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            if (d < 4) {
                r += dr[d];
                c += dc[d];
                int rNc = r * N + c;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, 1 + diffCounts.get(rNc));
            }

            int rxc2 = dancerXstepToRxc[dancer][step];
            int r2 = r(rxc2);
            int c2 = c(rxc2);
            if (getDirection(r1, c1, r2, c2) < 4) {
                int rNc = r2 * N + c2;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                r1 = r2;
                c1 = c2;
            }
        }

        for (int i = 0; i < changedRNcs.size(); i++) {
            int rNc = changedRNcs.get(i);
            int diffCount = diffCounts.get(rNc);
            if (diffCount == 0) {
                continue;
            }
            int r = rNc / N;
            int c = rNc % N;
            colorToComponents[getColor(r, c)].remove(r, c);
            rxcToCount[r][c] += diffCount;
            colorToComponents[getColor(r, c)].add(r, c);
        }

        double deltaScore = calculateScore2() - score;

        if (sa.accept(deltaScore)) {
            score += deltaScore;
            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                dancerXstepToRxc[dancer][step] = rxc(r, c);
            }
            saveBest();
        } else {
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                rxcToCount[r][c] -= diffCount;
            }

            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].load();
            }
        }
    }

    private void changePathStopOrMove() {
        int dancer = (int) (numDancers * rng.nextDouble());
        int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());

        int startStep = dancerXpointToStep[dancer][point];
        int startRxc = dancerXstepToRxc[dancer][startStep];
        int startR = r(startRxc);
        int startC = c(startRxc);

        int endStep = dancerXpointToStep[dancer][point + 1];
        int endRxc = dancerXstepToRxc[dancer][endStep];
        int endR = r(endRxc);
        int endC = c(endRxc);

        int numSteps2 = endStep - startStep;
        if (numSteps2 <= 1) {
            return;
        }

        int dr1 = endR - startR;
        int dc1 = endC - startC;
        int dr2 = Math.abs(dr1);
        int dc2 = Math.abs(dc1);
        int shortestPath = dr2 + dc2;
        if (numSteps2 - shortestPath <= 1) {
            return;
        }
        int[] directions = new int[numSteps2];
        int[] counts = new int[5];
        IntList[] indexes = new IntList[5];
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = new IntList(numSteps2);
        }
        if (dr1 > 0) {
            counts[3] -= dr2;
        } else if (dr1 < 0) {
            counts[0] -= dr2;
        }
        if (dc1 > 0) {
            counts[2] -= dc2;
        } else if (dc1 < 0) {
            counts[1] -= dc2;
        }
        for (int step = startStep + 1; step <= endStep; step++) {
            int rxc0 = dancerXstepToRxc[dancer][step - 1];
            int r0 = r(rxc0);
            int c0 = c(rxc0);

            int rxc = dancerXstepToRxc[dancer][step];
            int r = r(rxc);
            int c = c(rxc);

            int direction = getDirection(r0, c0, r, c);

            directions[step - (startStep + 1)] = direction;
            counts[direction]++;
            indexes[direction].add(step - (startStep + 1));
        }
        int index = (int) (counts.length * rng.nextDouble());
        while ((index < 4 && counts[index] <= 0) || (index == 4 && counts[index] <= 1)) {
            index = (int) (counts.length * rng.nextDouble());
        }

        if (index == 4) {
            assert indexes[4].size() >= 2;
            int index2 = (int) ((indexes[4].size() - 1) * rng.nextDouble());
            int i2 = indexes[4].get(index2);
            int i3 = indexes[4].get(index2 + 1);

            assert directions[i2] == 4;
            assert directions[i3] == 4;
            double random = rng.nextDouble();
            if (random < 0.25) {
                directions[i2] = 1;
                directions[i3] = 2;
            } else if (random < 0.5) {
                directions[i2] = 2;
                directions[i3] = 1;
            } else if (random < 0.75) {
                directions[i2] = 0;
                directions[i3] = 3;
            } else {
                directions[i2] = 3;
                directions[i3] = 0;
            }
        } else if (index == 0 || index == 3) {
            assert indexes[0].size() >= 1;
            assert indexes[3].size() >= 1;
            int i2 = indexes[0].get((int) (indexes[0].size() * rng.nextDouble()));
            int i3 = -1;
            {
                int min = (int) 1e9;
                for (int i = 0; i < indexes[3].size(); i++) {
                    int abs = Math.abs(indexes[3].get(i) - i2);
                    if (abs < min) {
                        min = abs;
                        i3 = indexes[3].get(i);
                    } else {
                        break;
                    }
                }
            }

            assert directions[i2] == 0;
            assert directions[i3] == 3;
            double random = rng.nextDouble();
            if (random < 0.333) {
                directions[i2] = 4;
                directions[i3] = 4;
            } else if (random < 0.666) {
                directions[i2] = 1;
                directions[i3] = 2;
            } else {
                directions[i2] = 2;
                directions[i3] = 1;
            }

        } else {
            assert indexes[1].size() >= 1;
            assert indexes[2].size() >= 1;
            int i2 = indexes[1].get((int) (indexes[1].size() * rng.nextDouble()));
            int i3 = -1;
            {
                int min = (int) 1e9;
                for (int i = 0; i < indexes[2].size(); i++) {
                    int abs = Math.abs(indexes[2].get(i) - i2);
                    if (abs < min) {
                        min = abs;
                        i3 = indexes[2].get(i);
                    } else {
                        break;
                    }
                }
            }

            assert directions[i2] == 1;
            assert directions[i3] == 2;
            double random = rng.nextDouble();
            if (random < 0.333) {
                directions[i2] = 4;
                directions[i3] = 4;
            } else if (random < 0.666) {
                directions[i2] = 0;
                directions[i3] = 3;
            } else {
                directions[i2] = 3;
                directions[i3] = 0;
            }
        }
        for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            r += dr[d];
            c += dc[d];
            if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                return;
            }
        }

        for (int color = 0; color < numColors; color++) {
            colorToComponents[color].save();
        }

        changedRNcs.clear();
        diffCounts.clear();
        for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
            int d = directions[step - (startStep + 1)];
            if (d < 4) {
                r += dr[d];
                c += dc[d];
                int rNc = r * N + c;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, 1 + diffCounts.get(rNc));
            }

            int rxc2 = dancerXstepToRxc[dancer][step];
            int r2 = r(rxc2);
            int c2 = c(rxc2);
            if (getDirection(r1, c1, r2, c2) < 4) {
                int rNc = r2 * N + c2;
                changedRNcs.add(rNc);
                diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                r1 = r2;
                c1 = c2;
            }
        }

        for (int i = 0; i < changedRNcs.size(); i++) {
            int rNc = changedRNcs.get(i);
            int diffCount = diffCounts.get(rNc);
            if (diffCount == 0) {
                continue;
            }
            int r = rNc / N;
            int c = rNc % N;
            colorToComponents[getColor(r, c)].remove(r, c);
            rxcToCount[r][c] += diffCount;
            colorToComponents[getColor(r, c)].add(r, c);
        }

        double deltaScore = calculateScore2() - score;

        if (sa.accept(deltaScore)) {
            score += deltaScore;

            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                dancerXstepToRxc[dancer][step] = rxc(r, c);
            }
            saveBest();
        } else {
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                rxcToCount[r][c] -= diffCount;
            }

            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].load();
            }
        }
    }

    private void saveBest() {
        if (score < bestScore) {
            bestScore = score;
            for (int dancer = 0; dancer < numDancers; dancer++) {
                for (int step = 0; step < numSteps; step++) {
                    bestDancerXstepToRxc[dancer][step] = dancerXstepToRxc[dancer][step];
                }
            }
        }
    }

    private void loadBest() {
        score = bestScore;
        for (int dancer = 0; dancer < numDancers; dancer++) {
            for (int step = 0; step < numSteps; step++) {
                dancerXstepToRxc[dancer][step] = bestDancerXstepToRxc[dancer][step];
            }
        }
    }

    private String[] makeSolution() {
        StringBuilder[] sbs = new StringBuilder[numSteps];
        for (int step = 0; step < numSteps; step++) {
            sbs[step] = new StringBuilder();
        }
        for (int dancer = 0; dancer < numDancers; dancer++) {
            for (int step = 0; step < numSteps; step++) {
                int rxc = dancerXstepToRxc[dancer][step];
                int r = r(rxc);
                int c = c(rxc);

                int rxc1 = dancerXstepToRxc[dancer][step + 1];
                int r1 = r(rxc1);
                int c1 = c(rxc1);

                if (c1 > c) {
                    sbs[step].append('R');
                } else if (c1 < c) {
                    sbs[step].append('L');
                } else if (r1 > r) {
                    sbs[step].append('D');
                } else if (r1 < r) {
                    sbs[step].append('U');
                } else {
                    sbs[step].append('-');
                }

            }
        }
        String[] ret = new String[numSteps];
        for (int step = 0; step < numSteps; step++) {
            ret[step] = sbs[step].toString();
        }
        return ret;
    }

    private int getColor(int r, int c) {
        return rxcxorderToColors[r][c][rxcToCount[r][c] % numColors];
    }

    private boolean isValid(int v, int min, int minUpper) {
        return v >= min && v < minUpper;
    }

    private int rxc(int r, int c) {
        return (r << 8) | c;
    }

    private static final int r(int v) {
        return (v >>> 8) & 255;
    }

    private static final int c(int v) {
        return v & 255;
    }

    private int getDirection(int fromR, int fromC, int toR, int toC) {
        if (toR < fromR) {
            return 0;
        }
        if (toR > fromR) {
            return 3;
        }
        if (toC < fromC) {
            return 1;
        }
        if (toC > fromC) {
            return 2;
        }
        return 4;
    }

    private void shuffle(int[] a) {
        for (int i = a.length - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            swap(a, i, j);
        }
    }

    private void shuffle(int[] a, int l, int r) {
        for (int i = r; i >= l; i--) {
            int j = l + (int) ((i + 1 - l) * rng.nextDouble());
            swap(a, i, j);
        }
    }

    private void swap(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            int N = Integer.parseInt(br.readLine());
            int C = Integer.parseInt(br.readLine());
            int D = Integer.parseInt(br.readLine());
            int S = Integer.parseInt(br.readLine());

            String[][] tileColors = new String[N][N];
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    tileColors[y][x] = br.readLine();
                }
            }

            int[][] marks = new int[D][];
            for (int i = 0; i < D; i++) {
                int numMarks = Integer.parseInt(br.readLine());
                marks[i] = new int[3 * numMarks];
                String[] s = br.readLine().split(" ");
                for (int j = 0; j < 3 * numMarks; j++) {
                    marks[i][j] = Integer.parseInt(s[j]);
                }
            }

            String[] ret = new DanceFloor(N, C, D, S, tileColors, marks).run();

            System.out.println(ret.length);
            for (int i = 0; i < ret.length; i++) {
                System.out.println(ret[i]);
            }
            System.out.flush();

        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class InitializedIntArray {
    private int[] values;
    private int initialValue;
    private int[] versions;
    private int latestVersion;

    public InitializedIntArray(int initial_value, int size) {
        init(initial_value, size);
    }

    public void init(int initial_value, int size) {
        this.initialValue = initial_value;
        values = new int[size];
        versions = new int[size];
        latestVersion = 1;
    }

    void clear() {
        latestVersion++;
    }

    public int get(int index) {
        assert (index < values.length);
        if (versions[index] != latestVersion) {
            versions[index] = latestVersion;
            values[index] = initialValue;
        }
        return values[index];
    }

    public void set(int index, int value) {
        assert (index < values.length);
        versions[index] = latestVersion;
        values[index] = value;
    }
}

class SAState {

    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 9.5;
    public double time = startTime;
    public double startTemperature = 100;
    public double endTemperature = 1e-9;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 700;
    public double endRange = 1;
    public double range = startRange;

    public int numIterations;
    public int validIterations;
    public int acceptIterations;

    private static final double[] log = new double[32768];
    static {
        for (int i = 0; i < log.length; i++) {
            log[i] = Math.log((i + 0.5) / log.length);
        }
    }

    public void init() {
        numIterations = 0;
        validIterations = 0;
        acceptIterations = 0;

        startTime = useTime ? DanceFloor.watch.getSecond() : numIterations;

        update();
        lastAcceptTemperature = inverseTemperature;
    }

    public void update() {
        updateTime();
        updateTemperature();
    }

    public void updateTemperature() {
        double time0to1 = elapsedPercentage(startTime, endTime, time);
        double startY = startTemperature;
        double endY = endTemperature;
        double temperature = interpolate(startY, endY, time0to1);
        inverseTemperature = 1.0 / temperature;
    }

    private double elapsedPercentage(double min, double max, double v) {
        return (v - min) / (max - min);
    }

    private double interpolate(double v0, double v1, double d0to1) {
        return v0 + (v1 - v0) * d0to1;
    }

    public void updateRange() {
        range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

    public void updateTime() {
        time = useTime ? DanceFloor.watch.getSecond() : numIterations;
    }

    public boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double deltaScore) {
        return acceptS(deltaScore);
    }

    public boolean acceptB(double deltaScore) {
        validIterations++;

        if (deltaScore > -1e-9) {
            acceptIterations++;
            return true;
        }

        assert deltaScore < 0 : Utils.toString(deltaScore);
        assert 1.0 / inverseTemperature >= 0;

        double d = deltaScore * inverseTemperature;
        if (d < -10) {
            return false;
        }
        if (log[DanceFloor.rng.nextInt() & 32767] < d) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

    public boolean acceptS(double deltaScore) {
        validIterations++;

        if (deltaScore < 1e-9) {
            acceptIterations++;
            return true;
        }

        assert deltaScore > 0;
        assert 1.0 / inverseTemperature >= 0;

        double d = -deltaScore * inverseTemperature;
        if (d < -10) {
            return false;
        }
        if (log[DanceFloor.rng.nextInt() & 32767] < d) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

}

class FourConnectedComponent {
    private static final int EMPTY = -1;
    private static final int[] dr = { -1, 0, 0, 1, };
    private static final int[] dc = { 0, -1, 1, 0, };

    private int[][] board;
    private int numComponents;
    private int N;
    private int id0 = 1;

    private int area;

    public FourConnectedComponent(int N) {
        this.N = N;
        board = new int[N][N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                board[r][c] = EMPTY;
            }
        }
    }

    public int area() {
        return area;
    }

    private IntSet2 ids = new IntSet2();

    public void add(int r, int c) {
        assert board[r][c] == EMPTY;

        ids.clear();
        for (int d = 0; d < dr.length; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                continue;
            }
            int id = board[nr][nc];
            if (id != EMPTY) {
                ids.add(id);
            }
        }

        if (ids.size() == 0) {
            changes.add((r << 8) | c);
            changes.add(board[r][c]);
            board[r][c] = id0++;
            numComponents++;
        } else if (ids.size() == 1) {
            changes.add((r << 8) | c);
            changes.add(board[r][c]);
            int id = ids.get(0);
            board[r][c] = id;
        } else if (ids.size() >= 2) {
            int id = ids.get(0);
            dfsAdd(r, c, id);
            numComponents -= ids.size() - 1;
        }

        area++;
    }

    private void dfsAdd(int r, int c, int id) {
        changes.add((r << 8) | c);
        changes.add(board[r][c]);
        board[r][c] = id;
        for (int d = 0; d < dr.length; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                continue;
            }
            if (board[nr][nc] == EMPTY) {
                continue;
            }
            if (board[nr][nc] == id) {
                continue;
            }
            dfsAdd(nr, nc, id);
        }
    }

    private boolean isValid(int v, int min, int minUpper) {
        return v >= min && v < minUpper;
    }

    public void remove(int r, int c) {
        int id = board[r][c];
        assert id != EMPTY;
        changes.add((r << 8) | c);
        changes.add(id);
        board[r][c] = EMPTY;

        IntSet2 rxcs = ids;
        rxcs.clear();
        for (int d = 0; d < dr.length; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                continue;
            }
            if (board[nr][nc] == EMPTY) {
                continue;
            }
            int nid = board[nr][nc];
            if (nid == id) {
                rxcs.add(nr * N + nc);
            }
        }

        if (rxcs.size() == 0) {
            numComponents--;
        } else if (rxcs.size() == 1) {
        } else if (rxcs.size() >= 2) {
            int count = 0;
            for (; rxcs.size() > 0; count++) {
                int rxc = rxcs.get(0);
                int r2 = rxc / N;
                int c2 = rxc % N;
                dfsRemove(r2, c2, id0++, rxcs);
            }
            numComponents += count - 1;
        }

        area--;
    }

    private void dfsRemove(int r, int c, int id, IntSet2 rxcs) {
        rxcs.removeValue(r * N + c);
        changes.add((r << 8) | c);
        changes.add(board[r][c]);
        board[r][c] = id;
        for (int d = 0; d < dr.length; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                continue;
            }
            if (board[nr][nc] == EMPTY) {
                continue;
            }
            if (board[nr][nc] == id) {
                continue;
            }
            dfsRemove(nr, nc, id, rxcs);
        }
    }

    public int numComponents() {
        return numComponents;
    }

    private IntList changes = new IntList(1 << 20);
    private int numComponents0;
    private int area0;

    public void save() {
        changes.clear();
        numComponents0 = numComponents;
        area0 = area;
    }

    public void load() {
        numComponents = numComponents0;
        area = area0;
        for (int i = changes.size() - 1; i >= 0; i -= 2) {
            int v = changes.get(i - 1);
            int r = r(v);
            int c = c(v);
            int value = changes.get(i);
            board[r][c] = value;
        }
    }

    private int r(int v) {
        return (v >>> 8) & 255;
    }

    private int c(int v) {
        return v & 255;
    }
}

class IntList {
    private static final int EMPTY = -1;
    private int[] values;
    private int size;

    public IntList(int capacity) {
        values = new int[capacity];
        clear();
    }

    public void clear() {
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

    public boolean add(int value) {
        values[size++] = value;
        return true;
    }

    public boolean removeValue(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public int remove(int index) {
        int value = values[index];
        for (int i = index; i + 1 < size; i++) {
            values[i] = values[i + 1];
        }
        size--;
        return value;
    }

    public int removeFast(int index) {
        int value = values[index];
        values[index] = values[size - 1];
        size--;
        return value;
    }

    public int get(int index) {
        return values[index];
    }

    public int set(int index, int value) {
        int oldValue = values[index];
        values[index] = value;
        return oldValue;
    }

    public void add(int index, int value) {
        assert index <= size;
        for (int i = size - 1; i >= index; i--) {
            values[i + 1] = values[i];
        }
        size++;
        values[index] = value;
    }

    public int indexOf(int value) {
        for (int i = 0; i < size; i++) {
            if (values[i] == value) {
                return i;
            }
        }
        return EMPTY;
    }

    public int lastIndexOf(int value) {
        for (int i = size - 1; i >= 0; i--) {
            if (values[i] == value) {
                return i;
            }
        }
        return EMPTY;
    }

}

class IntSet2 {
    private static final int EMPTY = -1;
    private ArrayList indexToValue;
    private HashMap valueToIndex;

    public IntSet2() {
        indexToValue = new ArrayList<>();
        valueToIndex = new HashMap<>();
    }

    public boolean add(Integer value) {
        if (valueToIndex.get(value) != null) {
            return false;
        }
        Integer size = Integer.valueOf(indexToValue.size());
        indexToValue.add(value);
        if (valueToIndex.containsKey(value)) {
            valueToIndex.replace(value, size);
        } else {
            valueToIndex.put(value, size);
        }
        return true;
    }

    public boolean remove(int index) {
        if (size() == 0) {
            return false;
        }
        assert index < size();
        swap(index, size() - 1);
        Integer remove = indexToValue.remove(size() - 1);
        valueToIndex.remove(remove);
        return true;
    }

    public boolean removeValue(Integer value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public int get(int index) {
        assert index < size();
        return indexToValue.get(index).intValue();
    }

    public int indexOf(Integer value) {
        Integer e = valueToIndex.get(value);
        return e == null ? EMPTY : e.intValue();
    }

    public int size() {
        return indexToValue.size();
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        for (; size() > 0;) {
            remove(0);
        }
    }

    public boolean contains(Integer value) {
        return indexOf(value) != EMPTY;
    }

    public void swap(int index, int index2) {
        assert index < size();
        assert index2 < size();

        {
            Integer swap = indexToValue.get(index);
            indexToValue.set(index, indexToValue.get(index2));
            indexToValue.set(index2, swap);
        }
        if (valueToIndex.containsKey(indexToValue.get(index))) {
            valueToIndex.replace(indexToValue.get(index), index);
        } else {
            valueToIndex.put(indexToValue.get(index), index);
        }
        if (valueToIndex.containsKey(indexToValue.get(index2))) {
            valueToIndex.replace(indexToValue.get(index2), index2);
        } else {
            valueToIndex.put(indexToValue.get(index2), index2);
        }

    }

}

final class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

}

class Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

class XorShift {
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

    public XorShift(long l) {
        x = (int) l;
    }

    public int nextInt() {
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

}

class IntSetUseInitializedIntArray {
    private static final int EMPTY = -1;
    private int size;
    private InitializedIntArray indexToValue;
    private InitializedIntArray valueToIndex;

    public IntSetUseInitializedIntArray(int capacity) {
        this.size = 0;
        indexToValue = new InitializedIntArray(0, capacity);
        valueToIndex = new InitializedIntArray(EMPTY, capacity);
    }

    public boolean add(int value) {
        if (valueToIndex.get(value) != EMPTY) {
            return false;
        }
        indexToValue.set(size, value);
        valueToIndex.set(indexToValue.get(size), size);
        size++;
        return true;
    }

    public boolean remove(int index) {
        if (size == 0) {
            return false;
        }
        assert index < size;
        swap(index, size - 1);
        valueToIndex.set(indexToValue.get(size - 1), EMPTY);

        size--;
        return true;
    }

    public boolean removeValue(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        remove(index);
        return true;
    }

    public void swap(int index, int index2) {
        assert index < size;
        assert index2 < size;

        int swap = indexToValue.get(index);
        indexToValue.set(index, indexToValue.get(index2));
        indexToValue.set(index2, swap);

        valueToIndex.set(indexToValue.get(index), index);
        valueToIndex.set(indexToValue.get(index2), index2);

    }

    public void swapValue(int value, int value2) {
        assert value < size;
        assert value2 < size;

        int swap = valueToIndex.get(value);
        valueToIndex.set(value, valueToIndex.get(value2));
        valueToIndex.set(value2, swap);

        indexToValue.set(valueToIndex.get(value), value);
        indexToValue.set(valueToIndex.get(value2), value2);

    }

    public int get(int index) {
        assert index < size;
        return indexToValue.get(index);
    }

    public int indexOf(int value) {
        return valueToIndex.get(value);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        indexToValue.clear();
        valueToIndex.clear();
        size = 0;
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

    @Override
    public String toString() {
        int[] copy = new int[size()];
        for (int i = 0; i < copy.length; i++) {
            copy[i] = indexToValue.get(i);
        }
        return Arrays.toString(copy);
    }
}

May 01, 2020

TopCoder MM117 : RotatingNumbers

Example scores:
0) 12.0
1) 14673.0
2) 727.0
3) 27.0
4) 4162.0
5) 465.0
6) 7921.0
7) 6024.0
8) 49.0
9) 2874.0

Approach

N<=10 : ビームサーチを1回使いました。
10<N<=40 : 深さ20のビームサーチを9秒間使い続けた解と、すべての数のマンハッタン距離が6以下の状態まで戻して、貪欲に端からそろえる解の良い方を返しました。
子の生成 :
- 2x2と3x3だけ
- R,Lを1回
  - Rotationせずにシミュレーションすることで、2倍くらい高速化できました。
- N<=10のときは全部の位置からRotationする
- 10<N<=40のときは、１つ数を選んで、その数が2x2または3x3に含まれる位置のもう1つ外側からRotationする
盤面重複の除去 : Zobrist Hashing
評価関数 : 4*この問題のスコア + max(abs(r1-r2),abs(c1-c2)) * (abs(r1-r2)+abs(c1-c2))
その他の工夫 : 中途半端にいい位置にすると、位置のペナルティを0にしたときのスコアの改善量よりRotationのペナルティの方が大きくなって、位置のペナルティが0にならなくなるので、5x5の範囲がP*5*5以下のペナルティになったときは、ビーム幅を2倍、Rotationする位置ももう1つじゃなくて２つ外側の位置からに増やして、ペナルティを0にしやすくした。

感想ちゃんと差がつくいい問題だった。ただ基本的に、まわしてそろえるなので、去年参加した人は強そうだな～と思った。 kosakkunさんのところにも似たようなのがあって、やったことある人は強そうだな～と思った。

source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;

class Solver {
    private final int N;
    private final int P;

    private final int[][] rxcToNumber;
    private final int[] numberToR;
    private final int[] numberToC;

    private final ArrayList moves = new ArrayList<>();
    private final int[] rotatePenalties;
    private int sumRotatePenalty;

    private final long[][][] hashes;
    private long hash;

    private int[][][] evaluations;

    private final XorShift rng = new XorShift(System.nanoTime());
    private final Watch watch = new Watch();

    private Comparator comparator = new Comparator() {
        @Override
        public int compare(State o1, State o2) {

            if (o1.gridPenalty + o1.sumRotatePenalty < o2.gridPenalty + o2.sumRotatePenalty) {
                return -1;
            }
            if (o1.gridPenalty + o1.sumRotatePenalty > o2.gridPenalty + o2.sumRotatePenalty) {
                return 1;
            }

            int coef = 10;
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 < coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return -1;
            }
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 > coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return 1;
            }
            return 0;
        }
    };

    private Comparator comparator2 = new Comparator() {
        @Override
        public int compare(State o1, State o2) {
            int coef = 4;
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 < coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return -1;
            }
            if (coef * (o1.gridPenalty + o1.sumRotatePenalty) + o1.gridPenalty2 > coef * (o2.gridPenalty + o2.sumRotatePenalty) + o2.gridPenalty2) {
                return 1;
            }
            return 0;
        }
    };
    private Comparator comparator6 = new Comparator() {
        @Override
        public int compare(State2 o1, State2 o2) {
            if (o1.gridPenalty2 < o2.gridPenalty2) {
                return -1;
            }
            if (o1.gridPenalty2 > o2.gridPenalty2) {
                return 1;
            }

            if (o1.distance < o2.distance) {
                return -1;
            }
            if (o1.distance > o2.distance) {
                return 1;
            }

            if (o1.gridPenalty + o1.sumRotatePenalty < o2.gridPenalty + o2.sumRotatePenalty) {
                return -1;
            }
            if (o1.gridPenalty + o1.sumRotatePenalty > o2.gridPenalty + o2.sumRotatePenalty) {
                return 1;
            }

            return 0;
        }
    };
    private int baseDepth6 = -1;
    private ArrayList moveHistory6 = new ArrayList();
    private ArrayList moveHistoryGreedy = new ArrayList();

    public Solver(int N, int P, int[][] grid) {
        this.N = N;
        this.P = P;

        rxcToNumber = grid;
        numberToR = new int[N * N];
        numberToC = new int[N * N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                grid[r][c]--;
                numberToR[grid[r][c]] = r;
                numberToC[grid[r][c]] = c;
            }
        }

        rotatePenalties = new int[N + 1];
        for (int n = 2; n <= N; n++) {
            rotatePenalties[n] = (int) (1e-9 + Math.pow(n - 1, 1.5));
        }

        hashes = new long[N][N][N * N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                for (int number = 0; number < N * N; number++) {
                    hashes[r][c][number] = rng.nextLong();
                }
            }
        }
        hash = 0;

        evaluations = new int[N][N][N * N];
        Utils.debug("N", N, "P", P);
    }

    public void solve() {
        if (N <= 10) {
            solveOneBeam();
        } else if (N <= 40) {
            solveBeam2();
            ArrayList bestMoveHistory = new ArrayList();
            for (int i = 0; i < moveHistory.size(); i++) {
                Move move = moveHistory.get(i);
                bestMoveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
            }
            int bestScore = calculateGridPenalty() + sumRotatePenalty;
            Utils.debug("bestScore", bestScore, calculateGridPenalty(), sumRotatePenalty);
            for (; moveHistory.size() > 0;) {
                sumRotatePenalty -= rotatePenalties[moveHistory.get(moveHistory.size() - 1).size];
                previous();
            }
            for (int i = 0; i < moveHistory6.size(); i++) {
                Move move = moveHistory6.get(i);
                for (int j = 0; j < move.numRotations; j++) {
                    sumRotatePenalty += rotatePenalties[move.size];
                }
                next(move.r, move.c, move.size, move.dir, move.numRotations);
            }
            Utils.debug("score2", calculateGridPenalty(), sumRotatePenalty);

            greedy();

            int score = calculateGridPenalty() + sumRotatePenalty;
            Utils.debug("score", score, calculateGridPenalty(), sumRotatePenalty);
            if (score < bestScore) {
                moves.clear();
                for (int i = 0; i < moveHistory6.size(); i++) {
                    Move move = moveHistory6.get(i);
                    moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                }
                for (int i = 0; i < moveHistoryGreedy.size(); i++) {
                    Move move = moveHistoryGreedy.get(i);
                    moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                }

            } else {
                moves.clear();
                for (int i = 0; i < bestMoveHistory.size(); i++) {
                    Move move = bestMoveHistory.get(i);
                    moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                }

            }

        }
    }

    private void greedy() {

        int[] numbers = new int[N * N];
        {
            boolean[][] used = new boolean[N][N];
            int index = 0;
            for (int i = 0; i < N; i++) {

                {
                    int r = i;
                    for (int c = 0; c < N; c++) {
                        if (used[r][c]) {
                            continue;
                        }
                        used[r][c] = true;
                        numbers[index] = r * N + c;
                        index++;
                    }
                }
                {
                    int c = i;
                    for (int r = 0; r < N; r++) {
                        if (used[r][c]) {
                            continue;
                        }
                        used[r][c] = true;
                        numbers[index] = r * N + c;
                        index++;
                    }
                }

            }
        }
        for (int index = 0; index < N * N; index++) {
            if (index >= N * N - 16) {
                ArrayList moves = beamsearch4x4(20, 1000);
                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    this.moveHistoryGreedy.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        sumRotatePenalty += rotatePenalties[move.size];
                        rotate(move.r, move.c, move.size, move.dir);
                    }
                }
                break;
            }

            int number = numbers[index];
            if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                evaluations[numberToR[number]][numberToC[number]][number] = -1;
                continue;
            }

            ArrayList moves = dijkstra(number);
            for (int i = 0; i < moves.size(); i++) {
                State2 move = moves.get(i);
                this.moveHistoryGreedy.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                for (int j = 0; j < move.numRotations; j++) {
                    this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                    sumRotatePenalty += rotatePenalties[move.size];
                    rotate(move.r, move.c, move.size, move.dir);
                }
            }
            if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                evaluations[numberToR[number]][numberToC[number]][number] = -1;
                continue;
            }
            if (getTargetRow(number) < N - 1 && getTargetColumn(number) < N - 1) {
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        System.err.format("%3d", rxcToNumber[r][c]);
                    }
                    System.err.println();
                }
                assert false;
            }

            {
                if (numberToC[number] == N - 1) {
                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 2, 2, 'L', 1));
                    this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 2, 2, 'L', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 1, numberToC[number] - 2, 2, 'L');

                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'L', 1));
                    this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'L', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 1, numberToC[number] - 1, 2, 'L');

                    this.moveHistoryGreedy.add(new Move(numberToR[number], numberToC[number] - 2, 2, 'R', 1));
                    this.moves.add(new Move(numberToR[number], numberToC[number] - 2, 2, 'R', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number], numberToC[number] - 2, 2, 'R');
                    if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                        evaluations[numberToR[number]][numberToC[number]][number] = -1;
                        continue;
                    }
                }

                if (numberToR[number] == N - 1) {
                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 2, numberToC[number] - 1, 2, 'R', 1));
                    this.moves.add(new Move(numberToR[number] - 2, numberToC[number] - 1, 2, 'R', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 2, numberToC[number] - 1, 2, 'R');

                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'R', 1));
                    this.moves.add(new Move(numberToR[number] - 1, numberToC[number] - 1, 2, 'R', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 1, numberToC[number] - 1, 2, 'R');

                    this.moveHistoryGreedy.add(new Move(numberToR[number] - 2, numberToC[number], 2, 'L', 1));
                    this.moves.add(new Move(numberToR[number] - 2, numberToC[number], 2, 'L', 1));
                    sumRotatePenalty += rotatePenalties[2];
                    rotate(numberToR[number] - 2, numberToC[number], 2, 'L');
                    if (numberToR[number] == getTargetRow(number) && numberToC[number] == getTargetColumn(number)) {
                        evaluations[numberToR[number]][numberToC[number]][number] = -1;
                        continue;
                    }
                }

                assert false;
            }
        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("greedy", "score", score, "GridPenalty",

                calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
    }

    private ArrayList dijkstra(int number) {
        int baseDepth = moveHistory.size();

        int goalR = getTargetRow(number);
        int goalC = getTargetColumn(number);
        if (goalC == N - 1) {
            goalR++;
        } else if (goalR == N - 1) {
            goalC++;
        }

        HashSet usedHash = new HashSet();

        boolean[][] used = new boolean[N][N];

        PriorityQueue pq = new PriorityQueue<>(comparator6);
        State2 best = null;
        final int calculateGridPenalty3 = calculateGridPenalty3();
        {
            State2 e = new State2(null, -1, -1, -1, 'L', 1, calculateGridPenalty(), sumRotatePenalty, calculateGridPenalty3, manhattanDistance(goalR, goalC, numberToR[number], numberToC[number]), 1000000);
            pq.add(e);

            usedHash.add(hash);
            best = e;
        }

        int numPolls = 0;
        for (; !pq.isEmpty();) {
            State2 currentState = pq.poll();

            numPolls++;
            ArrayList moves2 = reverse2(toList(currentState));
            set2(moves2, baseDepth);
            final int r0 = numberToR[number];
            final int c0 = numberToC[number];
            used[r0][c0] = true;
            if (currentState.distance == 0) {
                best = currentState;
                break;
            }

            int margin = 0;

            for (int size = 2; size <= 2; size++) {

                int startR = Math.max(0, r0 - (size - 1) - margin);
                int endR = Math.min(N - 1, r0 + margin);
                int startC = Math.max(0, c0 - (size - 1) - margin);
                int endC = Math.min(N - 1, c0 + margin);

                for (int r = startR; r <= endR; r++) {
                    for (int c = startC; c <= endC; c++) {
                        if (!canRotate(r, c, size)) {
                            continue;
                        }

                        int currentGridPenalty = calculateGridPenalty(r, c, size);
                        int currentGridPenalty3 = calculateGridPenalty3(r, c, size);
                        long currentHash = calculateHash(r, c, size);

                        {
                            int i = 1;
                            long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                            if (usedHash.add(e)) {
                                int gridPenalty = calculateGridPenaltyR(r, c, size);
                                int gridPenalty3 = calculateGridPenalty3R(r, c, size);
                                int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                boolean isOut = r0 - r < 0 || r0 - r >= size || c0 - c < 0 || c0 - c >= size;
                                int nextR = isOut ? r0 : calculateNextR_R(r, c, size, r0 - r, c0 - c);
                                int nextC = isOut ? c0 : calculateNextC_R(r, c, size, r0 - r, c0 - c);
                                int nextPenalty3 = currentState.gridPenalty2 - currentGridPenalty3 + gridPenalty3;
                                if (nextPenalty3 <= calculateGridPenalty3) {
                                    pq.add(new State2(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, nextPenalty3, manhattanDistance(goalR, goalC, nextR, nextC), 0));
                                }
                            }
                        }
                        {
                            int i = 3;
                            long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                            if (usedHash.add(e)) {
                                int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                int gridPenalty3 = calculateGridPenalty3RRR(r, c, size);
                                int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                boolean isOut = r0 - r < 0 || r0 - r >= size || c0 - c < 0 || c0 - c >= size;
                                int nextR = isOut ? r0 : calculateNextR_RRR(r, c, size, r0 - r, c0 - c);
                                int nextC = isOut ? c0 : calculateNextC_RRR(r, c, size, r0 - r, c0 - c);
                                int nextPenalty3 = currentState.gridPenalty2 - currentGridPenalty3 + gridPenalty3;
                                if (nextPenalty3 <= calculateGridPenalty3) {
                                    pq.add(new State2(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, nextPenalty3, manhattanDistance(goalR, goalC, nextR, nextC), 0));
                                }
                            }
                        }

                    }
                }

            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }
        return reverse2(toList(best));
    }

    private void solveBeam() {
        int bestScore = (int) 1e9;
        int numBeams = 0;
        int numMoves0 = 0;
        int numMovesNot0AndNotUpdateBest = 0;
        for (; watch.getSecond() < 9.5; numBeams++) {
            if (numBeams % 50 == 0) {
                Utils.debug("numBeams", numBeams, "bestScore", bestScore);
            }
            int worstNumber = -1;
            int worst = -1;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c]));
                    if (distance <= 0) {
                        continue;
                    }

                    distance = distance * 1000 + (int) (5000 * rng.nextDouble());
                    if (distance > worst) {
                        worst = distance;
                        worstNumber = rxcToNumber[r][c];
                    }
                }
            }
            if (worstNumber == -1) {
                break;
            }

            int maxDepth = 10;
            int maxWidth = 10;
            if (N == 8) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 9) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 10) {
                maxDepth = 10;
                maxWidth = 300;
            } else if (N >= 10 && N < 15) {
                maxDepth = 10;
                maxWidth = (int) (125 + (300 - 125) / 5.0 * (15 - N));
            } else if (N == 15) {
                maxDepth = 10;
                maxWidth = 125;
            } else if (N >= 15 && N < 20) {
                maxDepth = 10;
                maxWidth = (int) (50 + (125 - 50) / 5.0 * (20 - N));
            } else if (N == 20) {
                maxDepth = 10;
                maxWidth = 50;
            } else if (N >= 20 && N < 25) {
                maxDepth = 10;
                maxWidth = (int) (26 + 4.8 * (25 - N));
            } else if (N == 25) {
                maxDepth = 10;
                maxWidth = 26;
            } else if (N >= 25 && N < 30) {
                maxDepth = 10;
                maxWidth = (int) (16 + 2 * (30 - N));
            } else if (N == 30) {
                maxDepth = 10;
                maxWidth = 16;
            } else if (N >= 30 && N <= 40) {
                maxDepth = 10;
                maxWidth = 6 + 40 - N;
            } else if (N == 40) {
                maxDepth = 10;
                maxWidth = 6;
            }

            maxDepth = 20;

            ArrayList moves = null;

            if (useOtherBeam(worstNumber)) {
                moves = beamsearchMargin2(worstNumber, maxDepth, 2 * maxWidth);
            } else {
                moves = beamsearch(worstNumber, maxDepth, maxWidth);
            }

            if (moves.size() == 0) {
                numMoves0++;
                continue;
            }

            int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty;
            if (score < bestScore) {
                bestScore = score;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

                assert score == calculateGridPenalty() + sumRotatePenalty;

            } else {
                numMovesNot0AndNotUpdateBest++;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

            }

        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
        Utils.debug("numMoves0", numMoves0, "numMovesNot0AndNotUpdateBest", numMovesNot0AndNotUpdateBest);
    }

    private void solveBeam2() {
        int bestScore = (int) 1e9;
        int numBeams = 0;
        int numMoves0 = 0;
        int numMovesNot0AndNotUpdateBest = 0;
        for (; watch.getSecond() < 9.0; numBeams++) {
            if (numBeams % 50 == 0) {
                Utils.debug("numBeams", numBeams, "bestScore", bestScore);
            }
            int worstNumber = -1;
            int worst = -1;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c]));
                    if (distance <= 6) {
                        continue;
                    }

                    distance = distance * 1000 + (int) (5000 * rng.nextDouble());
                    if (distance > worst) {
                        worst = distance;
                        worstNumber = rxcToNumber[r][c];
                    }
                }
            }
            if (worstNumber == -1) {
                if (baseDepth6 == -1) {
                    baseDepth6 = moveHistory.size();
                    for (int i = 0; i < moveHistory.size(); i++) {
                        Move move = moveHistory.get(i);
                        moveHistory6.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    }
                    Utils.debug("score2", calculateGridPenalty(), sumRotatePenalty);
                }
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        int distance = manhattanDistance(r, c, getTargetRow(rxcToNumber[r][c]), getTargetColumn(rxcToNumber[r][c]));
                        if (distance <= 0) {
                            continue;
                        }

                        distance = distance * 1000 + (int) (5000 * rng.nextDouble());
                        if (distance > worst) {
                            worst = distance;
                            worstNumber = rxcToNumber[r][c];
                        }
                    }
                }
                if (worstNumber == -1) {
                    break;
                }
            }

            int maxDepth = 10;
            int maxWidth = 10;
            if (N == 8) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 9) {
                maxDepth = 20;
                maxWidth = 100;
            } else if (N == 10) {
                maxDepth = 10;
                maxWidth = 300;
            } else if (N >= 10 && N < 15) {
                maxDepth = 10;
                maxWidth = (int) (125 + (300 - 125) / 5.0 * (15 - N));
            } else if (N == 15) {
                maxDepth = 10;
                maxWidth = 125;
            } else if (N >= 15 && N < 20) {
                maxDepth = 10;
                maxWidth = (int) (50 + (125 - 50) / 5.0 * (20 - N));
            } else if (N == 20) {
                maxDepth = 10;
                maxWidth = 50;
            } else if (N >= 20 && N < 25) {
                maxDepth = 10;
                maxWidth = (int) (26 + 4.8 * (25 - N));
            } else if (N == 25) {
                maxDepth = 10;
                maxWidth = 26;
            } else if (N >= 25 && N < 30) {
                maxDepth = 10;
                maxWidth = (int) (16 + 2 * (30 - N));
            } else if (N == 30) {
                maxDepth = 10;
                maxWidth = 16;
            } else if (N >= 30 && N <= 40) {
                maxDepth = 10;
                maxWidth = 6 + 40 - N;
            } else if (N == 40) {
                maxDepth = 10;
                maxWidth = 6;
            }

            maxDepth = 20;

            ArrayList moves = null;

            if (useOtherBeam(worstNumber)) {
                moves = beamsearchMargin2(worstNumber, maxDepth, 2 * maxWidth);
            } else {
                moves = beamsearch(worstNumber, maxDepth, maxWidth);
            }

            if (moves.size() == 0) {
                numMoves0++;
                continue;
            }

            int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty;
            if (score < bestScore) {
                bestScore = score;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    moveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

                assert score == calculateGridPenalty() + sumRotatePenalty;

            } else {
                numMovesNot0AndNotUpdateBest++;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);
                    moveHistory.add(new Move(move.r, move.c, move.size, move.dir, move.numRotations));
                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];
                    }
                }

            }

        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
        Utils.debug("numMoves0", numMoves0, "numMovesNot0AndNotUpdateBest", numMovesNot0AndNotUpdateBest);
    }

    private boolean useOtherBeam(int number) {
        int r = numberToR[number];
        int c = numberToC[number];
        r = Math.max(2, Math.min(N - 3, r));
        c = Math.max(2, Math.min(N - 3, c));
        int startR = r - 2;
        int startC = c - 2;
        int endR = r + 3;
        int endC = c + 3;
        return calculateGridPenalty(startR, startC, Math.min(endR - startR, endC - startC)) <= P * (endR - startR) * (endC - startC);
    }

    private void solveOneBeam() {
        int bestScore = (int) 1e9;
        int numBeams = 0;
        {

            int maxDepth = 1000;
            int maxWidth = 10;
            if (N == 4) {
                maxDepth = 25;
                maxWidth = 18000;
            } else if (N == 5) {
                maxDepth = 40;
                maxWidth = 6000;
            } else if (N == 6) {
                maxDepth = 60;
                maxWidth = 2500;
            } else if (N == 7) {
                maxDepth = 100;
                maxWidth = 1100;
            } else if (N == 8) {
                maxDepth = 150;
                maxWidth = 550;
            } else if (N == 9) {
                maxDepth = 220;
                maxWidth = 280;
            } else if (N == 10) {
                maxDepth = 320;
                maxWidth = 150;
            }
            ArrayList moves = beamsearch(maxDepth, maxWidth);

            int[] counts = new int[30];

            int score = moves.get(moves.size() - 1).gridPenalty + moves.get(moves.size() - 1).sumRotatePenalty;
            if (score < bestScore) {
                bestScore = score;

                for (int i = 0; i < moves.size(); i++) {
                    State move = moves.get(i);

                    for (int j = 0; j < move.numRotations; j++) {
                        this.moves.add(new Move(move.r, move.c, move.size, move.dir, 1));
                        rotate(move.r, move.c, move.size, move.dir);
                        sumRotatePenalty += rotatePenalties[move.size];

                        counts[move.size]++;
                    }
                }

                assert score == calculateGridPenalty() + sumRotatePenalty : Utils.toString(moves.get(moves.size() - 1).gridPenalty, moves.get(moves.size() - 1).sumRotatePenalty, calculateGridPenalty(), sumRotatePenalty);

            }

            Utils.debug("counts", counts);

        }

        int score = calculateGridPenalty() + sumRotatePenalty;
        Utils.debug("numBeams", numBeams, "score", score, "GridPenalty", calculateGridPenalty(), "sumRotatePenalty", sumRotatePenalty, "time", watch.getSecondString());
    }

    private boolean canRotate(int r, int c, int size) {
        return r >= 0 && c >= 0 && r + size <= N && c + size <= N;
    }

    private void rotate(int r0, int c0, int n, char dir0) {
        hash ^= calculateHash(r0, c0, n);
        if (dir0 == 'R') {
            for (int r = 0, m = n - 1, halfN = n / 2, halfN2 = (n - 1) / 2; r < halfN; r++) {
                for (int c = 0; c <= halfN2; c++) {
                    int swapppppppppppppppppppppppppppp = rxcToNumber[r0 + 0 + r][c0 + 0 + c];
                    rxcToNumber[r0 + 0 + r][c0 + 0 + c] = rxcToNumber[r0 + m - c][c0 + 0 + r];
                    rxcToNumber[r0 + m - c][c0 + 0 + r] = rxcToNumber[r0 + m - r][c0 + m - c];
                    rxcToNumber[r0 + m - r][c0 + m - c] = rxcToNumber[r0 + 0 + c][c0 + m - r];
                    rxcToNumber[r0 + 0 + c][c0 + m - r] = swapppppppppppppppppppppppppppp;
                }
            }
        } else {
            for (int r = 0, m = n - 1, halfN = n / 2, halfN2 = (n - 1) / 2; r < halfN; r++) {
                for (int c = 0; c <= halfN2; c++) {
                    int swapppppppppppppppppppppppppppp = rxcToNumber[r0 + 0 + r][c0 + 0 + c];
                    rxcToNumber[r0 + 0 + r][c0 + 0 + c] = rxcToNumber[r0 + 0 + c][c0 + m - r];
                    rxcToNumber[r0 + 0 + c][c0 + m - r] = rxcToNumber[r0 + m - r][c0 + m - c];
                    rxcToNumber[r0 + m - r][c0 + m - c] = rxcToNumber[r0 + m - c][c0 + 0 + r];
                    rxcToNumber[r0 + m - c][c0 + 0 + r] = swapppppppppppppppppppppppppppp;
                }
            }
        }
        hash ^= calculateHash(r0, c0, n);
        updateNumberToRxc(r0, c0, n);
    }

    private int calculateNextR_R(int r0, int c0, int size0, int r, int c) {
        return r0 + 0 + c;
    }

    private int calculateNextR_RR(int r0, int c0, int size0, int r, int c) {
        return r0 + (size0 - 1) - r;
    }

    private int calculateNextR_RRR(int r0, int c0, int size0, int r, int c) {
        return r0 + (size0 - 1) - c;
    }

    private int calculateNextC_R(int r0, int c0, int size0, int r, int c) {
        return c0 + (size0 - 1) - r;
    }

    private int calculateNextC_RR(int r0, int c0, int size0, int r, int c) {
        return c0 + (size0 - 1) - c;
    }

    private int calculateNextC_RRR(int r0, int c0, int size0, int r, int c) {
        return c0 + 0 + r;
    }

    private int calculateGridPenaltyR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenaltyRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenaltyRRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                penalty += manhattanDistance(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty() {
        int penalty = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty3R(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3RR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3RRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + r][c0 + c];
                penalty += evaluations[r0 + r][c0 + c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty3() {
        int penalty = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int number = rxcToNumber[r][c];
                penalty += evaluations[r][c][number];
            }
        }
        return penalty;
    }

    private int calculateGridPenalty2R(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2RR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2RRR(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                penalty += manhattanDistance2(r0 + r, c0 + c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2(int r0, int c0, int size0) {
        int penalty = 0;
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance2(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    private int calculateGridPenalty2() {
        int penalty = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                int number = rxcToNumber[r][c];
                penalty += manhattanDistance2(r, c, getTargetRow(number), getTargetColumn(number));
            }
        }
        return P * penalty;
    }

    public String[] makeSolution() {
        String[] res = new String[moves.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = "" + moves.get(i).r + " " + moves.get(i).c + " " + moves.get(i).size + " " + moves.get(i).dir;
        }
        return res;
    }

    private int getTargetColumn(int number) {
        return number % N;
    }

    private int getTargetRow(int number) {
        return number / N;
    }

    private static int manhattanDistance2(int r, int c, int r2, int c2) {
        int absR = Math.abs(r - r2);
        int absC = Math.abs(c - c2);
        return Math.max(absR, absC) * (absR + absC);
    }

    private static int manhattanDistance(int r, int c, int r2, int c2) {
        int absR = Math.abs(r - r2);
        int absC = Math.abs(c - c2);
        return (absR + absC);
    }

    private ArrayList beamsearch4x4(int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();
        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }
        int sumWidth = 0;

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }
            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator.compare(currentState, best) < 0) {
                    best = currentState;
                }

                if (Integer.bitCount(depth) == 1) {
                    if (width == 0) {
                        Utils.debug(depth, currentState.gridPenalty, currentState.sumRotatePenalty);
                    }
                }

                set(reverse2(toList(currentState)), baseDepth);

                for (int size = 2; size <= 3; size++) {
                    for (int r = N - 4; r < N; r++) {
                        for (int c = N - 4; c < N; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }

                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);
                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }
        return reverse2(toList(best));
    }

    private ArrayList beamsearch(int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();
        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }
        int sumWidth = 0;

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }

            if (depth % 4 == 0) {
                usedHash.clear();
            }
            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator.compare(currentState, best) < 0) {
                    best = currentState;
                }

                if (Integer.bitCount(depth) == 1) {
                    if (width == 0) {
                        Utils.debug(depth, currentState.gridPenalty, currentState.sumRotatePenalty);
                    }
                }

                set(reverse2(toList(currentState)), baseDepth);

                for (int size = 2; size <= 3; size++) {
                    for (int r = 0; r < N; r++) {
                        for (int c = 0; c < N; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }

                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);
                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }

                            }
                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }

        Utils.debug("mean width", sumWidth / (double) maxDepth);

        return reverse2(toList(best));
    }

    private ArrayList beamsearch(int number, int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();

        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }

            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator2.compare(currentState, best) < 0) {
                    best = currentState;
                }

                set(reverse2(toList(currentState)), baseDepth);

                int targetR = numberToR[number];
                int targetC = numberToC[number];

                int margin = 1;

                for (int size = 2; size <= 3; size++) {

                    int startR = Math.max(0, targetR - (size - 1) - margin);
                    int endR = Math.min(N - 1, targetR + margin);
                    int startC = Math.max(0, targetC - (size - 1) - margin);
                    int endC = Math.min(N - 1, targetC + margin);

                    for (int r = startR; r <= endR; r++) {
                        for (int c = startC; c <= endC; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }
                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);

                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }

                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator2.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }

        return reverse2(toList(best));
    }

    private ArrayList beamsearchMargin2(int number, int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();

        HashSet usedHash = new HashSet();

        ArrayList[] states = new ArrayList[1 << 5];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            int gridPenalty = calculateGridPenalty();
            int gridPenalty2 = calculateGridPenalty2();
            State e = new State(null, -1, -1, -1, 'R', -1, gridPenalty, sumRotatePenalty, gridPenalty2);
            states[0].add(e);

            usedHash.add(hash);

            best = e;
        }

        for (int depth = 0; depth < maxDepth; depth++) {
            if (states[0].size() == 0) {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
                continue;
            }

            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparator2);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (comparator2.compare(currentState, best) < 0) {
                    best = currentState;
                }

                set(reverse2(toList(currentState)), baseDepth);

                int targetR = numberToR[number];
                int targetC = numberToC[number];

                int margin = 2;

                for (int size = 2; size <= 3; size++) {

                    int startR = Math.max(0, targetR - (size - 1) - margin);
                    int endR = Math.min(N - 1, targetR + margin);
                    int startC = Math.max(0, targetC - (size - 1) - margin);
                    int endC = Math.min(N - 1, targetC + margin);

                    for (int r = startR; r <= endR; r++) {
                        for (int c = startC; c <= endC; c++) {
                            if (!canRotate(r, c, size)) {
                                continue;
                            }
                            int currentGridPenalty = calculateGridPenalty(r, c, size);
                            int currentGridPenalty2 = calculateGridPenalty2(r, c, size);
                            long currentHash = calculateHash(r, c, size);

                            {
                                int i = 1;
                                long e = hash ^ currentHash ^ calculateHashR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2R(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }
                            {
                                int i = 3;
                                long e = hash ^ currentHash ^ calculateHashRRR(r, c, size);
                                if (usedHash.add(e)) {
                                    int gridPenalty = calculateGridPenaltyRRR(r, c, size);
                                    int gridPenalty2 = calculateGridPenalty2RRR(r, c, size);
                                    int rotatePenalty = (i < 3 ? i : 1) * rotatePenalties[size];
                                    states[rotatePenalty].add(new State(currentState, r, c, size, i < 3 ? 'R' : 'L', i < 3 ? i : 1, currentState.gridPenalty - currentGridPenalty + gridPenalty, currentState.sumRotatePenalty + rotatePenalty, currentState.gridPenalty2 - currentGridPenalty2 + gridPenalty2));
                                }
                            }

                        }
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0]);
            if (comparator2.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }

        return reverse2(toList(best));
    }

    private long calculateHashR(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - c][c0 + 0 + r];
                hash ^= hashes[r0 + r][c0 + c][number];
            }
        }
        return hash;
    }

    private long calculateHashRR(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + m - r][c0 + m - c];
                hash ^= hashes[r0 + r][c0 + c][number];
            }
        }
        return hash;
    }

    private long calculateHashRRR(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = 0, m = size0 - 1; r < size0; r++) {
            for (int c = 0; c < size0; c++) {
                int number = rxcToNumber[r0 + 0 + c][c0 + m - r];
                hash ^= hashes[r0 + r][c0 + c][number];
            }
        }
        return hash;
    }

    private long calculateHash(int r0, int c0, int size0) {
        long hash = 0;
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                int number = rxcToNumber[r][c];
                hash ^= hashes[r][c][number];
            }
        }
        return hash;
    }

    private void updateNumberToRxc(int r0, int c0, int size0) {
        for (int r = r0; r < r0 + size0; r++) {
            for (int c = c0; c < c0 + size0; c++) {
                numberToR[rxcToNumber[r][c]] = r;
                numberToC[rxcToNumber[r][c]] = c;
            }
        }
    }

    public void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < moveHistory.size(); i++) {
            if (!isSameMove(moveHistory.get(startIndex + i), list.get(i))) {
                break;
            }
            startIndexMinus1 = startIndex + i;
        }
        for (; moveHistory.size() > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State state2 = list.get(i);
            next(state2.r, state2.c, state2.size, state2.dir, state2.numRotations);
        }
    }

    private boolean isSameMove(Move move, State state) {
        if (state.r != move.r || state.c != move.c || state.size != move.size || state.dir != move.dir || state.numRotations != move.numRotations) {
            return false;
        }
        return true;
    }

    public void set2(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < moveHistory.size(); i++) {
            if (!isSameMove(moveHistory.get(startIndex + i), list.get(i))) {
                break;
            }
            startIndexMinus1 = startIndex + i;
        }
        for (; moveHistory.size() > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State2 state2 = list.get(i);
            next(state2.r, state2.c, state2.size, state2.dir, state2.numRotations);
        }
    }

    private boolean isSameMove(Move move, State2 state) {
        if (state.r != move.r || state.c != move.c || state.size != move.size || state.dir != move.dir || state.numRotations != move.numRotations) {
            return false;
        }
        return true;
    }

    private ArrayList moveHistory = new ArrayList<>();

    public void next(int r, int c, int size, char dir, int numRotations) {
        moveHistory.add(new Move(r, c, size, dir, numRotations));
        for (int i = 0; i < numRotations; i++) {
            rotate(r, c, size, dir);
        }
    }

    public void previous() {
        Move lastMove = moveHistory.remove(moveHistory.size() - 1);
        int r = lastMove.r;
        int c = lastMove.c;
        int size = lastMove.size;
        char dir = lastMove.dir == 'L' ? 'R' : 'L';
        for (int i = 0; i < lastMove.numRotations; i++) {
            rotate(r, c, size, dir);
        }
    }

    private  ArrayList reverse2(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    private ArrayList toList(State state0) {
        ArrayList res = new ArrayList<>();
        for (State current = state0; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    private ArrayList toList(State2 state0) {
        ArrayList res = new ArrayList<>();
        for (State2 current = state0; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

}

class State implements Comparable {

    State parent;
    int r;
    int c;
    int size;
    char dir;
    int numRotations;
    int gridPenalty;
    int gridPenalty2;
    int sumRotatePenalty;

    public State(State parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.sumRotatePenalty = sumRotatePenalty;
    }

    public State(State parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int gridPenalty2) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.gridPenalty2 = gridPenalty2;
        this.sumRotatePenalty = sumRotatePenalty;
    }

    @Override
    public int compareTo(State o) {
        if (gridPenalty < o.gridPenalty) {
            return -1;
        }
        if (gridPenalty > o.gridPenalty) {
            return 1;
        }
        return 0;
    }

}

class State2 {

    State2 parent;
    int r;
    int c;
    int size;
    char dir;
    int numRotations;
    int gridPenalty;
    int gridPenalty2;
    int sumRotatePenalty;

    int distance;
    int c2;

    public State2(State2 parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int r2, int c2) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.sumRotatePenalty = sumRotatePenalty;
        this.distance = r2;
        this.c2 = c2;
    }

    public State2(State2 parent, int r, int c, int size, char dir, int numRotations, int gridPenalty, int sumRotatePenalty, int gridPenalty2, int r2, int c2) {
        super();
        this.parent = parent;
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
        this.gridPenalty = gridPenalty;
        this.gridPenalty2 = gridPenalty2;
        this.sumRotatePenalty = sumRotatePenalty;
        this.distance = r2;
        this.c2 = c2;
    }

}

class Move {
    int r;
    int c;
    int size;
    char dir;
    int numRotations;

    public Move(int r, int c, int size, char dir, int numRotations) {
        super();
        this.r = r;
        this.c = c;
        this.size = size;
        this.dir = dir;
        this.numRotations = numRotations;
    }
}

public class RotatingNumbers {

    public String[] findSolution(int N, int P, int[][] grid) {
        Solver solver = new Solver(N, P, grid);
        solver.solve();
        return solver.makeSolution();
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            int N = Integer.parseInt(br.readLine());
            int P = Integer.parseInt(br.readLine());
            int[][] grid = new int[N][N];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    grid[r][c] = Integer.parseInt(br.readLine());
                }
            }

            RotatingNumbers prog = new RotatingNumbers();
            String[] ret = prog.findSolution(N, P, grid);

            System.out.println(ret.length);
            for (int i = 0; i < ret.length; i++) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class CollectionsUtils {
    private CollectionsUtils() {
    }

    public static final  void shuffle(ArrayList list, Random rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void shuffle(ArrayList list, XorShift rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void select0(ArrayList a, int l, int r, int k, Comparator comparator) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r, comparator);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final  void select(ArrayList a, int startInclusive, int endExclusive, int k, Comparator comparator) {
        select0(a, startInclusive, endExclusive - 1, k, comparator);
    }

    public static final > void select0(ArrayList a, int l, int r, int k) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final > void select(ArrayList a, int startInclusive, int endExclusive, int k) {
        select0(a, startInclusive, endExclusive - 1, k);
    }

    public static final  void swap(ArrayList a, int i, int j) {
        T swap = a.set(i, a.get(j));
        a.set(j, swap);
    }

    public static final  void sort3(ArrayList a, int i, int j, int k, Comparator comparator) {
        if (comparator.compare(a.get(i), a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (comparator.compare(a.get(i), a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (comparator.compare(a.get(j), a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final > void sort3(ArrayList a, int i, int j, int k) {
        if (a.get(i).compareTo(a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (a.get(i).compareTo(a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (a.get(j).compareTo(a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final  int partition3(ArrayList a, int l, int r, Comparator comparator) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r, comparator);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; comparator.compare(a.get(++i), v) < 0;) {
            }
            for (; comparator.compare(a.get(--j), v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition3(ArrayList a, int l, int r) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; a.get(++i).compareTo(v) < 0;) {
            }
            for (; a.get(--j).compareTo(v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition(ArrayList a, int l, int r) {
        int i = l - 1, j = r;
        T v = a.get(r);
        for (;;) {
            while (a.get(++i).compareTo(v) < 0)
                ;
            while (v.compareTo(a.get(--j)) < 0)
                if (j == l)
                    break;
            if (i >= j)
                break;
            swap(a, i, j);
        }
        swap(a, i, r);
        return i;
    }

    public static final  void sort(ArrayList a, int lInclusive, int rInclusive, Comparator comparator) {
        if (lInclusive >= rInclusive) {
            return;
        }
        int k = partition3(a, lInclusive, rInclusive, comparator);
        sort(a, lInclusive, k - 1, comparator);
        sort(a, k + 1, rInclusive, comparator);
    }

    public static final > void sort(ArrayList a, int lInclusive, int rInclusive) {
        if (lInclusive >= rInclusive) {
            return;
        }
        int k = partition3(a, lInclusive, rInclusive);
        sort(a, lInclusive, k - 1);
        sort(a, k + 1, rInclusive);
    }

    public static final  ArrayList reverse(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    public static final  ArrayList newReverse(ArrayList list) {
        ArrayList res = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            res.add(list.get(i));
        }
        return res;
    }

}

final class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

}

class Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

class XorShift {
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;

    public XorShift(long l) {
        x = (int) l;
    }

    public int nextInt() {
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

}

↑このページのトップヘ