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

  • 近傍 : 隣接する Polyomino を合併して分ける
    • 分け方は、ランダムな点から幅優先やダイクストラを使いました。
  • 温度 : スコアの桁数が大きいので、実行時に自動調節した。実行時に、スコアの差の絶対値の最大値、最小値を保持して、
    開始時の温度 : 0.1 * (-1.0 * スコアの差の絶対値の最大値) / log(0.01)
    • (-1.0 * スコアの差の絶対値の最大値)は、"最大の改悪をした時のスコアの差"です。
    • exp(スコアの差/温度) にこの温度の 0.1 * 以外の部分を代入すると、
       = exp(スコアの差/((-1.0 * スコアの差の絶対値の最大値) / log(0.01)))
       = exp(スコアの差/("最大の改悪をした時のスコアの差" / log(0.01)))
      ここで、スコアの差を"最大の改悪をした時のスコアの差"に選ぶと、
       = exp(log(0.01))
       = 0.01
      をえる。(-1.0 * スコアの差の絶対値の最大値) / log(0.01)は、最大の改悪をした時に 1% の確率で受理される温度です。これは去年 Graph Golf で中尾さんが使っていた温度の決め方です。すごくきれいな決め方なんですが、実際は調整がいります。
    終了時の温度 : 100 * (-1.0 * スコアの差の絶対値の最小値) / log(0.01)
    という感じで、定期的に更新していた。

  • Example test
    1 : 1582630
    2 : 122527345
    3 : 39108993
    4 : 69306490
    5 : 8691034
    6 : 35585746
    7 : 76784835
    8 : 7778108
    9 : 50994052
    10 : 100944964


みんな99点で、96点だった。どうやるんだろう?試してないのは
  • Polyomino を列挙して、重なったらペナルティーの焼きなまし法

かなー?



source code

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

public class PolyominoCovering {
    private final static int[] dr = { -1, 0, 0, 1, };
    private final static int[] dc = { 0, -1, 1, 0, };
    private int N;
    private int[][] numbers;
    private int[] sizeToMaxNum;
    private int numPolyominos;
    private int[][] idToCells;
    private int[][] cellToId;
    private long[] idToScore;

    private int[][] bestCellToId;

    private long score;
    private long bestScore = (long) -1e99;

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

    public int[] findSolution(int N, int[] grid, int[] tiles) {
        init(N, grid, tiles);
        solve();
        return makeSolution();
    }

    private void init(int n, int[] grid, int[] tiles) {
        this.N = n;
        this.numbers = new int[N][N];
        for (int i = 0; i < grid.length; i++) {
            numbers[i / N][i % N] = grid[i];
        }
        this.sizeToMaxNum = new int[8];
        for (int i = 0; i < tiles.length; i++) {
            this.sizeToMaxNum[i + 2] = tiles[i];
        }
        numPolyominos = 1;
        int numCells = 0;
        for (int size = 3; size <= 7; size++) {
            numPolyominos += sizeToMaxNum[size];
            numCells += size * sizeToMaxNum[size];
        }
        Utils.debug("N", N, "tiles", tiles, "empty", N * N - numCells);

        idToCells = new int[numPolyominos][];
        for (int id = 0, size = 3; id < numPolyominos;) {
            if (id == 0) {
                idToCells[id++] = new int[N * N - numCells];
                continue;
            }
            for (int i = 0; i < sizeToMaxNum[size]; i++) {
                idToCells[id++] = new int[size];
            }
            size++;
        }
        idToScore = new long[numPolyominos];

        cellToId = new int[N][N];
        bestCellToId = new int[N][N];

        merge = new IntSet(N * N);
        cells = new IntSet(N * N);
        cells2 = new IntSet(N * N);

        queue = new IntQueue(N * N);
        set = new IntSet(N * N);
    }

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

