EvbCFfp1XB

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

September 2019



Approach 2つの部分に分けました。1つ目は、対戦成績から skill を予想するところ。2つ目は、予想した skill でチームの強さを最適化するところ。予想するのにランダムフォレスト、最適化に焼きなまし法を使いました。

  • ランダムフォレスト
    • 特徴量 : 対戦成績をソートしただけ
    • 特徴量のサンプル数 : 32 * competitorの数分、実行時に生成する
    • 決定木の数 : 32
    • 32本の決定木の平均で skill を予想して、標準偏差で skill の標準偏差を予想した。
      スコアを計算するときに、 maxStrength = max(maxStrength, 予想したskill + 0.01*予想したskill の標準偏差), minStrength = min(minStrength, 予想したskill - 0.01*予想したskill の標準偏差) という風に計算して、ばらつきも含めて最適化できるようにした。もしかすると、ばらつきも含めて最適化しないほうが、偶然ハイスコアが出て、リーダーボード上ではよかったのかもと思っています。
  • 焼きなまし法
    • 近傍1 : competitor の移動
    • 近傍2 : competitor の交換

source code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.StandardOpenOption;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

public class ContestOrganizer {
    private int M;
    private int N;
    private int contests;
    private int[][] wins;

    private double[] skill;
    private double[] skillSD;
    private double[] strength;
    private double[] strengthSD;

    private double score;
    private IntList[] teams;

    private double bestScore;
    private IntList[] bestTeams;

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

    public String[] makeTeams(int M, String[] wins) {
        init(M, wins);
        predictSkill(32);
        minimizeDiff();
        return makeSolution();
    }

    private void init(int M, String[] wins) {
        this.M = M;
        this.N = wins.length;
        this.wins = new int[N][N];
        for (int r = 0; r < N; r++) {
            String[] split = wins[r].split(" ");
            for (int c = 0; c < N; c++) {
                this.wins[r][c] = Integer.parseInt(split[c]);
            }
        }
        this.contests = this.wins[0][1] + this.wins[1][0];
        teams = new IntList[M];
        for (int i = 0; i < M; i++) {
            teams[i] = new IntList(N);
        }
        bestTeams = new IntList[M];
        for (int i = 0; i < M; i++) {
            bestTeams[i] = new IntList(N);
        }
        temp = new int[N];
        strength = new double[M];
        strengthSD = new double[M];
        Utils.debug("N", N, "M", M, "contests", this.contests);
    }

