Approach 2点を交換する焼きなまし法です。

  • 脳死SA : 98以上
  • 直前の Line の位置から左右8以内の位置に制限する + 10%の確率でその左右8以内の位置で最もスコアが良くなる位置と交換 : 99以上(試行回数が3分の1になってしまったので多分ですけど。)



source code

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

public class LineUp {
private int R;
private int C;
private int[] heights;
private IntSet[] rToPerformerIndexes;
private int[][] bestRxcToPerformerIndex;
private int[][] idealHeights;

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

private double score;
private double bestScore;

private long SSEHeight = 0;
private long SAEDist = 0;
private long bestSSEHeight = 0;
private long bestSAEDist = 0;

public int[] getLineup(int[] heights, int[] arrangements) {
init(heights, arrangements);
solve();
return makeSolution();
}

private void init(int[] heights, int[] arrangements) {
C = heights.length;
this.heights = heights;
R = arrangements.length / C;
idealHeights = new int[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
idealHeights[r][c] = arrangements[r * C + c];
}
}
rToPerformerIndexes = new IntSet[R];
for (int r = 0; r < R; r++) {
rToPerformerIndexes[r] = new IntSet(C);
for (int c = 0; c < C; c++) {
rToPerformerIndexes[r].add(c);
}
}

score = calculateScore();

bestRxcToPerformerIndex = new int[R][C];
bestScore = 1e9;
saveBest();
}

private void solve() {
double numRestart = 1;
double startTemperature = 3;
double endTemperature = 0;
double startTime = watch.getSecond();
double endTime = 9.5;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTemperature = startTemperature + (endTemperature - startTemperature) * restart / numRestart;
sa.endTemperature = endTemperature;
sa.startTime = startTime + (endTime - startTime) * restart / numRestart;
sa.endTime = startTime + (endTime - startTime) * (restart + 1) / numRestart;
SA();
loadBest();
}
}

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("%7.5f", score), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), String.format("%.6f", sa.startTemperature), String.format("%.6f", sa.endTemperature));
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("%7.5f", score), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), String.format("%.6f", sa.startTemperature), String.format("%.6f", sa.endTemperature));
}
}

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

private void mutate() {
double random = 1.1 * rng.nextDouble();
if (random < 1) {
swapNear();
} else {
swapNearBest();
}
}

private void swap() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2;
while ((c2 = (int) (C * rng.nextDouble())) == c) {
}

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = 0;
deltaSSEHeight -= SEHeight(r, c, pi);
deltaSSEHeight -= SEHeight(r, c2, pi2);
deltaSSEHeight += SEHeight(r, c, pi2);
deltaSSEHeight += SEHeight(r, c2, pi);

long deltaSAEDist = 0;
deltaSAEDist -= AEDist(r, c, pi);
deltaSAEDist -= AEDist(r, c2, pi2);
deltaSAEDist += AEDist(r, c, pi2);
deltaSAEDist += AEDist(r, c2, pi);

double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight;
SAEDist += deltaSAEDist;
score += deltaScore2;
saveBest();
} else {
}
}

private void swapNear() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int pi = getPerformerIndex(r, c);
int prevC = getC(r - 1, pi);
int dc = 8;
int cl = Math.max(0, prevC - dc);
int cr = Math.min(prevC + dc, C - 1);
int c2 = (int) sa.interpolate(cl, cr + 1, rng.nextDouble());
if (c2 == c) {
return;
}

int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = -SEHeight(r, c, pi) - SEHeight(r, c2, pi2) + SEHeight(r, c, pi2) + SEHeight(r, c2, pi);
long deltaSAEDist = -AEDist(r, c, pi) - AEDist(r, c2, pi2) + AEDist(r, c, pi2) + AEDist(r, c2, pi);
double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight;
SAEDist += deltaSAEDist;
score += deltaScore2;
saveBest();
}
}

private void swapNearBest() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int pi = getPerformerIndex(r, c);
int prevC = getC(r - 1, pi);
int dc = 8;
int cl = Math.max(0, prevC - dc);
int cr = Math.min(prevC + dc, C - 1);
double bestdeltaScore = 1e99;
long bestSSE = 0;
long bestSAE = 0;
int bestc2 = -1;
for (int c2 = cl; c2 <= cr; c2++) {
if (c2 == c) {
continue;
}

int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = -SEHeight(r, c, pi) - SEHeight(r, c2, pi2) + SEHeight(r, c, pi2) + SEHeight(r, c2, pi);
long deltaSAEDist = -AEDist(r, c, pi) - AEDist(r, c2, pi2) + AEDist(r, c, pi2) + AEDist(r, c2, pi);
double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (deltaScore2 < bestdeltaScore) {
bestdeltaScore = deltaScore2;
bestSSE = deltaSSEHeight;
bestSAE = deltaSAEDist;
bestc2 = c2;
}
}
if (sa.accept(bestdeltaScore)) {
swap(r, c, bestc2);
SSEHeight += bestSSE;
SAEDist += bestSAE;
score += bestdeltaScore;
saveBest();
}
}

