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

  • 近傍1 : ランダムに grid を移動する
    • 95点台
  • 近傍2 : grid を交換する
    • 95点台+
  • 近傍3 : ある行または列から後のすべての grids を、1つまたは2つ移動する
    • 98点台


データ構造 差の絶対値の和を最小化するのに、中央値を求める必要がありました。
  • データ構造1 : ソートしたリスト(Binary Indexed Tree)
    • 追加 : O(logN), 削除 : O(logN), 中央値 : O(logN)
      • 遅かった。
  • データ構造2 : ソートしたリスト(配列)
    • 追加(最後に追加して挿入ソート) : O(N), 削除 : O(N), 中央値 : O(1)
      • grid の重複が多いときに早かった。使い分けはせずに、常にこれを使った。
  • データ構造3 : リスト(配列)
    • 追加 : O(1), 削除 : O(N), 中央値 : O(N)
      • grid の重複が少ないときに早かった。


source code

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

public class Lossy2dCompression {
    static final Watch watch = new Watch();
    static final XorShift rng = new XorShift(System.nanoTime());
    private SAState sa = new SAState();

    private double P;
    private int N;
    private int[][][] grids;
    private int[] numRows;
    private int[] numColumns;

    private int[] startRows;
    private int[] startColumns;
    private IntListSorted[][] compressed;
    private double score;

    private int[] bestStartRows;
    private int[] bestStartColumns;
    private IntListSorted[][] bestCompressed;
    private double bestScore;

    private int totalArea;
    private int errors;
    private int maxRows;
    private int maxColumns;

    private int compColumns = 20;

    private IntList list;
    private int[] Ns = new int[] { 5, 25, 50, 100, };
    private double[] Ps = new double[] { 0.05, 0.5, 0.95, };
    private double[][] temperatures = new double[][] { { 0.0008, 0.0001, 0.0001, 0.00005, }, { 0.001, 0.0008, 0.0006, 0.0004, }, { 0.0002, 0.0002, 0.0004, 0.0004, }, };

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

    public String[] findSolution(double P, int N, String[][] grids) {
        init(P, N, grids);
        solve();
        return makeSolution();
    }