    private void predictSkill(int n) {

        RandomForest rf = new RandomForest(getConfig());
        {
            int numSamples = n * N;

            double[][] features = new double[numSamples][N];
            double[] results = new double[numSamples];

            SecureRandom r1 = null;
            try {
                r1 = SecureRandom.getInstance("SHA1PRNG");
            } catch (NoSuchAlgorithmException e) {
                e.printStackTrace();
            }
            r1.setSeed(System.nanoTime());
            for (int f = 0; f < n; f++) {
                int[] skill = new int[N];
                for (int i = 0; i < N; i++) {
                    skill[i] = r1.nextInt(901) + 100;
                }
                int[][] winCount = new int[N][N];
                for (int i = 0; i < contests; i++) {
                    double[] perf = new double[N];
                    for (int j = 0; j < N; j++)
                        perf[j] = r1.nextDouble() * skill[j];
                    for (int j = 0; j < N; j++)
                        for (int k = 0; k < N; k++)
                            if (perf[j] > perf[k])
                                winCount[j][k]++;
                }

                for (int i = 0; i < N; i++) {
                    Arrays.sort(winCount[i]);
                }
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        features[f * N + i][j] = winCount[i][j] + 1e-9 * rng.nextDouble();
                    }
                    results[f * N + i] = skill[i];
                }
            }
            rf.train(features, results);
        }

        skill = new double[N];
        skillSD = new double[N];
        for (int i = 0; i < N; i++) {
            Arrays.sort(wins[i]);
            double[] testFeatures = new double[N];
            for (int j = 0; j < testFeatures.length; j++) {
                testFeatures[j] = wins[i][j];
            }
            skill[i] = rf.predict(testFeatures);
            assert !Double.isNaN(skill[i]);
            skillSD[i] = 1e-2 * rf.predictSD(testFeatures);
            assert !Double.isNaN(skillSD[i]);
        }

    }

    private RandomForestConfig getConfig() {
        RandomForestConfig config = new RandomForestConfig();
        config.numTThhrreeaadds = 1;
        config.numTrees = 1 << 5;
        config.isClassification = false;
        config.useBootstrapSample = false;
        config.bootstrapSampleRate = 1.0;
        config.useBootstrapFeature = false;
        config.bootstrapFeatureRate = 1.0;
        config.lossFunction = new SumSquaredErrors();
        config.maxDepth = 100;
        config.splitStrategy = new SplitStrategyCareful(10, 1, config.lossFunction);
        config.minSamples = 1;
        config.timeLimitSecond = 1e9;
        return config;
    }

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

    private void greedy() {
        for (int i = 0; i < N; i++) {
            teams[i % M].add(i);
        }
        score = calculateScore();
        bestScore = 1e9;
        saveBest();
        Utils.debug("greedy", "score", score, "time", watch.getSecondString());
    }

    private void SA() {
        double second = Math.ceil(watch.getSecond());
        sa.startTime = 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("%.1f", score), String.format("%.1f", 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("%.1f", score), String.format("%.1f", 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 = 2 * rng.nextDouble();
        if (random < 1) {
            move();
        } else if (random < 2) {
            swap();
        }
    }

    private void move() {
        int t = (int) (M * rng.nextDouble());
        while (teams[t].size() <= 1) {
            t = (int) (M * rng.nextDouble());
        }
        assert teams[t].size() >= 2;
        int index = (int) (teams[t].size() * rng.nextDouble());

        int t2 = t;
        while (t2 == t) {
            t2 = (int) (M * rng.nextDouble());
        }
        assert t2 != t;
        int competitor = teams[t].get(index);

        double newStrength = 0;
        double newStrengthSD = 0;
        for (int i = 0; i < teams[t].size(); i++) {
            if (i == index) {
                continue;
            }
            newStrength += (i < index ? (i + 1) : i) * skill[teams[t].get(i)];
            newStrengthSD += (i < index ? (i + 1) : i) * skillSD[teams[t].get(i)];
        }
        newStrength /= ((teams[t].size()) * (teams[t].size() - 1)) / 2;
        newStrengthSD /= ((teams[t].size()) * (teams[t].size() - 1)) / 2;
        assert !Double.isNaN(newStrength);
        assert !Double.isNaN(newStrengthSD);

        int index2 = index(t2, competitor);
        double newStrength2 = (index2 + 1) * skill[competitor];
        double newStrengthSD2 = (index2 + 1) * skill[competitor];
        for (int i = 0; i < teams[t2].size(); i++) {
            newStrength2 += (i < index2 ? (i + 1) : (i + 2)) * skill[teams[t2].get(i)];
            newStrengthSD2 += (i < index2 ? (i + 1) : (i + 2)) * skillSD[teams[t2].get(i)];
        }
        newStrength2 /= ((teams[t2].size() + 2) * (teams[t2].size() + 1)) / 2;
        newStrengthSD2 /= ((teams[t2].size() + 2) * (teams[t2].size() + 1)) / 2;
        assert !Double.isNaN(newStrength2);
        assert !Double.isNaN(newStrengthSD2);

        double minStrength = (int) 1e9;
        double maxStrength = (int) -1e9;
        for (int i = 0; i < M; i++) {
            double st = i == t ? newStrength : i == t2 ? newStrength2 : strength[i];
            double stSD = i == t ? newStrengthSD : i == t2 ? newStrengthSD2 : strengthSD[i];
            minStrength = Math.min(minStrength, st - stSD);
            maxStrength = Math.max(maxStrength, st + stSD);
        }
        assert !Double.isNaN(minStrength);
        assert !Double.isNaN(maxStrength);
        double deltaScore = (1e-9 + maxStrength - minStrength) - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            teams[t].remove(index);
            teams[t2].add(index2, competitor);
            strength[t] = newStrength;
            strength[t2] = newStrength2;
            strengthSD[t] = newStrengthSD;
            strengthSD[t2] = newStrengthSD2;
            saveBest();
        } else {
        }
    }

    private int index(int t2, int competitor) {
        for (int i = 0; i < teams[t2].size(); i++) {
            if (skill[competitor] < skill[teams[t2].get(i)]) {
                return i;
            }
        }
        return teams[t2].size();
    }

    private int index(int t2, int competitor, int removedIndex) {
        for (int i = 0; i < teams[t2].size(); i++) {
            if (i == removedIndex) {
                continue;
            }
            if (i < removedIndex) {
                if (skill[competitor] < skill[teams[t2].get(i)]) {
                    return i;
                }
            } else {
                if (skill[competitor] < skill[teams[t2].get(i)]) {
                    return i - 1;
                }
            }
        }
        return teams[t2].size() - 1;
    }

    private void swap() {
        int t1 = (int) (M * rng.nextDouble());
        int index1 = (int) (teams[t1].size() * rng.nextDouble());
        assert teams[t1].size() >= 1;

        int t2 = t1;
        while (t2 == t1) {
            t2 = (int) (M * rng.nextDouble());
        }
        int index2 = (int) (teams[t2].size() * rng.nextDouble());
        assert teams[t2].size() >= 1;

        int competitor1 = teams[t1].get(index1);
        int competitor2 = teams[t2].get(index2);

        int index3 = index(t1, competitor2, index1);
        int index4 = index(t2, competitor1, index2);
        double newStrength1 = strength(t1, index1, competitor2, index3);
        double newStrength2 = strength(t2, index2, competitor1, index4);
        assert !Double.isNaN(newStrength1);
        assert !Double.isNaN(newStrength2);
        double newStrengthSD1 = strengthSD(t1, index1, competitor2, index3);
        double newStrengthSD2 = strengthSD(t2, index2, competitor1, index4);
        assert !Double.isNaN(newStrengthSD1);
        assert !Double.isNaN(newStrengthSD2);

        double minStrength = (int) 1e9;
        double maxStrength = (int) -1e9;
        for (int i = 0; i < M; i++) {
            double st = i == t1 ? newStrength1 : i == t2 ? newStrength2 : strength[i];
            double stSD = i == t1 ? newStrengthSD1 : i == t2 ? newStrengthSD2 : strengthSD[i];
            minStrength = Math.min(minStrength, st - stSD);
            maxStrength = Math.max(maxStrength, st + stSD);
        }
        assert !Double.isNaN(minStrength);
        assert !Double.isNaN(maxStrength);
        double deltaScore = (1e-9 + maxStrength - minStrength) - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            teams[t1].remove(index1);
            teams[t2].remove(index2);
            teams[t1].add(index3, competitor2);
            teams[t2].add(index4, competitor1);
            strength[t1] = newStrength1;
            strength[t2] = newStrength2;
            strengthSD[t1] = newStrengthSD1;
            strengthSD[t2] = newStrengthSD2;
            saveBest();
        } else {
        }
    }

    private double strength(int t1, int index1, int competitor2, int index3) {
        double newStrength1 = 0;
        if (index3 == index1) {
            for (int i = 0; i < teams[t1].size(); i++) {
                if (i == index1) {
                    newStrength1 += (i + 1) * skill[competitor2];
                    continue;
                }
                newStrength1 += (i + 1) * skill[teams[t1].get(i)];
            }
        } else if (index3 < index1) {
            for (int i = 0; i < teams[t1].size(); i++) {
                if (i == index3) {
                    newStrength1 += (i + 1) * skill[competitor2];
                }
                if (i == index1) {
                    continue;
                }
                newStrength1 += (i < index3 ? (i + 1) : i < index1 ? (i + 2) : (i + 1)) * skill[teams[t1].get(i)];
            }
        } else {
            for (int i = 0, k = 1; i < teams[t1].size(); i++) {
                if (i == index1) {
                    continue;
                }
                newStrength1 += k++ * skill[teams[t1].get(i)];
                if (i == index3) {
                    newStrength1 += k++ * skill[competitor2];
                }
            }
        }
        newStrength1 /= ((teams[t1].size() + 1) * (teams[t1].size())) / 2;
        return newStrength1;
    }

    private double strengthSD(int t1, int index1, int competitor2, int index3) {
        double newStrength1 = 0;
        if (index3 == index1) {
            for (int i = 0; i < teams[t1].size(); i++) {
                if (i == index1) {
                    newStrength1 += (i + 1) * skillSD[competitor2];
                    continue;
                }
                newStrength1 += (i + 1) * skillSD[teams[t1].get(i)];
            }
        } else if (index3 < index1) {
            for (int i = 0; i < teams[t1].size(); i++) {
                if (i == index3) {
                    newStrength1 += (i + 1) * skillSD[competitor2];
                }
                if (i == index1) {
                    continue;
                }
                newStrength1 += (i < index3 ? (i + 1) : i < index1 ? (i + 2) : (i + 1)) * skillSD[teams[t1].get(i)];
            }
        } else {
            for (int i = 0, k = 1; i < teams[t1].size(); i++) {
                if (i == index1) {
                    continue;
                }
                newStrength1 += k++ * skillSD[teams[t1].get(i)];
                if (i == index3) {
                    newStrength1 += k++ * skillSD[competitor2];
                }
            }
        }
        newStrength1 /= ((teams[t1].size() + 1) * (teams[t1].size())) / 2;
        return newStrength1;
    }

    private double calculateScore() {
        double minStrength = (int) 1e9;
        double maxStrength = (int) -1e9;
        for (int i = 0; i < M; i++) {
            sort(teams[i]);
            double st = calculateScore(i);
            double stSD = calculateScoreSD(i);
            strength[i] = st;
            strengthSD[i] = stSD;
            minStrength = Math.min(minStrength, st - stSD);
            maxStrength = Math.max(maxStrength, st + stSD);
        }
        return (1e-9 + maxStrength - minStrength);
    }

    private double calculateScore(int i) {
        double total = 0;
        for (int j = 0; j < teams[i].size(); j++) {
            total += (j + 1) * skill[teams[i].get(j)];
        }
        total *= 2;
        total /= teams[i].size();
        total /= teams[i].size() + 1;
        return total;
    }

    private double calculateScoreSD(int i) {
        double total = 0;
        for (int j = 0; j < teams[i].size(); j++) {
            total += (j + 1) * skillSD[teams[i].get(j)];
        }
        total *= 2;
        total /= teams[i].size();
        total /= teams[i].size() + 1;
        return total;
    }

    private void sort(IntList team) {
        mergeSort(team.values, temp, 0, team.size() - 1);
    }

    private int[] temp;

    private void mergeSort(int[] a, int[] temp, int startInclusive, int endInclusive) {
        if (startInclusive >= endInclusive) {
            return;
        }
        int mid = (startInclusive + endInclusive) >> 1;
        mergeSort(a, temp, startInclusive, mid);
        mergeSort(a, temp, mid + 1, endInclusive);
        int i = startInclusive, j = mid + 1, k = startInclusive - 1;
        while (i <= mid && j <= endInclusive) {
            k++;
            double v1 = skill[a[i]];
            double v2 = skill[a[j]];
            if (v1 < v2) {
                temp[k] = a[i];
                i++;
            } else {
                temp[k] = a[j];
                j++;
            }
        }
        for (; i <= mid; i++) {
            k++;
            temp[k] = a[i];
        }
        for (; j <= endInclusive; j++) {
            k++;
            temp[k] = a[j];
        }
        System.arraycopy(temp, startInclusive, a, startInclusive, (endInclusive - startInclusive + 1));
    }

    private void saveBest() {
        if (score < bestScore) {
            bestScore = score;
            for (int t = 0; t < M; t++) {
                bestTeams[t].clear();
                for (int i = 0; i < teams[t].size(); i++) {
                    bestTeams[t].add(teams[t].get(i));
                }
            }
        }
    }

    private void loadBest() {
        score = bestScore;
        for (int t = 0; t < M; t++) {
            teams[t].clear();
            for (int i = 0; i < bestTeams[t].size(); i++) {
                teams[t].add(bestTeams[t].get(i));
            }
        }
    }

    private String[] makeSolution() {
        String[] res = new String[M];
        for (int i = 0; i < M; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < teams[i].size(); j++) {
                if (j > 0) {
                    sb.append(" ");
                }
                sb.append(teams[i].get(j));
            }
            res[i] = sb.toString();
        }
        return res;
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int M = Integer.parseInt(br.readLine());
            int N = Integer.parseInt(br.readLine());
            String[] wins = new String[N];
            for (int i = 0; i < N; ++i) {
                wins[i] = br.readLine();
            }
            ContestOrganizer sol = new ContestOrganizer();
            String[] ret = sol.makeTeams(M, wins);
            System.out.println(ret.length);
            for (int i = 0; i < ret.length; i++) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (IOException 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 = 0.0078125;
    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 ? ContestOrganizer.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 ? ContestOrganizer.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[ContestOrganizer.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[ContestOrganizer.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 IntList {
    private static final int EMPTY = -1;
    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 RandomForest implements ISupervisedLearningAlgorithm {
    private ISupervisedLearningAlgorithm[] algorithms;
    private RandomForestConfig config;
    private boolean print = true;

    public RandomForest(RandomForestConfig config) {
        super();
        this.algorithms = new ISupervisedLearningAlgorithm[config.numTrees];
        this.config = config;
    }

    static int count = 0;

    @Override
    public void train(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes) {
        assert (features.length == results.length);
        assert checkFeatureLength(features);
        int numSamples = features.length;
        int numFeatures = features[0].length;

        TimeManager timeManager = new TimeManager();
        if (config.numTThhrreeaadds == 1) {
            trainSingleThread(features, results, sampleIndexes, featureIndexes, timeManager);
        } else {
            trainMultiThreads(features, results, sampleIndexes, featureIndexes, timeManager);
        }

        if (print) {
        }

    }

    public void train(double[][] features, double[] results) {
        int[] sampleIndexes = new int[features.length];
        for (int i = 0; i < sampleIndexes.length; i++) {
            sampleIndexes[i] = i;
        }
        int[] featureIndexes = new int[features[0].length];
        for (int i = 0; i < featureIndexes.length; i++) {
            featureIndexes[i] = i;
        }
        train(features, results, sampleIndexes, featureIndexes);
    }

    public void train(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes) {
        assert (features.length == results.length);
        assert checkFeatureLength(features);
        int numSamples = features.length;
        int numFeatures = features[0].length;

        TimeManager timeManager = new TimeManager();
        if (config.numTThhrreeaadds == 1) {
            trainSingleThread(features, results, sampleIndexes, featureIndexes, timeManager);
        } else {
            trainMultiThreads(features, results, sampleIndexes, featureIndexes, timeManager);
        }

        if (print) {
        }

    }

    private void trainMultiThreads(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes, TimeManager timeManager) {
        assert sampleIndexes.length > 0;
        assert featureIndexes.length > 0;
        DecisionTreeConfig decisionTreeConfig = getDecisionTreeConfig();

        Thread[] threads = new Thread[config.numTThhrreeaadds];
        for (int t = 0; t < config.numTThhrreeaadds; t++) {
            final int ft = t;
            threads[t] = new Thread(new Runnable() {
                @Override
                public void run() {
                    for (int i = ft; i < algorithms.length; i += config.numTThhrreeaadds) {
                        if (timeManager.getSecond() > config.timeLimitSecond) {
                            break;
                        }

                        int[] bootstrapSampleIndexes;
                        if (config.useBootstrapSample && sampleIndexes.length > 1) {
                            bootstrapSampleIndexes = new int[(int) (config.bootstrapSampleRate * sampleIndexes.length)];
                            for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                                int index = (int) (sampleIndexes.length * RandomForestConstants.RNG.nextDouble());
                                bootstrapSampleIndexes[j] = sampleIndexes[index];
                            }
                        } else {
                            bootstrapSampleIndexes = new int[sampleIndexes.length];
                            for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                                bootstrapSampleIndexes[j] = sampleIndexes[j];
                            }
                        }

                        int[] bootstrapFeatureIndexes;
                        if (config.useBootstrapFeature && featureIndexes.length > 1) {
                            bootstrapFeatureIndexes = new int[(int) (config.bootstrapFeatureRate * featureIndexes.length)];
                            for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                                int index = (int) (featureIndexes.length * RandomForestConstants.RNG.nextDouble());
                                bootstrapFeatureIndexes[j] = featureIndexes[index];
                            }
                        } else {
                            bootstrapFeatureIndexes = new int[featureIndexes.length];
                            for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                                bootstrapFeatureIndexes[j] = featureIndexes[j];
                            }
                        }

                        algorithms[i] = new DecisionTree(decisionTreeConfig);
                        algorithms[i].train(features, results, bootstrapSampleIndexes, bootstrapFeatureIndexes);

                        if (print) {
                            if (Integer.bitCount(i + 1) == 1) {
                                Utils.debug("numTrees", i + 1, "time", timeManager.getSecondString());
                            }
                        }
                    }
                }
            });
        }
        for (int t = 0; t < config.numTThhrreeaadds; t++) {
            threads[t].start();
        }
        for (int t = 0; t < config.numTThhrreeaadds; t++) {
            try {
                threads[t].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        {
            int newLength = -1;
            for (int j = 0; j < algorithms.length; j++) {
                if (algorithms[j] == null) {
                    newLength = j;
                    break;
                }
            }
            if (newLength != -1) {
                algorithms = Arrays.copyOf(algorithms, newLength);
            }
        }
    }

    private void trainMultiThreads(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes, TimeManager timeManager) {
        assert sampleIndexes.length > 0;
        assert featureIndexes.length > 0;
        DecisionTreeConfig decisionTreeConfig = getDecisionTreeConfig();

        Thread[] threads = new Thread[config.numTThhrreeaadds];
        for (int t = 0; t < config.numTThhrreeaadds; t++) {
            final int ft = t;
            threads[t] = new Thread(new Runnable() {
                @Override
                public void run() {
                    for (int i = ft; i < algorithms.length; i += config.numTThhrreeaadds) {
                        if (timeManager.getSecond() > config.timeLimitSecond) {
                            break;
                        }

                        int[] bootstrapSampleIndexes;
                        if (config.useBootstrapSample && sampleIndexes.length > 1) {
                            bootstrapSampleIndexes = new int[(int) (config.bootstrapSampleRate * sampleIndexes.length)];
                            for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                                int index = (int) (sampleIndexes.length * RandomForestConstants.RNG.nextDouble());
                                bootstrapSampleIndexes[j] = sampleIndexes[index];
                            }
                        } else {
                            bootstrapSampleIndexes = new int[sampleIndexes.length];
                            for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                                bootstrapSampleIndexes[j] = sampleIndexes[j];
                            }
                        }

                        int[] bootstrapFeatureIndexes;
                        if (config.useBootstrapFeature && featureIndexes.length > 1) {
                            bootstrapFeatureIndexes = new int[(int) (config.bootstrapFeatureRate * featureIndexes.length)];
                            for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                                int index = (int) (featureIndexes.length * RandomForestConstants.RNG.nextDouble());
                                bootstrapFeatureIndexes[j] = featureIndexes[index];
                            }
                        } else {
                            bootstrapFeatureIndexes = new int[featureIndexes.length];
                            for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                                bootstrapFeatureIndexes[j] = featureIndexes[j];
                            }
                        }

                        algorithms[i] = new DecisionTree(decisionTreeConfig);
                        algorithms[i].train(features, results, bootstrapSampleIndexes, bootstrapFeatureIndexes);

                        if (print) {
                            if (Integer.bitCount(i + 1) == 1) {
                                Utils.debug("numTrees", i + 1, "time", timeManager.getSecondString());
                            }
                        }
                    }
                }
            });
        }
        for (int t = 0; t < config.numTThhrreeaadds; t++) {
            threads[t].start();
        }
        for (int t = 0; t < config.numTThhrreeaadds; t++) {
            try {
                threads[t].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        {
            int newLength = -1;
            for (int j = 0; j < algorithms.length; j++) {
                if (algorithms[j] == null) {
                    newLength = j;
                    break;
                }
            }
            if (newLength != -1) {
                algorithms = Arrays.copyOf(algorithms, newLength);
            }
        }
    }

    private void trainSingleThread(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes, TimeManager timeManager) {

        DecisionTreeConfig decisionTreeConfig = getDecisionTreeConfig();
        for (int i = 0; i < algorithms.length; i++) {
            if (timeManager.getSecond() > config.timeLimitSecond) {
                algorithms = Arrays.copyOf(algorithms, i);
                break;
            }

            int[] bootstrapSampleIndexes;
            if (config.useBootstrapSample && sampleIndexes.length > 1) {
                bootstrapSampleIndexes = new int[(int) (config.bootstrapSampleRate * sampleIndexes.length)];
                for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                    int index = (int) (sampleIndexes.length * RandomForestConstants.RNG.nextDouble());
                    bootstrapSampleIndexes[j] = sampleIndexes[index];
                }
            } else {
                bootstrapSampleIndexes = new int[sampleIndexes.length];
                for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                    bootstrapSampleIndexes[j] = sampleIndexes[j];
                }
            }

            int[] bootstrapFeatureIndexes;
            if (config.useBootstrapFeature && featureIndexes.length > 1) {
                bootstrapFeatureIndexes = new int[(int) (config.bootstrapFeatureRate * featureIndexes.length)];
                for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                    int index = (int) (featureIndexes.length * RandomForestConstants.RNG.nextDouble());
                    bootstrapFeatureIndexes[j] = featureIndexes[index];
                }
            } else {
                bootstrapFeatureIndexes = new int[featureIndexes.length];
                for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                    bootstrapFeatureIndexes[j] = featureIndexes[j];
                }
            }

            algorithms[i] = new DecisionTree(decisionTreeConfig);
            algorithms[i].train(features, results, bootstrapSampleIndexes, bootstrapFeatureIndexes);

            if (print) {
                if (Integer.bitCount(i + 1) == 1) {
                    Utils.debug("numTrees", i + 1, "time", timeManager.getSecondString());
                }
            }
        }
    }

    private void trainSingleThread(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes, TimeManager timeManager) {

        DecisionTreeConfig decisionTreeConfig = getDecisionTreeConfig();
        for (int i = 0; i < algorithms.length; i++) {
            if (timeManager.getSecond() > config.timeLimitSecond) {
                algorithms = Arrays.copyOf(algorithms, i);
                break;
            }

            int[] bootstrapSampleIndexes;
            if (config.useBootstrapSample && sampleIndexes.length > 1) {
                bootstrapSampleIndexes = new int[(int) (config.bootstrapSampleRate * sampleIndexes.length)];
                for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                    int index = (int) (sampleIndexes.length * RandomForestConstants.RNG.nextDouble());
                    bootstrapSampleIndexes[j] = sampleIndexes[index];
                }
            } else {
                bootstrapSampleIndexes = new int[sampleIndexes.length];
                for (int j = 0; j < bootstrapSampleIndexes.length; j++) {
                    bootstrapSampleIndexes[j] = sampleIndexes[j];
                }
            }

            int[] bootstrapFeatureIndexes;
            if (config.useBootstrapFeature && featureIndexes.length > 1) {
                bootstrapFeatureIndexes = new int[(int) (config.bootstrapFeatureRate * featureIndexes.length)];
                for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                    int index = (int) (featureIndexes.length * RandomForestConstants.RNG.nextDouble());
                    bootstrapFeatureIndexes[j] = featureIndexes[index];
                }
            } else {
                bootstrapFeatureIndexes = new int[featureIndexes.length];
                for (int j = 0; j < bootstrapFeatureIndexes.length; j++) {
                    bootstrapFeatureIndexes[j] = featureIndexes[j];
                }
            }

            algorithms[i] = new DecisionTree(decisionTreeConfig);
            algorithms[i].train(features, results, bootstrapSampleIndexes, bootstrapFeatureIndexes);

            if (print) {
                if (Integer.bitCount(i + 1) == 1) {
                    Utils.debug("numTrees", i + 1, "time", timeManager.getSecondString());
                }
            }
        }
    }

    private DecisionTreeConfig getDecisionTreeConfig() {
        DecisionTreeConfig decisionTreeConfig = new DecisionTreeConfig();
        decisionTreeConfig.isClassification = config.isClassification;
        decisionTreeConfig.lossFunction = config.lossFunction;
        decisionTreeConfig.maxDepth = config.maxDepth;
        decisionTreeConfig.minSamples = config.minSamples;
        decisionTreeConfig.splitStrategy = config.splitStrategy;
        return decisionTreeConfig;
    }

    private boolean checkFeatureLength(double[][] features) {
        for (int i = 1; i < features.length; i++) {
            if (features[i].length != features[i - 1].length) {
                Utils.debug("features[i].length != features[i - 1].length", features[i].length, features[i - 1].length);
                return false;
            }
        }
        return true;
    }

    private boolean checkFeatureLength(float[][] features) {
        for (int i = 1; i < features.length; i++) {
            if (features[i].length != features[i - 1].length) {
                Utils.debug("features[i].length != features[i - 1].length", features[i].length, features[i - 1].length);
                return false;
            }
        }
        return true;
    }

    @Override
    public double predict(double[] features) {
        if (config.isClassification) {
            HashMap<Integer, Integer> classCountMap = new HashMap<>();
            for (int i = 0; i < algorithms.length; i++) {
                double prediction = algorithms[i].predict(features);
                if (Double.isNaN(prediction)) {
                    continue;
                }
                int classs = (int) (prediction + 1e-9);
                Integer count = classCountMap.get(classs);
                classCountMap.put(classs, 1 + (count == null ? 0 : count.intValue()));
            }
            int maxClass = -123456789;
            int maxCount = 0;
            for (Integer classs : classCountMap.keySet()) {
                if (classCountMap.get(classs) > maxCount) {
                    maxCount = classCountMap.get(classs);
                    maxClass = classs;
                }
            }
            assert maxClass != -123456789;
            return maxClass;
        } else {
//            double sum = 0;
//            for (int i = 0; i < algorithms.length; i++) {
//                sum += algorithms[i].predict(features);
//            }
//            return sum / algorithms.length;
            MeanHelper helper = new MeanHelper();
            for (int i = 0; i < algorithms.length; i++) {
                helper.add(algorithms[i].predict(features));
            }
            return helper.mean(0);
        }
    }

    public double predictSD(double[] features) {
        if (config.isClassification) {
            HashMap<Integer, Integer> classCountMap = new HashMap<>();
            for (int i = 0; i < algorithms.length; i++) {
                double prediction = algorithms[i].predict(features);
                if (Double.isNaN(prediction)) {
                    continue;
                }
                int classs = (int) (prediction + 1e-9);
                Integer count = classCountMap.get(classs);
                classCountMap.put(classs, 1 + (count == null ? 0 : count.intValue()));
            }
            int maxClass = -123456789;
            int maxCount = 0;
            for (Integer classs : classCountMap.keySet()) {
                if (classCountMap.get(classs) > maxCount) {
                    maxCount = classCountMap.get(classs);
                    maxClass = classs;
                }
            }
            assert maxClass != -123456789;
            return maxClass;
        } else {
            MeanHelper helper = new MeanHelper();
            for (int i = 0; i < algorithms.length; i++) {
                helper.add(algorithms[i].predict(features));
            }
            return helper.standardDeviation(1e-9);
        }
    }

    public double predict(float[] features) {
        if (config.isClassification) {
            HashMap<Integer, Integer> classCountMap = new HashMap<>();
            for (int i = 0; i < algorithms.length; i++) {
                double prediction = algorithms[i].predict(features);
                if (Double.isNaN(prediction)) {
                    continue;
                }
                int classs = (int) (prediction + 1e-9);
                Integer count = classCountMap.get(classs);
                classCountMap.put(classs, 1 + (count == null ? 0 : count.intValue()));
            }
            int maxClass = -123456789;
            int maxCount = 0;
            for (Integer classs : classCountMap.keySet()) {
                if (classCountMap.get(classs) > maxCount) {
                    maxCount = classCountMap.get(classs);
                    maxClass = classs;
                }
            }
            assert maxClass != -123456789;
            return maxClass;
        } else {
            double sum = 0;
            for (int i = 0; i < algorithms.length; i++) {
                sum += algorithms[i].predict(features);
            }
            return sum / algorithms.length;
        }
    }

    public void save(File file) {
        for (int i = 0; i < algorithms.length; i++) {
            ((DecisionTree) algorithms[i]).save(new File(file.getParentFile(), file.getName() + "_" + i));
        }
    }

    public void load(File file) {
        DecisionTreeConfig decisionTreeConfig = getDecisionTreeConfig();
        for (int i = 0; i < algorithms.length; i++) {
            File filei = new File(file.getParentFile(), file.getName() + "_" + i);
            DecisionTree decisionTree = new DecisionTree(decisionTreeConfig);
            decisionTree.load(filei);
            algorithms[i] = decisionTree;
        }
    }

    public void load(String[] lines) {
        DecisionTreeConfig decisionTreeConfig = getDecisionTreeConfig();
        for (int i = 0; i < algorithms.length; i++) {
            DecisionTree decisionTree = new DecisionTree(decisionTreeConfig);
            String[] lines2 = new String[4];
            for (int j = 0; j < lines2.length; j++) {
                lines2[j] = lines[i * 4 + j];
            }
            decisionTree.load(lines2);
            algorithms[i] = decisionTree;
        }
    }

}