private void swapCandidate2() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2;
while ((c2 = (int) (C * rng.nextDouble())) == c) {
}
int c3 = c;
while (c3 == c || c3 == c2) {
c3 = (int) (C * rng.nextDouble());
}

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
int pi3 = getPerformerIndex(r, c3);

long deltaSSEHeight2 = 0;
deltaSSEHeight2 -= SEHeight(r, c, pi);
deltaSSEHeight2 -= SEHeight(r, c2, pi2);
deltaSSEHeight2 += SEHeight(r, c, pi2);
deltaSSEHeight2 += SEHeight(r, c2, pi);

long deltaSAEDist2 = 0;
deltaSAEDist2 -= AEDist(r, c, pi);
deltaSAEDist2 -= AEDist(r, c2, pi2);
deltaSAEDist2 += AEDist(r, c, pi2);
deltaSAEDist2 += AEDist(r, c2, pi);

long deltaSSEHeight3 = 0;
deltaSSEHeight3 -= SEHeight(r, c, pi);
deltaSSEHeight3 -= SEHeight(r, c3, pi3);
deltaSSEHeight3 += SEHeight(r, c, pi3);
deltaSSEHeight3 += SEHeight(r, c3, pi);

long deltaSAEDist3 = 0;
deltaSAEDist3 -= AEDist(r, c, pi);
deltaSAEDist3 -= AEDist(r, c3, pi3);
deltaSAEDist3 += AEDist(r, c, pi3);
deltaSAEDist3 += AEDist(r, c3, pi);

double newScore2 = SAEDist + deltaSAEDist2 + Math.sqrt(SSEHeight + deltaSSEHeight2);
double deltaScore2 = newScore2 - score;

double newScore3 = SAEDist + deltaSAEDist3 + Math.sqrt(SSEHeight + deltaSSEHeight3);
double deltaScore3 = newScore3 - score;

if (deltaScore2 < deltaScore3) {
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight2;
SAEDist += deltaSAEDist2;
score += deltaScore2;
saveBest();
} else {
}
} else {
if (sa.accept(deltaScore3)) {
swap(r, c, c3);
SSEHeight += deltaSSEHeight3;
SAEDist += deltaSAEDist3;
score += deltaScore3;
saveBest();
} else {
}
}

}

private void swapCandidate3() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2;
while ((c2 = (int) (C * rng.nextDouble())) == c) {
}
int c3 = c;
while (c3 == c || c3 == c2) {
c3 = (int) (C * rng.nextDouble());
}
int c4 = c;
while (c4 == c || c4 == c2 || c4 == c3) {
c4 = (int) (C * rng.nextDouble());
}

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
int pi3 = getPerformerIndex(r, c3);
int pi4 = getPerformerIndex(r, c4);

long deltaSSEHeight2 = 0;
deltaSSEHeight2 -= SEHeight(r, c, pi);
deltaSSEHeight2 -= SEHeight(r, c2, pi2);
deltaSSEHeight2 += SEHeight(r, c, pi2);
deltaSSEHeight2 += SEHeight(r, c2, pi);

long deltaSAEDist2 = 0;
deltaSAEDist2 -= AEDist(r, c, pi);
deltaSAEDist2 -= AEDist(r, c2, pi2);
deltaSAEDist2 += AEDist(r, c, pi2);
deltaSAEDist2 += AEDist(r, c2, pi);

long deltaSSEHeight3 = 0;
deltaSSEHeight3 -= SEHeight(r, c, pi);
deltaSSEHeight3 -= SEHeight(r, c3, pi3);
deltaSSEHeight3 += SEHeight(r, c, pi3);
deltaSSEHeight3 += SEHeight(r, c3, pi);

long deltaSAEDist3 = 0;
deltaSAEDist3 -= AEDist(r, c, pi);
deltaSAEDist3 -= AEDist(r, c3, pi3);
deltaSAEDist3 += AEDist(r, c, pi3);
deltaSAEDist3 += AEDist(r, c3, pi);

long deltaSSEHeight4 = 0;
deltaSSEHeight4 -= SEHeight(r, c, pi);
deltaSSEHeight4 -= SEHeight(r, c4, pi4);
deltaSSEHeight4 += SEHeight(r, c, pi4);
deltaSSEHeight4 += SEHeight(r, c4, pi);

long deltaSAEDist4 = 0;
deltaSAEDist4 -= AEDist(r, c, pi);
deltaSAEDist4 -= AEDist(r, c4, pi4);
deltaSAEDist4 += AEDist(r, c, pi4);
deltaSAEDist4 += AEDist(r, c4, pi);

double newScore2 = SAEDist + deltaSAEDist2 + Math.sqrt(SSEHeight + deltaSSEHeight2);
double deltaScore2 = newScore2 - score;

double newScore3 = SAEDist + deltaSAEDist3 + Math.sqrt(SSEHeight + deltaSSEHeight3);
double deltaScore3 = newScore3 - score;

double newScore4 = SAEDist + deltaSAEDist4 + Math.sqrt(SSEHeight + deltaSSEHeight4);
double deltaScore4 = newScore4 - score;