    private void init(double P, int N, String[][] grids) {
        Utils.debug("P", P, "N", N, "grids.length", grids.length);
        this.P = P;
        this.N = N;
        this.grids = new int[N][][];
        this.numRows = new int[N];
        this.numColumns = new int[N];
        for (int i = 0; i < N; i++) {
            String[] grid = grids[i];
            int R = grid.length;
            int C = grid[0].length();
            this.grids[i] = new int[R][C];
            this.numRows[i] = R;
            this.numColumns[i] = C;
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    this.grids[i][r][c] = grid[r].charAt(c) - 'A';
                }
            }
        }

        int sumRows = 0;
        for (int i = 0; i < N; i++) {
            sumRows += numRows[i];
        }

        int maxRows = 0;
        for (int i = 0; i < N; i++) {
            maxRows = Math.max(maxRows, numRows[i]);
        }

        int maxColumns = 0;
        for (int i = 0; i < N; i++) {
            maxColumns = Math.max(maxColumns, numColumns[i]);
        }
        Utils.debug("sumRows", sumRows, "maxRows", maxRows, "maxColumns", maxColumns);

        compressed = new IntListSorted[sumRows][compColumns];
        for (int r = 0; r < sumRows; r++) {
            for (int c = 0; c < compColumns; c++) {
                compressed[r][c] = new IntListSorted(N + 1);
            }
        }

        startRows = new int[N];
        startColumns = new int[N];

        bestCompressed = new IntListSorted[sumRows][compColumns];
        for (int r = 0; r < sumRows; r++) {
            for (int c = 0; c < compColumns; c++) {
                bestCompressed[r][c] = new IntListSorted(N + 1);
            }
        }

        bestStartRows = new int[N];
        bestStartColumns = new int[N];

        totalArea = 0;
        for (int i = 0; i < N; i++) {
            int[][] grid = this.grids[i];
            totalArea += grid.length * grid[0].length;
        }

        used = new InitializedBooleanArray_v2();
        used.init(sumRows * compColumns);

        list = new IntList(N + 1);

        Utils.debug("init", "time", watch.getSecondString());
    }

    private void solve() {
        loss0();
        SA();
    }

    private void loss0() {
        int currentR = 0;
        for (int i = 0; i < N; i++) {
            startRows[i] = currentR;
            startColumns[i] = 0;

            int[][] grid = grids[i];
            for (int r = 0; r < numRows[i]; r++) {
                for (int c = 0; c < numColumns[i]; c++) {
                    compressed[currentR + r][c].add(grid[r][c]);
                }
            }

            currentR += numRows[i];
        }
        maxRows = calculateMaxRows();
        maxColumns = calculateMaxColumns();
        errors = calculateErrors();
        score = calculateScore();
        bestScore = 1e9;
        saveBest();
        Utils.debug("loss0", "score", score, "time", watch.getSecondString());
    }

    private void SA() {
        double second = watch.getSecond();
        {
            double eps = 1e-9;
            niLoop: for (int ni = 1; ni < Ns.length; ni++) {
                if (Ns[ni - 1] <= N && N <= Ns[ni]) {
                    Utils.debug(Ns[ni - 1], N, Ns[ni]);

                    for (int pi = 1; pi < Ps.length; pi++) {
                        if (Ps[pi - 1] - eps <= P && P <= Ps[pi] + eps) {
                            Utils.debug(Ps[pi - 1], P, Ps[pi]);

                            double d = (1.0 * N - Ns[ni - 1]) / (Ns[ni] - Ns[ni - 1]);
                            double a = interpolate(temperatures[pi - 1][ni - 1], temperatures[pi - 1][ni + 0], d);
                            double b = interpolate(temperatures[pi + 0][ni - 1], temperatures[pi + 0][ni + 0], d);
                            Utils.debug(d, a, b);

                            double d2 = (P - Ps[pi - 1]) / (Ps[pi] - Ps[pi - 1]);
                            double c = interpolate(a, b, d2);
                            Utils.debug(d2, c);

                            sa.startTemperature = c;

                            break niLoop;
                        }
                    }

                }
            }
        }
        sa.init();
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 5) - 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("%.3f", score), String.format("%.3f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                    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("%.3f", score), String.format("%.3f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }
            }

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

    private void mutate() {
        double random = 2.1 * rng.nextDouble();
        if (random < 1) {
            move();
        } else if (random < 2) {
            swap();
        } else if (random < 2.1) {
            slide();
        }
    }

    private void move() {
        int index = (int) (N * rng.nextDouble());

        int r;
        int c;
        if (rng.nextDouble() < 0.5) {
            r = (int) (maxRows * rng.nextDouble());
            c = (int) (maxColumns * rng.nextDouble());
        } else {
            r = startRows[index] + -2 + (int) (5 * rng.nextDouble());
            c = startColumns[index] + -2 + (int) (5 * rng.nextDouble());
            r = Math.max(0, Math.min(maxRows - 1, r));
            c = Math.max(0, Math.min(maxColumns - 1, c));
        }
        while (r + numRows[index] > compressed.length || c + numColumns[index] > compressed[0].length) {
            if (rng.nextDouble() < 0.5) {
                r = (int) (maxRows * rng.nextDouble());
                c = (int) (maxColumns * rng.nextDouble());
            } else {
                r = startRows[index] + -2 + (int) (5 * rng.nextDouble());
                c = startColumns[index] + -2 + (int) (5 * rng.nextDouble());
                r = Math.max(0, Math.min(maxRows - 1, r));
                c = Math.max(0, Math.min(maxColumns - 1, c));
            }
        }

        int currentR = startRows[index];
        int currentC = startColumns[index];

        int currentError = calculateDeltaError(index, currentR, currentC, r, c);

        move(index, r, c, currentR, currentC);

        int newError = calculateDeltaError(index, currentR, currentC, r, c);

        int newMaxRows = maxRows;
        if (r == currentR) {
        } else if (r < currentR) {
            if (currentR + numRows[index] == maxRows) {
                newMaxRows = calculateMaxRows();
            }
        } else {
            if (r + numRows[index] > maxRows) {
                newMaxRows = r + numRows[index];
            }
        }

        int newMaxColumns = maxColumns;
        if (c == currentC) {
        } else if (c < currentC) {
            if (currentC + numColumns[index] == maxColumns) {
                newMaxColumns = calculateMaxColumns();
            }
        } else {
            if (c + numColumns[index] > maxColumns) {
                newMaxColumns = c + numColumns[index];
            }
        }

        double compressionScore = newMaxRows * newMaxColumns * 1.0 / totalArea;
        double lossinessScore = (errors - currentError + newError) * 1.0 / (12.5 * totalArea);
        double newScore = compressionScore * P + lossinessScore * (1.0 - P);
        double deltaScore = newScore - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            errors = errors - currentError + newError;
            maxRows = newMaxRows;
            maxColumns = newMaxColumns;
            saveBest();
        } else {
            move(index, currentR, currentC, r, c);
        }
    }

    private void slide() {
        int delta = rng.nextDouble() < 0.5 ? 1 : 2;

        if (rng.nextDouble() < 0.5) {
            int r = (int) (maxRows * rng.nextDouble());

            if (rng.nextDouble() < 0.5) {

                for (int i2 = 0; i2 < N; i2++) {
                    if (startRows[i2] > r) {
                        if (startRows[i2] + delta + numRows[i2] > compressed.length) {
                            return;
                        }
                    }
                }

                list.clear();
                for (int i = 0; i < N; i++) {
                    if (startRows[i] > r) {
                        list.add(i);
                        move(i, startRows[i] + delta, startColumns[i], startRows[i], startColumns[i]);
                    }
                }

                double deltaScore = calculateScore() - score;
                if (sa.accept(deltaScore)) {
                    score += deltaScore;
                    errors = calculateErrors();
                    maxRows = calculateMaxRows();
                    maxColumns = calculateMaxColumns();
                    saveBest();
                } else {
                    for (int li = 0; li < list.size(); li++) {
                        int i = list.get(li);
                        move(i, startRows[i] - delta, startColumns[i], startRows[i], startColumns[i]);
                    }
                }
            } else {
                for (int i2 = 0; i2 < N; i2++) {
                    if (startRows[i2] > r) {
                        if (startRows[i2] - delta < 0) {
                            return;
                        }
                    }
                }

                list.clear();
                for (int i = 0; i < N; i++) {
                    if (startRows[i] > r) {
                        list.add(i);
                        move(i, startRows[i] - delta, startColumns[i], startRows[i], startColumns[i]);
                    }
                }

                double deltaScore = calculateScore() - score;
                if (sa.accept(deltaScore)) {
                    score += deltaScore;
                    errors = calculateErrors();
                    maxRows = calculateMaxRows();
                    maxColumns = calculateMaxColumns();
                    saveBest();
                } else {
                    for (int li = 0; li < list.size(); li++) {
                        int i = list.get(li);
                        move(i, startRows[i] + delta, startColumns[i], startRows[i], startColumns[i]);
                    }
                }
            }
        } else {
            int c = (int) (maxColumns * rng.nextDouble());

            if (rng.nextDouble() < 0.5) {
                for (int i2 = 0; i2 < N; i2++) {
                    if (startColumns[i2] > c) {
                        if (startColumns[i2] + delta + numColumns[i2] > compressed[0].length) {
                            return;
                        }
                    }
                }

                list.clear();
                for (int i = 0; i < N; i++) {
                    if (startColumns[i] > c) {
                        list.add(i);
                        move(i, startRows[i], startColumns[i] + delta, startRows[i], startColumns[i]);
                    }
                }

                double deltaScore = calculateScore() - score;
                if (sa.accept(deltaScore)) {
                    score += deltaScore;
                    errors = calculateErrors();
                    maxRows = calculateMaxRows();
                    maxColumns = calculateMaxColumns();
                    saveBest();
                } else {
                    for (int li = 0; li < list.size(); li++) {
                        int i = list.get(li);
                        move(i, startRows[i], startColumns[i] - delta, startRows[i], startColumns[i]);
                    }
                }
            } else {
                for (int i2 = 0; i2 < N; i2++) {
                    if (startColumns[i2] > c) {
                        if (startColumns[i2] - delta < 0) {
                            return;
                        }
                    }
                }

                list.clear();
                for (int i = 0; i < N; i++) {
                    if (startColumns[i] > c) {
                        list.add(i);
                        move(i, startRows[i], startColumns[i] - delta, startRows[i], startColumns[i]);
                    }
                }

                double deltaScore = calculateScore() - score;
                if (sa.accept(deltaScore)) {
                    score += deltaScore;
                    errors = calculateErrors();
                    maxRows = calculateMaxRows();
                    maxColumns = calculateMaxColumns();
                    saveBest();
                } else {
                    for (int li = 0; li < list.size(); li++) {
                        int i = list.get(li);
                        move(i, startRows[i], startColumns[i] + delta, startRows[i], startColumns[i]);
                    }
                }
            }
        }

    }

    private void swap() {
        int index = (int) (N * rng.nextDouble());
        int index2 = index;
        while (index2 == index) {
            index2 = (int) (N * rng.nextDouble());
        }

        int r1 = startRows[index];
        int c1 = startColumns[index];
        int r2 = startRows[index2];
        int c2 = startColumns[index2];
        if (r1 + numRows[index2] > compressed.length || c1 + numColumns[index2] > compressed[0].length || r2 + numRows[index] > compressed.length || c2 + numColumns[index] > compressed[0].length) {
            return;
        }
        int currentError = calculateDeltaError(index, index2, r1, c1, r2, c2);

        move(index, r2, c2, r1, c1);
        move(index2, r1, c1, r2, c2);

        int newError = calculateDeltaError(index, index2, r1, c1, r2, c2);

        int newMaxRows = maxRows;
        if (startRows[index] + numRows[index] > maxRows) {
            newMaxRows = startRows[index] + numRows[index];
        } else if (startRows[index2] + numRows[index2] > maxRows) {
            newMaxRows = startRows[index2] + numRows[index2];
        } else {
            if (startRows[index2] + numRows[index] == maxRows || startRows[index] + numRows[index2] == maxRows) {
                newMaxRows = calculateMaxRows();
            }
        }

        int newMaxColumns = maxColumns;
        if (startColumns[index] + numColumns[index] > maxColumns) {
            newMaxColumns = startColumns[index] + numColumns[index];
        } else if (startColumns[index2] + numColumns[index2] > maxColumns) {
            newMaxColumns = startColumns[index2] + numColumns[index2];
        } else {
            if (startColumns[index2] + numColumns[index] == maxColumns || startColumns[index] + numColumns[index2] == maxColumns) {
                newMaxColumns = calculateMaxColumns();
            }
        }

        double compressionScore = newMaxRows * newMaxColumns * 1.0 / totalArea;
        double lossinessScore = (errors - currentError + newError) * 1.0 / (12.5 * totalArea);
        double newScore = compressionScore * P + lossinessScore * (1.0 - P);
        double deltaScore = newScore - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            errors = errors - currentError + newError;
            maxRows = newMaxRows;
            maxColumns = newMaxColumns;
            saveBest();
        } else {
            move(index, r1, c1, r2, c2);
            move(index2, r2, c2, r1, c1);
        }
    }

    private void move(int index, int r, int c, int currentR, int currentC) {
        startRows[index] = r;
        startColumns[index] = c;
        remove(index, currentR, currentC);
        add(index, r, c);
    }

    private void add(int i, int r, int c) {
        int[][] grid = grids[i];
        for (int dr = 0; dr < numRows[i]; dr++) {
            for (int dc = 0; dc < numColumns[i]; dc++) {
                compressed[r + dr][c + dc].add(grid[dr][dc]);
            }
        }
    }

    private void remove(int i, int r, int c) {
        int[][] grid = grids[i];
        for (int dr = 0; dr < numRows[i]; dr++) {
            for (int dc = 0; dc < numColumns[i]; dc++) {
                compressed[r + dr][c + dc].removeValue(grid[dr][dc]);
            }
        }
    }

    private double calculateScore() {
        double compressionScore = calculateMaxRows() * calculateMaxColumns() * 1.0 / totalArea;
        int errors = calculateErrors();
        double lossinessScore = errors * 1.0 / (12.5 * totalArea);
        return compressionScore * P + lossinessScore * (1.0 - P);
    }

    private int calculateErrors() {
        int errors = 0;
        for (int i = 0; i < N; i++) {
            int[][] grid = grids[i];
            for (int r = 0; r < grid.length; r++) {
                for (int c = 0; c < grid[r].length; c++) {
                    errors += Math.abs(median(compressed[startRows[i] + r][startColumns[i] + c]) - grid[r][c]);
                }
            }
        }
        return errors;
    }

    private InitializedBooleanArray_v2 used;

    private int calculateDeltaError(int index, int r1, int c1, int r2, int c2) {
        used.clear();
        int errors = 0;
        int C = compressed[0].length;
        for (int r = r1; r < r1 + numRows[index]; r++) {
            for (int c = c1; c < c1 + numColumns[index]; c++) {
                used.set(r * C + c, true);

                int median = median(compressed[r][c]);
                for (int i = 0; i < compressed[r][c].size(); i++) {
                    errors += Math.abs(median - compressed[r][c].get(i));
                }
            }
        }
        for (int r = r2; r < r2 + numRows[index]; r++) {
            for (int c = c2; c < c2 + numColumns[index]; c++) {
                if (used.get(r * C + c)) {
                    continue;
                }
                int median = median(compressed[r][c]);
                for (int i = 0; i < compressed[r][c].size(); i++) {
                    errors += Math.abs(median - compressed[r][c].get(i));
                }
            }
        }
        return errors;
    }

    private int calculateDeltaError(int index, int index2, int r1, int c1, int r2, int c2) {
        used.clear();
        int errors = 0;
        int C = compressed[0].length;
        for (int r = r1; r < r1 + numRows[index]; r++) {
            for (int c = c1; c < c1 + numColumns[index]; c++) {
                used.set(r * C + c, true);

                int median = median(compressed[r][c]);
                for (int i = 0; i < compressed[r][c].size(); i++) {
                    errors += Math.abs(median - compressed[r][c].get(i));
                }
            }
        }
        for (int r = r2; r < r2 + numRows[index]; r++) {
            for (int c = c2; c < c2 + numColumns[index]; c++) {
                if (used.get(r * C + c)) {
                    continue;
                }
                used.set(r * C + c, true);
                int median = median(compressed[r][c]);
                for (int i = 0; i < compressed[r][c].size(); i++) {
                    errors += Math.abs(median - compressed[r][c].get(i));
                }
            }
        }

        for (int r = r1; r < r1 + numRows[index2]; r++) {
            for (int c = c1; c < c1 + numColumns[index2]; c++) {
                if (used.get(r * C + c)) {
                    continue;
                }
                used.set(r * C + c, true);

                int median = median(compressed[r][c]);
                for (int i = 0; i < compressed[r][c].size(); i++) {
                    errors += Math.abs(median - compressed[r][c].get(i));
                }
            }
        }
        for (int r = r2; r < r2 + numRows[index2]; r++) {
            for (int c = c2; c < c2 + numColumns[index2]; c++) {
                if (used.get(r * C + c)) {
                    continue;
                }

                int median = median(compressed[r][c]);
                for (int i = 0; i < compressed[r][c].size(); i++) {
                    errors += Math.abs(median - compressed[r][c].get(i));
                }
            }
        }
        return errors;
    }

    private void saveBest() {
        if (score < bestScore) {
            bestScore = score;
            for (int i = 0; i < N; i++) {
                bestStartRows[i] = startRows[i];
                bestStartColumns[i] = startColumns[i];
            }
            for (int r = 0; r < compressed.length; r++) {
                for (int c = 0; c < compressed[r].length; c++) {
                    bestCompressed[r][c].clear();
                    for (int i = 0; i < compressed[r][c].size(); i++) {
                        bestCompressed[r][c].add(compressed[r][c].get(i));
                    }
                }
            }
        }
    }

    private void loadBest() {
        score = bestScore;
        for (int i = 0; i < N; i++) {
            startRows[i] = bestStartRows[i];
            startColumns[i] = bestStartColumns[i];
        }
        for (int r = 0; r < bestCompressed.length; r++) {
            for (int c = 0; c < bestCompressed[r].length; c++) {
                compressed[r][c].clear();
                for (int i = 0; i < bestCompressed[r][c].size(); i++) {
                    compressed[r][c].add(bestCompressed[r][c].get(i));
                }
            }
        }
    }

    private String[] makeSolution() {
        int numRows = calculateMaxRows();
        int numColumns = calculateMaxColumns();
        Utils.debug("numRows", numRows, "numColumns", numColumns);

        String[] res = new String[numRows + N];
        for (int r = 0; r < numRows; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < numColumns; c++) {
                sb.append((char) ('A' + median(compressed[r][c])));
            }
            res[r] = sb.toString();
        }
        for (int i = 0; i < N; i++) {
            int r = numRows + i;
            res[r] = startRows[i] + " " + startColumns[i];
        }
        return res;
    }

    private int calculateMaxRows() {
        int numRows = 0;
        for (int i = 0; i < N; i++) {
            int endRows = startRows[i] + this.numRows[i];
            if (endRows > numRows) {
                numRows = endRows;
            }
        }
        return numRows;
    }

    private int calculateMaxColumns() {
        int numColumns = 0;
        for (int i = 0; i < N; i++) {
            int endColumns = startColumns[i] + this.numColumns[i];
            if (endColumns > numColumns) {
                numColumns = endColumns;
            }
        }
        return numColumns;
    }

    private int median(IntListSorted list) {
        if (list.size() == 0) {
            return 0;
        }
        int k = list.size() >>> 1;
        if ((list.size() & 1) == 1) {
            return list.get(k);
        } else {
            return (list.get(k - 1) + list.get(k)) >>> 1;
        }
    }

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

            double P = Double.parseDouble(br.readLine());
            int N = Integer.parseInt(br.readLine());

            String[][] grids = new String[N][];

            for (int i = 0; i < N; i++) {
                int H = Integer.parseInt(br.readLine());
                grids[i] = new String[H];
                for (int k = 0; k < H; k++)
                    grids[i][k] = br.readLine();
            }
            Lossy2dCompression prog = new Lossy2dCompression();
            String[] ret = prog.findSolution(P, N, grids);

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

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 double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

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

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

}