class DecisionTree implements ISupervisedLearningAlgorithm {
    private Node root = new Node();
    private DecisionTreeConfig config;

    public DecisionTree(DecisionTreeConfig config) {
        super();
        this.config = config;
    }

    private int[] featureIndexes;

    @Override
    public void train(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes) {
        assert sampleIndexes.length > 0;
        assert featureIndexes.length > 0;
        this.featureIndexes = featureIndexes;

        root.score = config.lossFunction.getScore(features, results, sampleIndexes, featureIndexes);

        dfs(features, results, sampleIndexes, root, 0);
    }

    public void train(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes) {
        assert sampleIndexes.length > 0;
        assert featureIndexes.length > 0;
        this.featureIndexes = featureIndexes;

        root.score = config.lossFunction.getScore(features, results, sampleIndexes, featureIndexes);

        dfs(features, results, sampleIndexes, root, 0);
    }

    private void dfs(double[][] features, double[] results, int[] sampleIndexes, Node node, int depth) {
        if (depth >= config.maxDepth || sampleIndexes.length <= config.minSamples || isSameResult(results, sampleIndexes)) {
            setLeafNode(results, sampleIndexes, node);
            RandomForestConstants.leafDepth.add(depth);
            RandomForestConstants.leafSample.add(sampleIndexes.length);
            return;
        }

        SplitResult splitResult = config.splitStrategy.split(features, results, sampleIndexes, featureIndexes);
        if (splitResult.leftSamples.length == 0 || splitResult.rightSamples.length == 0) {
            setLeafNode(results, sampleIndexes, node);
            RandomForestConstants.failDepth.add(depth);
            RandomForestConstants.leafDepth.add(depth);
            RandomForestConstants.leafSample.add(sampleIndexes.length);
            return;
        }

        if (RandomForestConstants.CALCULATE_IMPORTANCE && splitResult.splitFeature >= 0 && splitResult.splitFeature < RandomForestConstants.IMPORTANCE_HELPER.length) {
            RandomForestConstants.IMPORTANCE_HELPER[splitResult.splitFeature].add(node.score - (splitResult.leftScore + splitResult.rightScore));
        }

        node.isLeaf = false;
        node.splitFeature = splitResult.splitFeature;
        node.splitValue = splitResult.splitValue;

        if (node.left == null) {
            node.left = new Node();
        }
        node.left.score = splitResult.leftScore;
        dfs(features, results, Arrays.copyOf(splitResult.leftSamples.values, splitResult.leftSamples.length), node.left, depth + 1);

        if (node.right == null) {
            node.right = new Node();
        }
        node.right.score = splitResult.rightScore;
        dfs(features, results, Arrays.copyOf(splitResult.rightSamples.values, splitResult.rightSamples.length), node.right, depth + 1);
    }