if (deltaScore2 < deltaScore3) {
if (deltaScore2 < deltaScore4) {
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight2;
SAEDist += deltaSAEDist2;
score += deltaScore2;
saveBest();
} else {
}
} else {
if (sa.accept(deltaScore4)) {
swap(r, c, c4);
SSEHeight += deltaSSEHeight4;
SAEDist += deltaSAEDist4;
score += deltaScore4;
saveBest();
} else {
}
}
} else {
if (deltaScore3 < deltaScore4) {
if (sa.accept(deltaScore3)) {
swap(r, c, c3);
SSEHeight += deltaSSEHeight3;
SAEDist += deltaSAEDist3;
score += deltaScore3;
saveBest();
} else {
}
} else {
if (sa.accept(deltaScore4)) {
swap(r, c, c4);
SSEHeight += deltaSSEHeight4;
SAEDist += deltaSAEDist4;
score += deltaScore4;
saveBest();
} else {
}
}
}

}

private void saveBest() {
if (score < bestScore) {
bestScore = score;
bestSSEHeight = SSEHeight;
bestSAEDist = SAEDist;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
bestRxcToPerformerIndex[r][c] = rToPerformerIndexes[r].get(c);
}
}
}
}

private void loadBest() {
score = bestScore;
SSEHeight = bestSSEHeight;
SAEDist = bestSAEDist;
for (int r = 0; r < R; r++) {
rToPerformerIndexes[r].clear();
for (int c = 0; c < C; c++) {
rToPerformerIndexes[r].add(bestRxcToPerformerIndex[r][c]);
}
}
}

private void prevPos() {
int r = 1 + (int) ((R - 1) * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2 = getC(r - 1, getPerformerIndex(r, c));

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = 0;
deltaSSEHeight -= SEHeight(r, c, pi);
deltaSSEHeight -= SEHeight(r, c2, pi2);
deltaSSEHeight += SEHeight(r, c, pi2);
deltaSSEHeight += SEHeight(r, c2, pi);

long deltaSAEDist = 0;
deltaSAEDist -= AEDist(r, c, pi);
deltaSAEDist -= AEDist(r, c2, pi2);
deltaSAEDist += AEDist(r, c, pi2);
deltaSAEDist += AEDist(r, c2, pi);

double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight;
SAEDist += deltaSAEDist;
score += deltaScore2;
} else {
}
}

private double calculateScore() {
SAEDist = 0;
SSEHeight = 0;

for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
int pi = getPerformerIndex(r, c);
SSEHeight += SEHeight(r, c, pi);
SAEDist += AEDistPrev(r, c, pi);
}
}
return SAEDist + Math.sqrt(SSEHeight);
}

private long AEDist(int r, int c, int pi) {
return AEDistNext(r, c, pi) + AEDistPrev(r, c, pi);
}

private int AEDistPrev(int r, int c, int pi) {
int prevC = getC(r - 1, pi);
return Math.abs(prevC - c);
}

private int AEDistNext(int r, int c, int pi) {
if (r + 1 >= R) {
return 0;
}
int nextC = getC(r + 1, pi);
return Math.abs(nextC - c);
}

private int getPerformerIndex(int r, int c) {
return rToPerformerIndexes[r].get(c);
}

private int getC(int r, int performerIndex) {
if (r == -1) {
return performerIndex;
}
if (r >= R) {
throw new AssertionError();
}
return rToPerformerIndexes[r].indexOf(performerIndex);
}

private long SEHeight(int r, int c, int pi) {
long err = diffHeight(r, c, pi);
return err * err;
}

private long diffHeight(int r, int c, int performerIndex) {
return heights[performerIndex] - idealHeights[r][c];
}

private void swap(int r, int c, int c2) {
rToPerformerIndexes[r].swap(c, c2);
}

private int[] makeSolution() {
int[] ret = new int[R * C];
for (int r = 0, i = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
ret[i++] = getPerformerIndex(r, c);
}
}
return ret;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
int[] heights = new int[Integer.parseInt(br.readLine())];
for (int i = 0; i < heights.length; ++i) {
heights[i] = Integer.parseInt(br.readLine());
}
int[] arrangements = new int[Integer.parseInt(br.readLine())];
for (int i = 0; i < arrangements.length; ++i) {
arrangements[i] = Integer.parseInt(br.readLine());
}
LineUp sol = new LineUp();
int[] ret = sol.getLineup(heights, arrangements);
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 = 40;
public double endTemperature = 1e9;
public double expTemperature = 1;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 101;
public double endRange = 3;
public double range = startRange;

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

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 ? LineUp.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

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

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

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

public void updateTemperature() {
boolean useExp = !true;
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;
}
}

public void updateRange() {
}

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

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

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

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++;
lastAcceptIterations = numIterations;
return true;
}

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

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

public boolean acceptS(double deltaScore) {
validIterations++;
if (deltaScore < 1e-9) {
acceptIterations++;
lastAcceptIterations = numIterations;
return true;
}
if (-deltaScore * inverseTemperature < -10) {
return false;
}
if (log[LineUp.rng.nextInt() & 32767] < -deltaScore * inverseTemperature) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
lastAcceptIterations = numIterations;
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 long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

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

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

}

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