    private void greedy() {
        for (int r = 0; r < N; r++) {
            Arrays.fill(cellToId[r], -1);
        }
        boolean[] used = new boolean[numPolyominos];
        for (int i = 0; i < numPolyominos;) {
            int id = 0 + (int) (numPolyominos * rng.nextDouble());
            if (used[id]) {
                continue;
            }

            used[id] = true;
            outToIn(id);

            i++;
        }
        score = 0;
        for (int id = 0; id < numPolyominos; id++) {
            if (id == 0) {
                idToScore[id] = -1000 * idToCells[id].length;
                score += idToScore[id];
                continue;
            }
            long partScore = 1;
            int[] cells = idToCells[id];
            for (int i = 0; i < cells.length; i++) {
                int cell = cells[i];
                int r = cell / N;
                int c = cell % N;
                partScore *= numbers[r][c];
            }
            idToScore[id] = partScore;
            score += idToScore[id];
        }
        saveBest();
        Utils.debug("greedy", "score", score, "time", watch.getSecondString());
    }

    private int r0 = 0;
    private int c0 = 0;
    private int d0 = 2;

    private void outToIn(int id) {
        for (int i = 0; i < idToCells[id].length; i++) {
            idToCells[id][i] = r0 * N + c0;
            cellToId[r0][c0] = id;

            int nr = r0 + dr[d0];
            int nc = c0 + dc[d0];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N || cellToId[nr][nc] != -1) {
                if (d0 == 0) {
                    d0 = 2;
                } else if (d0 == 1) {
                    d0 = 0;
                } else if (d0 == 2) {
                    d0 = 3;
                } else if (d0 == 3) {
                    d0 = 1;
                }
            }
            r0 += dr[d0];
            c0 += dc[d0];
        }
    }

    private void SA() {
        double second = Math.ceil(watch.getSecond());
        sa.init();
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 10) - 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("%d", score), String.format("%d", 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("%d", score), String.format("%d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }

            }

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

    private void mutate() {
        double random = 1 * rng.nextDouble();
        if (random < 1) {
            mergeAndSplit();
        }
    }

    private IntSet merge;
    private IntSet cells;
    private IntSet cells2;

    private void mergeAndSplit() {
        int r = (int) (N * rng.nextDouble());
        int c = (int) (N * rng.nextDouble());

        int direction = (int) (dr.length * rng.nextDouble());
        int nr = r + dr[direction];
        int nc = c + dc[direction];
        if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
            return;
        }

        int id = cellToId[r][c];
        int id2 = cellToId[nr][nc];
        if (id2 == id) {
            return;
        }

        if (id == 0 || id2 == 0) {
            if (id == 0) {
                int swap = id;
                id = id2;
                id2 = swap;
            }
            assert id != 0;
            assert id2 == 0;

            merge.clear();
            for (int i = 0; i < idToCells[id].length; i++) {
                merge.add(idToCells[id][i]);
            }
            assert merge.size() == idToCells[id].length;
            for (int i = 0; i < idToCells[id2].length; i++) {
                merge.add(idToCells[id2][i]);
            }
            assert merge.size() == idToCells[id].length + idToCells[id2].length;
            search4(merge, idToCells[id].length);
            if (cells.size() != idToCells[id].length) {
                return;
            }
            assert cells.size() == idToCells[id].length : Utils.toString(cells.size(), idToCells[id].length, idToCells[id2].length);

            cells2.clear();
            for (int i = 0; i < merge.size(); i++) {
                if (cells.contains(merge.get(i))) {
                    continue;
                }
                cells2.add(merge.get(i));
            }
            assert cells2.size() == idToCells[id2].length;
        } else {
            merge.clear();
            for (int i = 0; i < idToCells[id].length; i++) {
                merge.add(idToCells[id][i]);
            }
            assert merge.size() == idToCells[id].length;
            for (int i = 0; i < idToCells[id2].length; i++) {
                merge.add(idToCells[id2][i]);
            }
            assert merge.size() == idToCells[id].length + idToCells[id2].length;

            if (idToCells[id].length > idToCells[id2].length) {
                int swap = id;
                id = id2;
                id2 = swap;
            }
            bfs2(merge, idToCells[id].length);
            if (cells.size() != idToCells[id].length) {
                return;
            }
            assert cells.size() == idToCells[id].length : Utils.toString(cells.size(), idToCells[id].length, idToCells[id2].length);

            cells2.clear();
            for (int i = 0; i < merge.size(); i++) {
                if (cells.contains(merge.get(i))) {
                    continue;
                }
                cells2.add(merge.get(i));
            }
            assert cells2.size() == idToCells[id2].length;

            if (!isValid(cells2)) {
                return;
            }
        }

        long currentPartScore = idToScore[id] + idToScore[id2];
        long newScore1 = id == 0 ? -1000 * cells.size() : calculateScore(cells);
        long newScore2 = id2 == 0 ? -1000 * cells2.size() : calculateScore(cells2);
        long newPartScore = newScore1 + newScore2;
        if (sa.accept(newPartScore - currentPartScore)) {
            score += newPartScore - currentPartScore;

            for (int i = 0; i < cells.size(); i++) {
                int cell = cells.get(i);
                idToCells[id][i] = cell;
                cellToId[r(cell)][c(cell)] = id;
            }
            for (int i = 0; i < cells2.size(); i++) {
                int cell = cells2.get(i);
                idToCells[id2][i] = cell;
                cellToId[r(cell)][c(cell)] = id2;
            }

            idToScore[id] = newScore1;
            idToScore[id2] = newScore2;

            saveBest();
        }
    }

    private long calculateScore(IntSet cells) {
        long score = 1;
        for (int i = 0; i < cells.size(); i++) {
            int cell = cells.get(i);
            score *= numbers[r(cell)][c(cell)];
        }
        return score;
    }

    private boolean isValid(IntSet cells) {
        return bfs(cells);
    }

    private IntSet set;

    private IntSet bfs2(IntSet merge, int maxSize) {
        cells.clear();
        set.clear();
        for (int i = 0; i < merge.size(); i++) {
            used[i] = false;
        }
        {
            int cell = merge.get((int) (merge.size() * rng.nextDouble()));
            set.add(cell);
            used[merge.indexOf(cell)] = true;
        }
        for (int loop = 0; loop < maxSize; loop++) {
            if (set.size() == 0) {
                cells.clear();
                return cells;
            }
            assert set.size() > 0;
            int cell = set.get((int) (set.size() * rng.nextDouble()));
            set.removeValue(cell);
            int r = r(cell);
            int c = c(cell);
            cells.add(cell);
            for (int d = 0; d < dr.length; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    continue;
                }
                int ncell = nr * N + nc;
                int index = merge.indexOf(ncell);
                if (index == -1) {
                    continue;
                }
                if (used[index]) {
                    continue;
                }
                used[index] = true;
                set.add(ncell);
            }
        }
        return cells;
    }

    class Node implements Comparable<Node> {
        Node parent;
        int cell;
        int score;
        int size;

        public Node(Node parent, int cell, int score, int size) {
            super();
            this.parent = parent;
            this.cell = cell;
            this.score = score;
            this.size = size;
        }

        @Override
        public int compareTo(Node o) {
            if (Math.abs(score) > Math.abs(o.score)) {
                return -1;
            }
            if (Math.abs(score) < Math.abs(o.score)) {
                return 1;
            }
            return 0;
        }

    }

    class Node2 implements Comparable<Node2> {
        Node2 parent;
        int cell;
        int score;
        int size;

        public Node2(Node2 parent, int cell, int score, int size) {
            super();
            this.parent = parent;
            this.cell = cell;
            this.score = score;
            this.size = size;
        }

        @Override
        public int compareTo(Node2 o) {
            if (Math.abs(score) < Math.abs(o.score)) {
                return -1;
            }
            if (Math.abs(score) > Math.abs(o.score)) {
                return 1;
            }
            return 0;
        }

    }

    private IntSet search4(IntSet merge, int maxSize) {
        cells.clear();
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < merge.size(); i++) {
            used[i] = false;
        }
        {
            int cell = merge.get((int) (merge.size() * rng.nextDouble()));
            pq.add(new Node(null, cell, numbers[r(cell)][c(cell)], 1));
            used[merge.indexOf(cell)] = true;
        }
        for (; !pq.isEmpty();) {
            Node node = pq.poll();
            int cell = node.cell;
            int r = r(cell);
            int c = c(cell);
            cells.add(cell);
            if (cells.size() == maxSize) {
                break;
            }
            for (int d = 0; d < dr.length; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    continue;
                }
                int ncell = nr * N + nc;
                int index = merge.indexOf(ncell);
                if (index == -1) {
                    continue;
                }
                if (node.size + 1 == maxSize) {
                    if (node.score * numbers[nr][nc] < 0) {
                        continue;
                    }
                }
                if (used[index]) {
                    continue;
                }
                used[index] = true;
                pq.add(new Node(node, ncell, node.score * numbers[nr][nc], node.size + 1));
            }
        }

        return cells;
    }

    private IntQueue queue;
    boolean[] used = new boolean[50 * 50];

    private boolean bfs(IntSet cells) {
        queue.clear();
        for (int i = 0; i < cells.size(); i++) {
            used[i] = false;
        }
        {
            int cell = cells.get(0);
            queue.add(cell);
            assert cells.indexOf(cell) == 0;
            used[cells.indexOf(cell)] = true;
        }
        for (; !queue.isEmpty();) {
            int cell = queue.poll();
            int r = r(cell);
            int c = c(cell);

            for (int d = 0; d < dr.length; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    continue;
                }
                int ncell = nr * N + nc;
                int index = cells.indexOf(ncell);
                if (index == -1) {
                    continue;
                }
                if (used[index]) {
                    continue;
                }
                used[index] = true;
                queue.add(ncell);
            }
        }
        for (int i = 0; i < cells.size(); i++) {
            if (!used[i]) {
                return false;
            }
        }
        return true;
    }

    private int r(int cell) {
        return cell / N;
    }

    private int c(int cell) {
        return cell % N;
    }

    private int[] makeSolution() {
        int[] solution = new int[N * N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                solution[r * N + c] = cellToId[r][c] == 0 ? -1 : cellToId[r][c];
            }
        }
        return solution;
    }

    private void saveBest() {
        if (score > bestScore) {
            bestScore = score;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    bestCellToId[r][c] = cellToId[r][c];
                }
            }
        }
    }

    private void loadBest() {
        score = bestScore;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                cellToId[r][c] = bestCellToId[r][c];
            }
        }
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            int[] grid = new int[N * N];
            for (int i = 0; i < N * N; i++)
                grid[i] = Integer.parseInt(br.readLine());
            int[] tiles = new int[6];
            for (int i = 0; i < 6; i++)
                tiles[i] = Integer.parseInt(br.readLine());

            PolyominoCovering pc = new PolyominoCovering();
            int[] ret = pc.findSolution(N, grid, tiles);

            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 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 = 0;
    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 ? PolyominoCovering.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 = 0.1 * (-1.0 * maxAbsDeltaScore) / Math.log(startRate);
        } else {
            startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(startRate);
        }
    }

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

    public void updateTemperature() {
        updateStartTemperature();
        updateEndTemperature();
        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 ? PolyominoCovering.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 acceptB(deltaScore);
    }

    public boolean acceptB(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[PolyominoCovering.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[PolyominoCovering.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

}

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

}

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

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

    public void clear() {
        current = 0;
        size = 0;
    }

    public int size() {
        return size - current;
    }

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

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

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

    public int poll() {
        return values[current++];
    }

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

    public boolean remove(int value) {
        int index = indexOf(value);
        if (index == EMPTY) {
            return false;
        }
        for (int i = index; i < size; i++) {
            values[i] = values[i + 1];
        }
        size--;
        return true;
    }
}

class IntSet {
    private static final int EMPTY = -1;
    private int size;
    private int[] indexToValue;
    private int[] valueToIndex;

    public IntSet(int capacity) {
        this.size = 0;
        indexToValue = new int[capacity];
        valueToIndex = new int[capacity];
        Arrays.fill(valueToIndex, EMPTY);
    }

    public boolean add(int value) {
        if (valueToIndex[value] != EMPTY) {
            return false;
        }
        indexToValue[size] = value;
        valueToIndex[indexToValue[size]] = size;
        size++;
        return true;
    }

    public boolean remove(int index) {
        if (size == 0) {
            return false;
        }
        assert index < size;
        swap(index, size - 1);
        valueToIndex[indexToValue[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[index];
        indexToValue[index] = indexToValue[index2];
        indexToValue[index2] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[index2]] = index2;

    }

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

        int swap = valueToIndex[index];
        valueToIndex[index] = valueToIndex[index2];
        valueToIndex[index2] = swap;

        indexToValue[valueToIndex[index]] = index;
        indexToValue[valueToIndex[index2]] = index2;

    }

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

    public int indexOf(int value) {
        return valueToIndex[value];
    }

    public int size() {
        return size;
    }

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

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

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

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(indexToValue, size()));
    }
}

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