    private void dfs(float[][] features, float[] results, int[] sampleIndexes, Node node, int depth) {
        if (depth >= config.maxDepth || sampleIndexes.length <= config.minSamples || isSameResult(results, sampleIndexes)) {
            setLeafNode(results, sampleIndexes, node);
            RandomForestConstants.leafDepth.add(depth);
            RandomForestConstants.leafSample.add(sampleIndexes.length);
            return;
        }

        SplitResult splitResult = config.splitStrategy.split(features, results, sampleIndexes, featureIndexes);
        if (splitResult.leftSamples.length == 0 || splitResult.rightSamples.length == 0) {
            setLeafNode(results, sampleIndexes, node);
            RandomForestConstants.failDepth.add(depth);
            RandomForestConstants.leafDepth.add(depth);
            RandomForestConstants.leafSample.add(sampleIndexes.length);
            return;
        }

        if (RandomForestConstants.CALCULATE_IMPORTANCE && splitResult.splitFeature >= 0 && splitResult.splitFeature < RandomForestConstants.IMPORTANCE_HELPER.length) {
            RandomForestConstants.IMPORTANCE_HELPER[splitResult.splitFeature].add(node.score - (splitResult.leftScore + splitResult.rightScore));
        }

        node.isLeaf = false;
        node.splitFeature = splitResult.splitFeature;
        node.splitValue = splitResult.splitValue;

        if (node.left == null) {
            node.left = new Node();
        }
        node.left.score = splitResult.leftScore;
        dfs(features, results, Arrays.copyOf(splitResult.leftSamples.values, splitResult.leftSamples.length), node.left, depth + 1);

        if (node.right == null) {
            node.right = new Node();
        }
        node.right.score = splitResult.rightScore;
        dfs(features, results, Arrays.copyOf(splitResult.rightSamples.values, splitResult.rightSamples.length), node.right, depth + 1);
    }