class SAState {

    public static final boolean useTime = true;

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

    public double startRange = 0;
    public double endRange = 0;
    public double range = startRange;

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

    private double minAbsDeltaScore;
    private double maxAbsDeltaScore;
    private MeanHelper helper = new MeanHelper();

    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;

        minAbsDeltaScore = 1e99;
        maxAbsDeltaScore = 1e-99;
        helper.clear();

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

        update();
        lastAcceptTemperature = inverseTemperature;
    }

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

    public boolean useMean = true;
    public boolean useMax = !true;
    public double startRate = 0.01;
    public double endRate = 0.01;
    public boolean useExp = !true;

    public void updateStartTemperature() {
        if (useMean) {
            double d = helper.mean(maxAbsDeltaScore);
            d = d > 0 ? d : maxAbsDeltaScore;
            startTemperature = (-1.0 * d) / Math.log(startRate);
        } else if (useMax) {
            startTemperature = (-1.0 * maxAbsDeltaScore) / Math.log(startRate);
        } else {
            startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(startRate);
        }
    }

    public void updateEndTemperature() {
        endTemperature = (-1.0 * minAbsDeltaScore) / Math.log(endRate);
    }

    public void updateTemperature() {
        if (useExp) {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double startX = Math.log(startY);
            double endX = Math.log(endY);
            double xStartToEnd = interpolate(startX, endX, time0to1);
            double temperature = Math.exp(xStartToEnd);

            inverseTemperature = 1.0 / temperature;
        } else {
            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 ? Lossy2dCompression.watch.getSecond() : numIterations;
    }

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

    public boolean accept(double deltaScore) {
        double abs = Math.abs(deltaScore);
        if (abs > 1e-9) {
            helper.add(deltaScore);
            minAbsDeltaScore = Math.min(minAbsDeltaScore, abs);
            maxAbsDeltaScore = Math.max(maxAbsDeltaScore, abs);
        }
        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;

        if (deltaScore * inverseTemperature < -10) {
            return false;
        }
        if (log[Lossy2dCompression.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
            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;

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

}

class MeanHelper {
    private double max;
    private double min;
    private double sum;
    private double sumSquared;
    private double sumCubed;
    private double sumFourth;
    private int count;

    public MeanHelper() {
        clear();
    }

    public void add(double value) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value;
        double valueSquared = value * value;
        sumSquared += valueSquared;
        sumCubed += valueSquared * value;
        sumFourth += valueSquared * valueSquared;
        count++;
    }

    public void add(double value, double number) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value * number;
        double valueSquared = value * value;
        sumSquared += valueSquared * number;
        sumCubed += valueSquared * value * number;
        sumFourth += valueSquared * valueSquared * number;
        count += number;
    }

    public double kurtosis(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
    }

    public double skewness(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
    }

    public double mean() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sum / count;
    }

    public double mean(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sum / count;
    }

    public double sumOfSquaredError() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sumSquared - sum * sum / count;
    }

    public double sumOfSquaredError(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sumSquared - sum * sum / count;
    }

    public double variance() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double variance(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double unbiasedVariance() {
        if (count - 1 == 0) {
            throw new AssertionError();
        }
        return (count * variance()) / (count - 1);
    }

    private double unbiasedVariance(double defaultValue) {
        if (count - 1 == 0) {
            return defaultValue;
        }
        return (count * variance()) / (count - 1);
    }

    public double standardDeviation() {
        return Math.sqrt(variance());
    }

    public double standardDeviation(double defaultValue) {
        return Math.sqrt(variance(defaultValue));
    }

    public double unbiasedStandardDeviation() {
        return Math.sqrt(unbiasedVariance());
    }

    public double unbiasedStandardDeviation(double defaultValue) {
        return Math.sqrt(unbiasedVariance(defaultValue));
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void clear() {
        max = Double.NEGATIVE_INFINITY;
        min = Double.POSITIVE_INFINITY;
        sum = 0;
        sumSquared = 0;
        sumCubed = 0;
        sumFourth = 0;
        count = 0;
    }

    public double max() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return max;
    }

    public double max(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return max;
    }

    public double min() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return min;
    }

    public double min(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return min;
    }

    public int count() {
        return count;
    }

    public double sum() {
        return sum;
    }

    public double sumSquared() {
        return sumSquared;
    }
}

class InitializedBooleanArray_v2 {
    private boolean[] values;
    private int[] epoch;
    private int current_epoch;

    public void init(int size) {
        current_epoch = 0;
        values = new boolean[size];
        epoch = new int[size];
    }

    public void clear() {
        current_epoch++;
    }

    public boolean get(int at) {
        assert (at < values.length);
        if (epoch[at] != current_epoch) {
            epoch[at] = current_epoch;
            values[at] = false;
        }
        return values[at];
    }

    public void set(int at, boolean value) {
        assert (at < values.length);
        epoch[at] = current_epoch;
        values[at] = value;
    }
}

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

    public IntListSorted(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;
        for (int i = size - 1; i >= 1; i--) {
            if (values[i - 1] <= values[i]) {
                break;
            }
            swap(values, i - 1, i);
        }
        return true;
    }

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

    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 get(int index) {
        return values[index];
    }

    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) {
        int index = Arrays.binarySearch(values, 0, size, value);
        if (index < 0) {
            return EMPTY;
        }
        int index0 = index;
        for (;;) {
            index = Arrays.binarySearch(values, 0, index0, value);
            if (index < 0) {
                break;
            }
            index0 = index;
        }
        return index0;
    }

}

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

}