EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)




Approach ビームサーチを使いました。

  • ビーム幅:100に固定
  • 評価関数:Σ使ってない石 (進める方向の数/2)

感想
  • 最適解がでやすかった。



Source Code 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;
import java.util.Scanner;

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

    private final int N;

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

    private int[] r;
    private int[] c;
    private int[][] rxcToIndex;

    private ArrayList[][] adjacentIndexes;

    private int minC;
    private int maxC;
    private int minR;
    private int maxR;

    public Solver(int N, int[] x, int[] y) {
        this.N = N;
        this.r = y;
        this.c = x;

        used = new boolean[N];

        minR = (int) 1e9;
        maxR = (int) -1e9;
        minC = (int) 1e9;
        maxC = (int) -1e9;
        for (int i = 0; i < N; i++) {
            minR = Math.min(minR, r[i]);
            maxR = Math.max(maxR, r[i]);
            minC = Math.min(minC, c[i]);
            maxC = Math.max(maxC, c[i]);
        }

        rxcToIndex = new int[maxR + 1][maxC + 1];
        for (int i = 0; i < rxcToIndex.length; i++) {
            Arrays.fill(rxcToIndex[i], -1);
        }
        for (int i = 0; i < N; i++) {
            rxcToIndex[r[i]][c[i]] = i;
        }

        adjacentIndexes = new ArrayList[N][dr.length];
        for (int i = 0; i < N; i++) {
            for (int d = 0; d < dr.length; d++) {
                adjacentIndexes[i][d] = new ArrayList();
            }
        }

        for (int i = 0; i < N; i++) {
            for (int d = 0; d < dr.length; d++) {
                for (int length = 1; length < 1000; length++) {
                    int nr = r[i] + dr[d] * length;
                    int nc = c[i] + dc[d] * length;

                    if (!isValid(nr, minR, maxR) || !isValid(nc, minC, maxC)) {
                        break;
                    }

                    if (rxcToIndex[nr][nc] != -1) {
                        adjacentIndexes[i][d].add(rxcToIndex[nr][nc]);
                    }
                }
            }
        }

        Utils.debug("N", N);
    }

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

    ArrayList moves;

    private Comparator comparatorEven = new Comparator() {
        @Override
        public int compare(State o1, State o2) {
            if (o1.length > o2.length) {
                return -1;
            }
            if (o1.length < o2.length) {
                return 1;
            }

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

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

    public void solve() {
        moves = beamsearch(N, 100);
    }

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

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

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

        State best = null;
        {
            for (int i = 0; i < N; i++) {
                int link = 0;
                for (int d = 0; d < dr.length; d++) {
                    for (int i2 = 0; i2 < adjacentIndexes[i][d].size(); i2++) {
                        int index = adjacentIndexes[i][d].get(i2).intValue();
                        if (used[index]) {
                            continue;
                        }
                        link++;
                    }
                }
                if (link == 0) {
                    continue;
                }
                next(i);
                int score = calculateScore();
                previous();
                states[0].add(new State(null, i, 1, score));

            }
        }
        for (int depth = 0; depth < maxDepth; depth++) {
            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparatorEven);

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

                if (best == null || comparatorEven.compare(currentState, best) < 0) {
                    best = currentState;
                }

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

                int parentI = currentState.parent == null ? -1 : currentState.parent.i;
                int parentD = parentI == -1 ? -1 : (r[parentI] != r[currentState.i] ? (r[parentI] < r[currentState.i] ? 3 : 0) : (c[parentI] < c[currentState.i] ? 2 : 1));
                int reverseD = 3 - parentD;
                for (int d = 0; d < dr.length; d++) {
                    if (d == reverseD) {
                        continue;
                    }
                    for (int i = 0; i < adjacentIndexes[currentState.i][d].size(); i++) {
                        int index = adjacentIndexes[currentState.i][d].get(i).intValue();
                        if (used[index]) {
                            continue;
                        }

                        next(index);
                        int score = calculateScore();
                        previous();

                        states[1].add(new State(currentState, index, currentState.length + 1, score));
                        break;
                    }
                }

            }
            {
                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], comparatorEven);
            if (best == null || comparatorEven.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }
        ArrayList list = reverse2(toList(best));
        return list;
    }

    private int calculateScore() {
        int even = 0;
        for (int i = 0; i < N; i++) {
            if (used[i]) {
                continue;
            }
            int link = 0;
            for (int d = 0; d < dr.length; d++) {
                for (int i2 = 0; i2 < adjacentIndexes[i][d].size(); i2++) {
                    int index3 = adjacentIndexes[i][d].get(i2).intValue();
                    if (used[index3]) {
                        continue;
                    }
                    link++;
                    break;
                }
            }
            even += link / 2;
        }
        return even;
    }

    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.i);
        }
    }

    private boolean isSameMove(Integer move, State state) {
        if (state.i != move.intValue()) {
            return false;
        }
        return true;
    }

    private ArrayList moveHistory = new ArrayList<>();
    private boolean[] used;

    public void next(int i) {
        moveHistory.add(i);
        used[i] = true;
    }

    public void previous() {
        int i = moveHistory.remove(moveHistory.size() - 1).intValue();
        used[i] = false;
    }

    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 != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    class State {

        State parent;
        int i;
        int length;
        int numEvens;
        int random;

        public State(State parent, int i, int length) {
            super();
            this.parent = parent;
            this.i = i;
            this.length = length;
            random = rng.nextInt();
        }

        public State(State parent, int i, int length, int numEvens) {
            super();
            this.parent = parent;
            this.i = i;
            this.length = length;
            this.numEvens = numEvens;
            random = rng.nextInt();
        }

    }

}

public class Main {

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

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {

            int N = sc.nextInt();
            int x[] = new int[N];
            int y[] = new int[N];
            for (int i = 0; i < N; i++) {
                x[i] = sc.nextInt();
                y[i] = sc.nextInt();
            }

            int[] ret = new Main().findSolution(N, x, y);

            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());
    }

}




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

感想
  • 私が見た一番小さいスコアは2だったけど、上位は1とか出しているんだろうか?
    • スコア1を確認できた。(5/29 追記)
  • 焼きなまし法がうまくいく問題で、焼きなまし法を使って負けるパターンは、
    1. 焼きなまし法よりいい方法があった
      • TSP:3opt + kick, Guided Local Search
      • Vertex Coloring:Tabu Search
      • Graph Golf:GA
      • ...
    2. いい評価関数があった
      • GraphReconstruction
      • ...
    3. いい近傍があった
      • CrystalLighting
      • ...
    4. 高速化で負けた
    5. その他
    だと思うけど、今回はどれだろうか?高速化で負けていると思うけど、大差なのでその他もありえそう。
    • 評価関数だった(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);
        }
    }
    
    



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のときは、1つ数を選んで、その数が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つじゃなくて2つ外側の位置からに増やして、ペナルティを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());
    }

}



↑このページのトップヘ