    private boolean isSameResult(double[] results, int[] samples) {
        for (int i = 1; i < samples.length; i++) {
            if (results[samples[i - 1]] != results[samples[i]]) {
                return false;
            }
        }
        return true;
    }

    private boolean isSameResult(float[] results, int[] samples) {
        for (int i = 1; i < samples.length; i++) {
            if (results[samples[i - 1]] != results[samples[i]]) {
                return false;
            }
        }
        return true;
    }

    private void setLeafNode(double[] results, int[] samples, Node node) {
        if (samples.length == 0) {
            throw new AssertionError();
        }

        if (config.isClassification) {
            node.isLeaf = true;

            HashMap<Integer, Integer> classCountMap = new HashMap<>();
            for (int i = 0; i < samples.length; i++) {
                int classs = (int) (results[samples[i]] + 1e-9);
                Integer count = classCountMap.get(classs);
                classCountMap.put(classs, 1 + (count == null ? 0 : count));
            }

            double maxClass = Double.NaN;
            int maxCount = 0;
            for (Integer classs : classCountMap.keySet()) {
                Integer count = classCountMap.get(classs);
                if (count > maxCount) {
                    maxCount = count;
                    maxClass = classs;
                }
            }

            node.result = maxClass;
            return;
        }

        double sum = 0;
        for (int i = 0; i < samples.length; i++) {
            sum += results[samples[i]];
        }
        node.result = sum / samples.length;
        node.isLeaf = true;
    }

    private void setLeafNode(float[] results, int[] samples, Node node) {
        if (samples.length == 0) {
            throw new AssertionError();
        }

        if (config.isClassification) {
            node.isLeaf = true;

            HashMap<Integer, Integer> classCountMap = new HashMap<>();
            for (int i = 0; i < samples.length; i++) {
                int classs = (int) (results[samples[i]] + 1e-9);
                Integer count = classCountMap.get(classs);
                classCountMap.put(classs, 1 + (count == null ? 0 : count));
            }

            double maxClass = Double.NaN;
            int maxCount = 0;
            for (Integer classs : classCountMap.keySet()) {
                Integer count = classCountMap.get(classs);
                if (count > maxCount) {
                    maxCount = count;
                    maxClass = classs;
                }
            }

            node.result = maxClass;
            return;
        }

        double sum = 0;
        for (int i = 0; i < samples.length; i++) {
            sum += results[samples[i]];
        }
        node.result = sum / samples.length;
        node.isLeaf = true;
    }

    @Override
    public double predict(double[] features) {
        for (Node currentNode = root;;) {
            if (currentNode.isLeaf) {
                return currentNode.result;
            }
            currentNode = features[currentNode.splitFeature] < currentNode.splitValue ? currentNode.left : currentNode.right;
        }
    }

    public double predict(float[] features) {
        for (Node currentNode = root;;) {
            if (currentNode.isLeaf) {
                return currentNode.result;
            }
            currentNode = features[currentNode.splitFeature] < currentNode.splitValue ? currentNode.left : currentNode.right;
        }
    }

    public void save(File file) {
        IntArray nodeIndexes = new IntArray();
        IntArray lefts = new IntArray();
        IntArray rights = new IntArray();
        IntArray featureIndexes = new IntArray();
        DoubleArray splitValues = new DoubleArray();

        int nodeIndex = 0;
        LinkedList<Pair<Integer, Node>> queue = new LinkedList<>();
        {
            queue.addLast(new Pair<Integer, Node>(nodeIndex++, root));
        }
        for (; !queue.isEmpty();) {
            Pair<Integer, Node> currentNode = queue.pollFirst();
            if (currentNode.second.isLeaf) {
                nodeIndexes.add(currentNode.first.intValue());
                featureIndexes.add(-1);
                lefts.add(-1);
                rights.add(-1);
                splitValues.add(currentNode.second.result);
                continue;
            }

            nodeIndexes.add(currentNode.first.intValue());
            featureIndexes.add(currentNode.second.splitFeature);
            lefts.add(nodeIndex + 0);
            rights.add(nodeIndex + 1);
            splitValues.add(currentNode.second.splitValue);
            queue.addLast(new Pair<Integer, Node>(nodeIndex++, currentNode.second.left));
            queue.addLast(new Pair<Integer, Node>(nodeIndex++, currentNode.second.right));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < lefts.length; i++) {
            if (i > 0) {
                sb.append(",");
            }
            sb.append(lefts.values[i]);
        }
        sb.append("\n");
        for (int i = 0; i < rights.length; i++) {
            if (i > 0) {
                sb.append(",");
            }
            sb.append(rights.values[i]);
        }
        sb.append("\n");
        for (int i = 0; i < featureIndexes.length; i++) {
            if (i > 0) {
                sb.append(",");
            }
            sb.append(featureIndexes.values[i]);
        }
        sb.append("\n");
        for (int i = 0; i < splitValues.length; i++) {
            if (i > 0) {
                sb.append(",");
            }
            sb.append((float) splitValues.values[i]);
        }
        sb.append("\n");
        TextFileIO.write(sb.toString(), file);
    }

    public void load(File file) {
        IntArray lefts = new IntArray();
        IntArray rights = new IntArray();
        IntArray featureIndexes = new IntArray();
        DoubleArray splitValues = new DoubleArray();

        ArrayList<String> lines = TextFileIO.readLines(file);

        boolean printArrayTree2 = !true;
        if (printArrayTree2) {
            TextFileIO.appendln("trees.add(new ArrayTree2(");
            for (int i = 0; i < lines.size(); i++) {
                if (i < 3) {
                    TextFileIO.appendln("toInt(\"" + lines.get(i) + "\"),");
                } else {
                    TextFileIO.appendln("toDouble(\"" + lines.get(i) + "\")));");
                }
            }
        }

        {
            String[] split = lines.get(0).split(",");
            for (int i = 0; i < split.length; i++) {
                lefts.add(Integer.parseInt(split[i]));
            }
        }
        {
            String[] split = lines.get(1).split(",");
            for (int i = 0; i < split.length; i++) {
                rights.add(Integer.parseInt(split[i]));
            }
        }
        {
            String[] split = lines.get(2).split(",");
            for (int i = 0; i < split.length; i++) {
                featureIndexes.add(Integer.parseInt(split[i]));
            }
        }
        {
            String[] split = lines.get(3).split(",");
            for (int i = 0; i < split.length; i++) {
                splitValues.add(Double.parseDouble(split[i]));
            }
        }

        dfs(root, 0, lefts, rights, featureIndexes, splitValues);
    }

    public void load(String[] lines) {
        IntArray lefts = new IntArray();
        IntArray rights = new IntArray();
        IntArray featureIndexes = new IntArray();
        DoubleArray splitValues = new DoubleArray();
        {
            String[] split = lines[0].split(",");
            for (int i = 0; i < split.length; i++) {
                lefts.add(Integer.parseInt(split[i]));
            }
        }
        {
            String[] split = lines[1].split(",");
            for (int i = 0; i < split.length; i++) {
                rights.add(Integer.parseInt(split[i]));
            }
        }
        {
            String[] split = lines[2].split(",");
            for (int i = 0; i < split.length; i++) {
                featureIndexes.add(Integer.parseInt(split[i]));
            }
        }
        {
            String[] split = lines[3].split(",");
            for (int i = 0; i < split.length; i++) {
                splitValues.add(Double.parseDouble(split[i]));
            }
        }

        dfs(root, 0, lefts, rights, featureIndexes, splitValues);
    }

    private void dfs(Node node, int i, IntArray lefts, IntArray rights, IntArray featureIndexes2, DoubleArray splitValues) {

        LinkedList<Integer> queue = new LinkedList<>();
        LinkedList<Node> nodeQueue = new LinkedList<>();
        {
            queue.addLast(i);
            nodeQueue.addLast(node);
        }
        for (; !queue.isEmpty();) {
            int index = queue.pollFirst().intValue();
            Node currentNode = nodeQueue.pollFirst();

            if (featureIndexes2.values[index] == -1) {
                currentNode.isLeaf = true;
                currentNode.result = splitValues.values[index];
                continue;
            }

            currentNode.isLeaf = false;
            currentNode.splitFeature = featureIndexes2.values[index];
            currentNode.splitValue = splitValues.values[index];

            if (currentNode.left == null) {
                currentNode.left = new Node();
            }

            queue.addLast(lefts.values[index]);
            nodeQueue.addLast(currentNode.left);
            if (currentNode.right == null) {
                currentNode.right = new Node();
            }

            queue.addLast(rights.values[index]);
            nodeQueue.addLast(currentNode.right);
        }
    }
}

class DecisionTreeConfig {
    public ILossFunction lossFunction;

    public int minSamples;
    public int maxDepth;
    public ISplitStrategy splitStrategy;

    public boolean isClassification;

    public DecisionTreeConfig() {
    }
}

interface ILossFunction {
    public double getScore(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes);

    public double getScore(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes);
}

interface ISplitStrategy {
    public SplitResult split(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes);

    public SplitResult split(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes);

}

interface ISupervisedLearningAlgorithm {
    public void train(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes);

    public void train(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes);

    double predict(double[] features);

    double predict(float[] features);
}

class Node {
    public Node left;
    public Node right;
    public double result;
    public double splitValue;
    public int splitFeature;
    public boolean isLeaf = false;
    public double score;
}

class RandomForestConfig {
    public boolean useBootstrapSample;
    public double bootstrapSampleRate;

    public boolean useBootstrapFeature;
    public double bootstrapFeatureRate;

    public ILossFunction lossFunction;

    public int minSamples;
    public int maxDepth;
    public int numTrees;

    public ISplitStrategy splitStrategy;

    public double timeLimitSecond;

    public boolean isClassification;

    public int numTThhrreeaadds;

    public RandomForestConfig() {
    }
}

final class RandomForestConstants {

    public static final XorShift RNG = new XorShift(System.nanoTime());
    public static final boolean CALCULATE_IMPORTANCE = true;
    public static final double[] COUNT_FEATURES = new double[20000];
    public static final String[] FEATURE_NAMES = new String[20000];
    public static final MeanHelper[] IMPORTANCE_HELPER = new MeanHelper[20000];
    static {
        for (int i = 0; i < IMPORTANCE_HELPER.length; i++) {
            IMPORTANCE_HELPER[i] = new MeanHelper();
        }
    }
    public static MeanHelper failDepth = new MeanHelper();
    public static MeanHelper leafDepth = new MeanHelper();
    public static MeanHelper leafSample = new MeanHelper();

    private RandomForestConstants() {
    }
}

class SplitResult {
    public int splitFeature = -1;
    public double splitValue = -1;
    public IntArray leftSamples = new IntArray();
    public IntArray rightSamples = new IntArray();
    public double rightScore = Double.POSITIVE_INFINITY;
    public double leftScore = Double.POSITIVE_INFINITY;
}

class SplitStrategyCareful implements ISplitStrategy {
    private int features;
    private int samples;
    private ILossFunction lossFunction;

    public SplitStrategyCareful(int features, int samples, ILossFunction lossFunction) {
        super();
        this.features = features;
        this.samples = samples;
        this.lossFunction = lossFunction;
    }

    @Override
    public SplitResult split(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes) {

        double scoreParent = this.lossFunction.getScore(features, results, sampleIndexes, featureIndexes);

        IntArray leftSamples = new IntArray(sampleIndexes.length);
        IntArray rightSamples = new IntArray(sampleIndexes.length);

        SplitResult best = new SplitResult();

        ArrayList<Integer> splitFeatureIndexes = new ArrayList<>();
        for (int c = 0; c < featureIndexes.length; c++) {
            splitFeatureIndexes.add(featureIndexes[c]);
        }
        int countFails = 0;
        for (int i = 0; i < this.features; i++) {
            if (splitFeatureIndexes.size() == 0) {
                break;
            }

            int featureIndexIndex = (int) (splitFeatureIndexes.size() * RandomForestConstants.RNG.nextDouble());
            int featureIndex = splitFeatureIndexes.get(featureIndexIndex).intValue();
            if (!(featureIndex >= 0 && featureIndex < features[0].length)) {
                Utils.debug("!(feature >= 0 && feature < features[0].length)");
            }

            HashSet<Double> splitValues = new HashSet<>();
            for (int j = 0; j < sampleIndexes.length; j++) {
                int sampleIndex = sampleIndexes[j];
                if (!(sampleIndex >= 0 && sampleIndex < features.length)) {
                    Utils.debug("!(s >= 0 && s < features.length)");
                }
                double splitValue = features[sampleIndex][featureIndex] - 1e-9;
                splitValues.add(splitValue);
            }

            ArrayList<Double> validSplitValues = new ArrayList<>(splitValues);
            CollectionsUtils.select(validSplitValues, 0, validSplitValues.size(), 0);
            validSplitValues.remove(0);
            if (validSplitValues.size() == 0) {
                splitFeatureIndexes.remove(featureIndexIndex);
                countFails++;
                i--;
                continue;
            }

            for (int j = 0; j < this.samples; j++) {
                if (validSplitValues.size() == 0) {
                    break;
                }

                double splitValue = validSplitValues.remove((int) (validSplitValues.size() * RandomForestConstants.RNG.nextDouble())).doubleValue();
                leftSamples.clear();
                rightSamples.clear();

                for (int k = 0; k < sampleIndexes.length; k++) {
                    int sample = sampleIndexes[k];
                    if (features[sample][featureIndex] < splitValue) {
                        leftSamples.add(sample);
                    } else {
                        rightSamples.add(sample);
                    }
                }

                double score = this.lossFunction.getScore(features, results, Arrays.copyOf(leftSamples.values, leftSamples.length), featureIndexes);
                double scoreR = this.lossFunction.getScore(features, results, Arrays.copyOf(rightSamples.values, rightSamples.length), featureIndexes);

                if (RandomForestConstants.CALCULATE_IMPORTANCE && featureIndex >= 0 && featureIndex < RandomForestConstants.IMPORTANCE_HELPER.length) {
                    RandomForestConstants.IMPORTANCE_HELPER[featureIndex].add(scoreParent - (score + scoreR));
                }

                if (score + scoreR < best.leftScore + best.rightScore) {

                    best.splitFeature = featureIndex;

                    double maxLeftSplitValue = -1e9;
                    for (int k = 0; k < leftSamples.length; k++) {
                        int sample = leftSamples.values[k];
                        maxLeftSplitValue = Math.max(maxLeftSplitValue, features[sample][featureIndex]);
                    }
                    best.splitValue = (maxLeftSplitValue + splitValue) / 2.0;
                    best.leftScore = score;
                    best.rightScore = scoreR;

                    if (best.leftSamples.values.length >= leftSamples.values.length) {
                        System.arraycopy(leftSamples.values, 0, best.leftSamples.values, 0, leftSamples.values.length);
                    } else {
                        best.leftSamples.values = Arrays.copyOf(leftSamples.values, leftSamples.values.length);
                    }
                    best.leftSamples.length = leftSamples.length;

                    if (best.rightSamples.values.length >= rightSamples.values.length) {
                        System.arraycopy(rightSamples.values, 0, best.rightSamples.values, 0, rightSamples.values.length);
                    } else {
                        best.rightSamples.values = Arrays.copyOf(rightSamples.values, rightSamples.values.length);
                    }
                    best.rightSamples.length = rightSamples.length;
                }
            }
        }
        return best;
    }

    @Override
    public SplitResult split(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes) {

        double scoreParent = this.lossFunction.getScore(features, results, sampleIndexes, featureIndexes);

        IntArray leftSamples = new IntArray(sampleIndexes.length);
        IntArray rightSamples = new IntArray(sampleIndexes.length);

        SplitResult best = new SplitResult();

        ArrayList<Integer> splitFeatureIndexes = new ArrayList<>();
        for (int c = 0; c < featureIndexes.length; c++) {
            splitFeatureIndexes.add(featureIndexes[c]);
        }
        int countFails = 0;
        for (int i = 0; i < this.features; i++) {
            if (splitFeatureIndexes.size() == 0) {
                break;
            }

            int featureIndexIndex = (int) (splitFeatureIndexes.size() * RandomForestConstants.RNG.nextDouble());
            int featureIndex = splitFeatureIndexes.get(featureIndexIndex).intValue();
            if (!(featureIndex >= 0 && featureIndex < features[0].length)) {
                Utils.debug("!(feature >= 0 && feature < features[0].length)");
            }

            HashSet<Double> splitValues = new HashSet<>();
            for (int j = 0; j < sampleIndexes.length; j++) {
                int sampleIndex = sampleIndexes[j];
                if (!(sampleIndex >= 0 && sampleIndex < features.length)) {
                    Utils.debug("!(s >= 0 && s < features.length)");
                }
                double splitValue = features[sampleIndex][featureIndex] - 1e-9;
                splitValues.add(splitValue);
            }

            ArrayList<Double> validSplitValues = new ArrayList<>(splitValues);
            CollectionsUtils.select(validSplitValues, 0, validSplitValues.size(), 0);
            validSplitValues.remove(0);
            if (validSplitValues.size() == 0) {
                splitFeatureIndexes.remove(featureIndexIndex);
                countFails++;
                i--;
                continue;
            }

            for (int j = 0; j < this.samples; j++) {
                if (validSplitValues.size() == 0) {
                    break;
                }

                double splitValue = validSplitValues.remove((int) (validSplitValues.size() * RandomForestConstants.RNG.nextDouble())).doubleValue();
                leftSamples.clear();
                rightSamples.clear();

                for (int k = 0; k < sampleIndexes.length; k++) {
                    int sample = sampleIndexes[k];
                    if (features[sample][featureIndex] < splitValue) {
                        leftSamples.add(sample);
                    } else {
                        rightSamples.add(sample);
                    }
                }

                double score = this.lossFunction.getScore(features, results, Arrays.copyOf(leftSamples.values, leftSamples.length), featureIndexes);
                double scoreR = this.lossFunction.getScore(features, results, Arrays.copyOf(rightSamples.values, rightSamples.length), featureIndexes);

                if (RandomForestConstants.CALCULATE_IMPORTANCE && featureIndex >= 0 && featureIndex < RandomForestConstants.IMPORTANCE_HELPER.length) {
                    RandomForestConstants.IMPORTANCE_HELPER[featureIndex].add(scoreParent - (score + scoreR));
                }

                if (score + scoreR < best.leftScore + best.rightScore) {

                    best.splitFeature = featureIndex;

                    double maxLeftSplitValue = -1e9;
                    for (int k = 0; k < leftSamples.length; k++) {
                        int sample = leftSamples.values[k];
                        maxLeftSplitValue = Math.max(maxLeftSplitValue, features[sample][featureIndex]);
                    }
                    best.splitValue = (maxLeftSplitValue + splitValue) / 2.0;
                    best.leftScore = score;
                    best.rightScore = scoreR;

                    if (best.leftSamples.values.length >= leftSamples.values.length) {
                        System.arraycopy(leftSamples.values, 0, best.leftSamples.values, 0, leftSamples.values.length);
                    } else {
                        best.leftSamples.values = Arrays.copyOf(leftSamples.values, leftSamples.values.length);
                    }
                    best.leftSamples.length = leftSamples.length;

                    if (best.rightSamples.values.length >= rightSamples.values.length) {
                        System.arraycopy(rightSamples.values, 0, best.rightSamples.values, 0, rightSamples.values.length);
                    } else {
                        best.rightSamples.values = Arrays.copyOf(rightSamples.values, rightSamples.values.length);
                    }
                    best.rightSamples.length = rightSamples.length;
                }
            }
        }
        return best;
    }

}

class CollectionsUtils {
    private CollectionsUtils() {
    }

    public static final <T> void shuffle(ArrayList<T> 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 <T> void shuffle(ArrayList<T> 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 <T> void select0(ArrayList<T> a, int l, int r, int k, Comparator<T> 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 <T> void select(ArrayList<T> a, int startInclusive, int endExclusive, int k, Comparator<T> comparator) {
        select0(a, startInclusive, endExclusive - 1, k, comparator);
    }

    public static final <T extends Comparable<T>> void select0(ArrayList<T> 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 <T extends Comparable<T>> void select(ArrayList<T> a, int startInclusive, int endExclusive, int k) {
        select0(a, startInclusive, endExclusive - 1, k);
    }

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

    public static final <T> void sort3(ArrayList<T> a, int i, int j, int k, Comparator<T> 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 <T extends Comparable<T>> void sort3(ArrayList<T> 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 <T> int partition3(ArrayList<T> a, int l, int r, Comparator<T> 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 <T extends Comparable<T>> int partition3(ArrayList<T> 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 <T extends Comparable<T>> int partition(ArrayList<T> 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 <T> void sort(ArrayList<T> a, int lInclusive, int rInclusive, Comparator<T> 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 <T extends Comparable<T>> void sort(ArrayList<T> 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 <T> ArrayList<T> reverse(ArrayList<T> 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 <T> ArrayList<T> newReverse(ArrayList<T> list) {
        ArrayList<T> res = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            res.add(list.get(i));
        }
        return res;
    }

}

class SumSquaredErrors implements ILossFunction {

    @Override
    public double getScore(double[][] features, double[] results, int[] sampleIndexes, int[] featureIndexes) {

        double sum = 0;
        double sumSquared = 0;
        int count = 0;
        for (int i = 0; i < sampleIndexes.length; i++) {
            double result = results[sampleIndexes[i]];
            sum += result;
            sumSquared += result * result;
            count++;
        }
        return count == 0 ? 0 : sumSquared - sum * sum / count;
    }

    @Override
    public double getScore(float[][] features, float[] results, int[] sampleIndexes, int[] featureIndexes) {

        double sum = 0;
        double sumSquared = 0;
        int count = 0;
        for (int i = 0; i < sampleIndexes.length; i++) {
            double result = results[sampleIndexes[i]];
            sum += result;
            sumSquared += result * result;
            count++;
        }
        return count == 0 ? 0 : sumSquared - sum * sum / count;
    }
}

class DoubleArray {
    public double[] values;
    public int length;

    public DoubleArray() {
        this(new double[4], 0);
    }

    public DoubleArray(int capacity) {
        this(new double[capacity], 0);
    }

    public DoubleArray(double[] values) {
        this(values, values.length);
    }

    public DoubleArray(double[] values, int length) {
        this.values = values;
        this.length = length;
    }

    public void add(double value) {
        if (length == values.length) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        values[length++] = value;
    }

    public boolean contains(double value) {
        for (int i = 0; i < length; i++) {
            if (values[i] == value) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        length = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i = 0; i < length; i++) {
            sb.append(values[i] + ",");
        }
        sb.append("}");
        return sb.toString();
    }

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

    public double remove() {
        return values[--length];
    }

    public double remove(int index) {
        if (index >= length) {
            throw new AssertionError();
        }

        double res = values[index];

        System.arraycopy(values, index + 1, values, index, length - (index + 1));
        length--;

        return res;
    }

    public void set(int index, double value) {
        if (index == length) {
            add(value);
            return;
        }

        if (index > length) {
            throw new AssertionError();
        }

        if (length == values.length) {
            values = Arrays.copyOf(values, values.length << 1);
        }

        System.arraycopy(values, index, values, index + 1, length - index);
        length++;

        values[index] = value;
    }

    public double[] toArray() {
        return Arrays.copyOf(values, length);
    }

}

class IntArray {
    public int[] values;
    public int length;

    public IntArray() {
        this(new int[4], 0);
    }

    public IntArray(int capacity) {
        this(new int[capacity], 0);
    }

    public IntArray(int[] values) {
        this(values, values.length);
    }

    public IntArray(int[] values, int length) {
        this.values = values;
        this.length = length;
    }

    public void add(int value) {
        if (length == values.length) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        values[length++] = value;
    }

    public int remove() {
        return values[--length];
    }

    public boolean contains(int value) {
        for (int i = 0; i < length; i++) {
            if (values[i] == value) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        length = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i = 0; i < length; i++) {
            sb.append(values[i] + ",");
        }
        sb.append("}");
        return sb.toString();
    }

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

    public int remove(int index) {
        if (index >= length) {
            throw new AssertionError();
        }

        if (index == length - 1) {
            return remove();
        }

        int res = values[index];
        System.arraycopy(values, index + 1, values, index, length - (index + 1));
        length--;

        return res;
    }

    public void set(int index, int value) {
        if (index == length) {
            add(value);
            return;
        }

        if (index >= length) {
            throw new AssertionError();
        }

        if (length >= values.length - 1) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        System.arraycopy(values, index, values, index + 1, length - index);
        length++;

        values[index] = value;
    }

    public IntArray copy() {
        return new IntArray(Arrays.copyOf(values, length), length);
    }

    public int[] toArray() {
        return Arrays.copyOf(values, length);
    }

}

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 Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
    public T first;
    public S second;

    public Pair(T t, S s) {
        this.first = t;
        this.second = s;
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((first == null) ? 0 : first.hashCode());
            result = prime * result + ((second == null) ? 0 : second.hashCode());
            hash = result;
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair<T, S> other = (Pair<T, S>) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        return true;
    }

    @Override
    public int compareTo(Pair<T, S> o) {
        return first.compareTo(o.first);
    }
}

class TextFileIO {
    public static String read0(File file, String encoding) {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            char[] ch = new char[50000];
            int read;
            while ((read = reader.read(ch)) > 0) {
                String s = new String(ch, 0, read);
                sb.append(s);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return sb.toString();
    }

    public static String read(File file) {
        return read(file, "UTF-8");
    }

    public static String read(File file, String encoding) {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                sb.append(line + "\n");
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return sb.toString();
    }

    public static String[] read2(File file, String encoding) {
        ArrayList<String> list = new ArrayList<String>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                list.add(line);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return (String[]) list.toArray(new String[list.size()]);
    }

    public static ArrayList<String> readLines(File file) {
        return read3(file, "UTF-8");
    }

    public static ArrayList<String> readLines(File file, String encoding) {
        return read3(file, encoding);
    }

    public static List<String> readLines(Path file, Charset encoding) {
        try (BufferedReader reader = Files.newBufferedReader(file, encoding)) {
            return reader.lines().collect(Collectors.toList());
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        ArrayList<String> res = new ArrayList<String>();
        return res;
    }

    public static ArrayList<String> read3(File file) {
        return read3(file, "UTF-8");
    }

    public static ArrayList<String> read3(File file, String encoding) {
        ArrayList<String> res = new ArrayList<String>();

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                res.add(line);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return res;
    }

    public static ArrayList<String> readFirstNLines(int numLines, File file) {
        return readFirstNLines(numLines, file, "UTF-8");
    }

    public static ArrayList<String> readFirstNLines(int numLines, File file, String encoding) {
        ArrayList<String> res = new ArrayList<String>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                res.add(line);
                if (res.size() >= numLines) {
                    break;
                }
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return res;
    }

    private static void mkParents(File file) {
        File parentFile = file.getParentFile();
        if (!parentFile.exists()) {
            for (int i = 0; i < 5; i++) {
                if (parentFile.mkdirs()) {
                    break;
                }
            }
        }
    }

    public static void write(String contents, Path file, Charset encoding) {
        try {
            Files.createDirectories(file.getParent());
        } catch (IOException e) {
            e.printStackTrace();
        }
        try (BufferedWriter writer = Files.newBufferedWriter(file, encoding)) {
            writer.write(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void append(String contents, Path file, Charset encoding) {
        try {
            Files.createDirectories(file.getParent());
        } catch (IOException e) {
            e.printStackTrace();
        }
        try (BufferedWriter writer = Files.newBufferedWriter(file, encoding, StandardOpenOption.APPEND)) {
            writer.append(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void write(String contents, File file, String encoding) {
        mkParents(file);

        BufferedWriter writer = null;
        try {
            writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file), encoding));
            writer.write(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void append(String contents, File file, String encoding) {
        mkParents(file);

        BufferedWriter writer = null;
        try {
            writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file, true), encoding));
            writer.append(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void appendln(String contents, File file, String encoding) {
        append(contents + "\n", file, encoding);
    }

    public static void write(String contents) {
        write(contents, new File("./debug.txt"), "UTF-8");
    }

    public static void write(String contents, File file) {
        write(contents, file, "UTF-8");
    }

    public static void writeln(String contents) {
        write(contents + "\n", new File("./debug.txt"), "UTF-8");
    }

    public static void writeln(String contents, File file) {
        write(contents + "\n", file, "UTF-8");
    }

    public static void append(String contents) {
        append(contents, new File("./debug.txt"), "UTF-8");
    }

    public static void append(String contents, File file) {
        append(contents, file, "UTF-8");
    }

    public static void appendln(String contents) {
        append(contents + "\n", new File("./debug.txt"), "UTF-8");
    }

    public static void appendln(String contents, File file) {
        append(contents + "\n", file, "UTF-8");
    }

    public static String read() {
        return read(new File("./debug.txt"), "UTF-8");
    }

    public static int calculateNumLines(File file) {
        return calculateNumLines(file, "UTF-8");
    }

    public static int calculateNumLines(File file, String encoding) {
        int numLines = 0;
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                numLines++;
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return numLines;
    }

    public static void printRandomLines(double d, File file) {
        printRandomLines(d, file, "UTF-8");
    }

    public static void printRandomLines(double d, File file, String encoding) {
        Random rng = new Random(System.nanoTime());
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                if (rng.nextDouble() < d) {
                    Utils.debug(line);
                }
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

class TimeManager {
    private long start;
    private int count;

    public TimeManager() {
        init();
    }

    public int getCount() {
        return count;
    }

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

    public long getTime() {
        count++;
        return System.nanoTime() - start;
    }

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

    public void init(long start) {
        this.start = start;
        count = 0;
    }

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

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

}


 



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

このページのトップヘ