Approach

最初にSAを試したけど遅くて止めた。
円を一つづつ決める貪欲法を使いました。


円の中心の位置 ランダム
円の色  できるだけ givenImage に近づけるため、 givenImage = (x + drawnImage) / 2 を解いて、中心の位置の givenImage[r][c] * 2 - drawnImage[r][c] の色
円の半径 1づつ広げてスコアが最もよいもの

をこの円用の時間いっぱい繰り返して、最もよい円を選んで、

円の色を (半径の範囲の givenImage の中央値) * 2 - (半径の範囲の drawnImage の平均値)

に変更して、良い方を選ぶ。


勉強になったところ

sum squared error に対しては 平均が良くて、
sum absolute error に対しては中央値が良い。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Random;

public class CirclesMix {

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

private int H;
private int W;
private int N;

private int[][] givenImage;
private int[][] drawnImage;

private long score;
private long bestScore;

private Circle[] solution;
private Circle[] bestSolution;
private Point[] points;

public int[] drawImage(int H, int[] pixels, int N) {
init(H, pixels, N);

solve();

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

return makeSolution();

}

private void init(int h, int[] pixels, int n) {
H = h;
W = pixels.length / H;

givenImage = new int[H][W];
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
givenImage[r][c] = pixels[r * W + c];
}
}

drawnImage = new int[H][W];
for (int r = 0; r < H; ++r) {
Arrays.fill(drawnImage[r], 0);
}

N = n;

solution = new Circle[N];
for (int i = 0; i < N; i++) {
solution[i] = new Circle();
}

score = (long) 1e18;

bestSolution = new Circle[N];
for (int i = 0; i < N; i++) {
bestSolution[i] = new Circle();
}

bestScore = (long) 1e18;

// Utils.debug("time", watch.getSecondString());
initDrss2();
// Utils.debug("time", watch.getSecondString());

points = new Point[(H + 0) * (W + 0)];
for (int r = 0, i = 0; r < H; r++) {
for (int c = 0; c < W; c++, i++) {
points[i] = new Point(c, r);
}
}
ArraysUtils.shuffle(points, rng);
// Utils.debug("time", watch.getSecondString());

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

private static final int[] dr1 = new int[] { -1, 0, 0, 1, };
private static final int[] dc1 = new int[] { 0, -1, 1, 0, };
private IntArray[] drs = new IntArray[1001];
private IntArray[] dcs = new IntArray[1001];

private void initDrss2() {

int r0 = 0;
int c0 = 0;

for (int i = 0; i < drs.length; i++) {
drs[i] = new IntArray();
dcs[i] = new IntArray();
}

LinkedList<Integer> queue = new LinkedList<>();
boolean[][] used = new boolean[1 << 11][1 << 11];
{
used[(1 << 10) + r0][(1 << 10) + c0] = true;
queue.add(r0);
queue.add(c0);
}
for (; !queue.isEmpty();) {
int r = queue.poll().intValue();
int c = queue.poll().intValue();

int dr = r - r0;
int dc = c - c0;
int distance = (int) (Math.sqrt(dr * dr + dc * dc) + 1 - 1e-9);
if (distance > 1000) {
continue;
}

drs[distance].add(r);
dcs[distance].add(c);

for (int i = 0; i < dr1.length; i++) {
int nr = r + dr1[i];
int nc = c + dc1[i];
int ndistance = (int) (Math.sqrt(nr * nr + nc * nc) + 1e-9);
if (ndistance > 1000) {
continue;
}

if (used[(1 << 10) + nr][(1 << 10) + nc]) {
continue;
}
used[(1 << 10) + nr][(1 << 10) + nc] = true;
queue.add(nr);
queue.add(nc);
}

}

assert drs[0].length == 1;
assert drs[1].length == 4 : Utils.toString(drs[1].toArray());

}

private static final int getDiff(int c1, int c2) {
return Math.abs(((c1 >>> 16) & 255) - ((c2 >>> 16) & 255)) + Math.abs(((c1 >>> 8) & 255) - ((c2 >>> 8) & 255)) + Math.abs(((c1 >>> 0) & 255) - ((c2 >>> 0) & 255));
}

private static final int drawOver(int c1, int c2) {
return ((((c1 & 0xFF0000) + (c2 & 0xFF0000)) >>> 1) & 0xFF0000) | ((((c1 & 0x00FF00) + (c2 & 0x00FF00)) >>> 1) & 0x00FF00) | ((((c1 & 0x0000FF) + (c2 & 0x0000FF)) >>> 1) & 0x0000FF);
}

private int[] makeSolution() {
int[] res = new int[4 * N];
for (int i = 0; i < N; i++) {
res[4 * i + 0] = solution[i].r;
res[4 * i + 1] = solution[i].c;
res[4 * i + 2] = solution[i].radius;
res[4 * i + 3] = solution[i].color;
}
return res;
}

private void solve() {
greedy3();
}

class PairComparator implements Comparator<Pair<Long, Circle>> {
private Circle circle;

public void setCircle(Circle circle) {
this.circle = circle;
}

@Override
public int compare(Pair<Long, Circle> o1, Pair<Long, Circle> o2) {
boolean intersect1 = o1.second.intersect(circle);
boolean intersect2 = o2.second.intersect(circle);
if (intersect1) {
if (intersect2) {
} else {
return 1;
}
} else {
if (intersect2) {
return -1;
} else {

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

private void greedy3() {
Pair<Long, Circle>[] circles = new Pair[1 << 20];
for (int i = 0; i < circles.length; i++) {
circles[i] = new Pair<Long, Circle>(Long.MAX_VALUE, new Circle());
}
int circleIndex = 0;
int maxCircleIndex = 0;

// long currentScore = calculateScore(0, -1);
int step = 0;

boolean[][] used = new boolean[H][W];

PairComparator comparator = new PairComparator();

int mask = (1 << 4) - 1;

int pointIndex = -1;

double[] timelimits = new double[N];
double startTime = watch.getSecond();
double endTime = 9.5;
for (int i = 0; i < N; i++) {
timelimits[i] = startTime + (endTime - startTime) * (i + 1) / N;
}

for (int i = 0; i < N; i++) {

bestScore = (long) 1e18;

for (int loop = 0;; loop++, step++) {
if ((loop & mask) == mask) {
if (watch.getSecond() > timelimits[i]) {
break;
}
}

pointIndex++;
if (pointIndex >= points.length) {
pointIndex = 0;
}
solution[i].r = points[pointIndex].y;
solution[i].c = points[pointIndex].x;

if (used[solution[i].r][solution[i].c]) {
continue;
}
used[solution[i].r][solution[i].c] = true;

int colorR = solution[i].r;
int colorC = solution[i].c;

int givenRed = (givenImage[colorR][colorC] >>> 16) & 255;
int givenGreen = (givenImage[colorR][colorC] >>> 8) & 255;
int givenBlue = (givenImage[colorR][colorC] >>> 0) & 255;

int drawnRed = (drawnImage[colorR][colorC] >>> 16) & 255;
int drawnGreen = (drawnImage[colorR][colorC] >>> 8) & 255;
int drawnBlue = (drawnImage[colorR][colorC] >>> 0) & 255;

int red = givenRed * 2 - drawnRed;
red = Math.max(0, Math.min(255, red));
int green = givenGreen * 2 - drawnGreen;
green = Math.max(0, Math.min(255, green));
int blue = givenBlue * 2 - drawnBlue;
blue = Math.max(0, Math.min(255, blue));
solution[i].color = (red << 16) | (green << 8) | (blue);

long delta = calculateScoreEachRadius(i);

circles[circleIndex].first = delta;
Circle second = circles[circleIndex].second;
second.r = solution[i].r;
second.c = solution[i].c;
second.radius = solution[i].radius;
second.color = solution[i].color;
circleIndex++;
}
{

ArraysUtils.select(circles, 0, circleIndex, 0);
Pair<Long, Circle> pair = circles[0];
solution[i].r = pair.second.r;
solution[i].c = pair.second.c;
solution[i].radius = pair.second.radius;

int medianGiven = medianColor(givenImage, solution[i].r, solution[i].c, pair.second.radius);
int meanDrawn = meanColor(drawnImage, solution[i].r, solution[i].c, pair.second.radius);

int givenRed = (medianGiven >>> 16) & 255;
int givenGreen = (medianGiven >>> 8) & 255;
int givenBlue = (medianGiven >>> 0) & 255;

int drawnRed = (meanDrawn >>> 16) & 255;
int drawnGreen = (meanDrawn >>> 8) & 255;
int drawnBlue = (meanDrawn >>> 0) & 255;

int red = givenRed * 2 - drawnRed;
red = Math.max(0, Math.min(255, red));
int green = givenGreen * 2 - drawnGreen;
green = Math.max(0, Math.min(255, green));
int blue = givenBlue * 2 - drawnBlue;
blue = Math.max(0, Math.min(255, blue));

solution[i].color = (red << 16) | (green << 8) | (blue);

long delta = calculateScore(i);

circles[circleIndex].first = delta;
Circle second = circles[circleIndex].second;
second.r = solution[i].r;
second.c = solution[i].c;
second.radius = solution[i].radius;
second.color = solution[i].color;
circleIndex++;
}

maxCircleIndex = Math.max(maxCircleIndex, circleIndex);
ArraysUtils.select(circles, 0, circleIndex, 0);
Pair<Long, Circle> pair = circles[0];
Circle second = pair.second;
solution[i].r = second.r;
solution[i].c = second.c;
solution[i].radius = second.radius;
solution[i].color = second.color;
// bestScore = pair.first.longValue();
comparator.setCircle(solution[i]);
ArraysUtils.select(circles, 0, circleIndex, Math.min(circleIndex, N + 10 - i), comparator);
int nextCircleIndex = Math.min(circleIndex, N + 10 - i);
Arrays.sort(circles, 0, nextCircleIndex, comparator);
for (int j = 0; j < nextCircleIndex; j++) {
if (circles[j].second.intersect(solution[i])) {
nextCircleIndex = j;
break;
}
}
for (int j = nextCircleIndex; j < circleIndex; j++) {
used[circles[j].second.r][circles[j].second.c] = false;
}
circleIndex = nextCircleIndex;
// currentScore += bestScore;

update(i);

// if (i < 10 || Integer.bitCount(i) == 1 || i > N - 5) {
// Utils.debug("i", i, "step", step, "currentScore", currentScore);
// }
}

score = calculateScore();
Utils.debug("step", step, "score", score, "maxCircleIndex", maxCircleIndex);

}

private IntArray redForMedian = new IntArray(1 << 20);
private IntArray greenForMedian = new IntArray(1 << 20);
private IntArray blueForMedian = new IntArray(1 << 20);

private int medianColor(int[][] given, int colorR, int colorC, int radius) {
redForMedian.clear();
greenForMedian.clear();
blueForMedian.clear();
for (int r = Math.max(colorR - radius, 0); r <= Math.min(colorR + radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(radius) - p2(colorR - r));
for (int c = Math.max(colorC - dc, 0); c <= Math.min(colorC + dc, W - 1); c++) {
redForMedian.add((given[r][c] >>> 16) & 255);
greenForMedian.add((given[r][c] >>> 8) & 255);
blueForMedian.add((given[r][c] >>> 0) & 255);
}
}
ArraysUtils.select(redForMedian.values, 0, redForMedian.length, redForMedian.length >>> 1);
ArraysUtils.select(greenForMedian.values, 0, greenForMedian.length, greenForMedian.length >>> 1);
ArraysUtils.select(blueForMedian.values, 0, blueForMedian.length, blueForMedian.length >>> 1);
int medianRed = redForMedian.values[redForMedian.length >>> 1];
int medianGreen = greenForMedian.values[greenForMedian.length >>> 1];
int medianBlue = blueForMedian.values[blueForMedian.length >>> 1];
return (medianRed << 16) | (medianGreen << 8) | (medianBlue);
}

private MeanHelper redForMean = new MeanHelper();
private MeanHelper greenForMean = new MeanHelper();
private MeanHelper blueForMean = new MeanHelper();

private int meanColor(int[][] given, int colorR, int colorC, int radius) {
redForMean.clear();
greenForMean.clear();
blueForMean.clear();
for (int r = Math.max(colorR - radius, 0); r <= Math.min(colorR + radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(radius) - p2(colorR - r));
for (int c = Math.max(colorC - dc, 0); c <= Math.min(colorC + dc, W - 1); c++) {
redForMean.add((given[r][c] >>> 16) & 255);
greenForMean.add((given[r][c] >>> 8) & 255);
blueForMean.add((given[r][c] >>> 0) & 255);
}
}
int meanRed = (int) redForMean.mean();
int meanGreen = (int) greenForMean.mean();
int meanBlue = (int) blueForMean.mean();
return (meanRed << 16) | (meanGreen << 8) | (meanBlue);
}

private int p2(int t) {
return t * t;
}

private long calculateScore() {
for (int r = 0; r < H; ++r) {
Arrays.fill(drawnImage[r], 0);
}
for (int i = 0; i < N; ++i) {
for (int r = Math.max(solution[i].r - solution[i].radius, 0); r <= Math.min(solution[i].r + solution[i].radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
for (int c = Math.max(solution[i].c - dc, 0); c <= Math.min(solution[i].c + dc, W - 1); c++) {
if (p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius)) {
drawnImage[r][c] = drawOver(drawnImage[r][c], solution[i].color);
}
}
}
}
long diff = 0;
for (int r = 0; r < H; ++r) {
for (int c = 0; c < W; ++c) {
diff += getDiff(givenImage[r][c], drawnImage[r][c]);
}
}
return diff;
}

private long calculateScore(int from, int to) {
for (int r = 0; r < H; ++r) {
Arrays.fill(drawnImage[r], 0);
}
for (int i = from; i <= to; ++i) {
for (int r = Math.max(solution[i].r - solution[i].radius, 0); r <= Math.min(solution[i].r + solution[i].radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
for (int c = Math.max(solution[i].c - dc, 0); c <= Math.min(solution[i].c + dc, W - 1); c++) {
if (p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius)) {
drawnImage[r][c] = drawOver(drawnImage[r][c], solution[i].color);
}
}
}
}
long diff = 0;
for (int r = 0; r < H; ++r) {
for (int c = 0; c < W; ++c) {
diff += getDiff(givenImage[r][c], drawnImage[r][c]);
}
}
return diff;
}

private void update(int i) {
int minR = Math.max(solution[i].r - solution[i].radius, 0);
int maxR = Math.min(solution[i].r + solution[i].radius, H - 1);
for (int r = minR; r <= maxR; r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
int minC = Math.max(solution[i].c - dc, 0);
int maxC = Math.min(solution[i].c + dc, W - 1);
for (int c = minC; c <= maxC; c++) {
assert p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius);
drawnImage[r][c] = drawOver(drawnImage[r][c], solution[i].color);
}
}
}

private long calculateScore(int i) {
long diff = 0;
int minR = Math.max(solution[i].r - solution[i].radius, 0);
int maxR = Math.min(solution[i].r + solution[i].radius, H - 1);
for (int r = minR; r <= maxR; r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
int minC = Math.max(solution[i].c - dc, 0);
int maxC = Math.min(solution[i].c + dc, W - 1);
for (int c = minC; c <= maxC; c++) {
assert p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius);
diff -= getDiff(givenImage[r][c], drawnImage[r][c]);
diff += getDiff(givenImage[r][c], drawOver(drawnImage[r][c], solution[i].color));
}
}
return diff;
}

private long calculateScoreEachRadius(int i) {
int r0 = solution[i].r;
int c0 = solution[i].c;
int color0 = solution[i].color;

long diff = 0;
long bestDiff = (long) 1e18;
int bestRadius = 0;
for (int radius = 0; radius < drs.length; radius++) {
if (radius > bestRadius + 3) {
break;
}

IntArray dr = drs[radius];
IntArray dc = dcs[radius];

for (int d = 0; d < dr.length; d++) {
int r = r0 + dr.values[d];
int c = c0 + dc.values[d];
if (r < 0 || r >= H) {
continue;
}
if (c < 0 || c >= W) {
continue;
}

diff -= getDiff(givenImage[r][c], drawnImage[r][c]);
diff += getDiff(givenImage[r][c], drawOver(drawnImage[r][c], color0));

}

if (diff < bestDiff) {
bestDiff = diff;
bestRadius = radius;
}

}

solution[i].radius = bestRadius;
return bestDiff;
}

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

int H = Integer.parseInt(br.readLine());

int S = Integer.parseInt(br.readLine());
int[] pixels = new int[S];
for (int i = 0; i < S; ++i) {
pixels[i] = Integer.parseInt(br.readLine());
}

int N = Integer.parseInt(br.readLine());

CirclesMix cm = new CirclesMix();
int[] ret = cm.drawImage(H, pixels, N);

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

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 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 Circle implements Comparable<Circle> {
int r;
int c;
int radius;
int color;

@Override
public int compareTo(Circle o) {
if (radius > o.radius) {
return -1;
}
if (radius < o.radius) {
return 1;
}
return 0;
}

public boolean intersect(Circle circle) {
int dr = r - circle.r;
int dc = c - circle.c;
return Math.sqrt(dr * dr + dc * dc) <= radius + circle.radius;
}
}

class ArraysUtils {
private ArraysUtils() {
}

public static final void shuffle(int[] a, Random rng) {
for (int i = a.length - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
ArraysUtils.swap(a, i, j);
}
}

public static final void shuffle(int[] a, XorShift rng) {
for (int i = a.length - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
ArraysUtils.swap(a, i, j);
}
}

public static final void shuffle(Object[] a, XorShift rng) {
for (int i = a.length - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
ArraysUtils.swap(a, i, j);
}
}

private static final void select0(int[] a, int l, int r, int k) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

private static final void select0(double[] a, int l, int r, int k) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

private static final void select0(Comparable[] a, int l, int r, int k) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

private static final <T> void select0(T[] a, int l, int r, int k, Comparator<T> comparator) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r, comparator);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

public static final void select(int[] a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final void select(double[] a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final void select(Comparable[] a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final <T> void select(T[] a, int startInclusive, int endExclusive, int k, Comparator<T> comparator) {
select0(a, startInclusive, endExclusive - 1, k, comparator);
}

public static final void swap(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}

public static final void swap(double[] a, int i, int j) {
double swap = a[i];
a[i] = a[j];
a[j] = swap;
}

public static final void swap(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

public static final void sort3(int[] a, int i, int j, int k) {
if (a[i] > a[j]) {
swap(a, i, j);
}
if (a[i] > a[k]) {
swap(a, i, k);
}
if (a[j] > a[k]) {
swap(a, j, k);
}
}

public static final void sort3(double[] a, int i, int j, int k) {
if (a[i] > a[j]) {
swap(a, i, j);
}
if (a[i] > a[k]) {
swap(a, i, k);
}
if (a[j] > a[k]) {
swap(a, j, k);
}
}

public static final void sort3(Comparable[] a, int i, int j, int k) {
if (a[i].compareTo(a[j]) > 0) {
swap(a, i, j);
}
if (a[i].compareTo(a[k]) > 0) {
swap(a, i, k);
}
if (a[j].compareTo(a[k]) > 0) {
swap(a, j, k);
}
}

public static final <T> void sort3(T[] a, int i, int j, int k, Comparator<T> comparator) {
if (comparator.compare(a[i], a[j]) > 0) {
swap(a, i, j);
}
if (comparator.compare(a[i], a[k]) > 0) {
swap(a, i, k);
}
if (comparator.compare(a[j], a[k]) > 0) {
swap(a, j, k);
}
}

public static final int partition3(int[] 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;
int v = a[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; a[++i] < v;) {
}
for (; a[--j] > v;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final int partition3(double[] 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;
double v = a[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; a[++i] < v;) {
}
for (; a[--j] > v;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final int partition3(Comparable[] 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;
Comparable v = a[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; a[++i].compareTo(v) < 0;) {
}
for (; a[--j].compareTo(v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final <T> int partition3(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[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; comparator.compare(a[++i], v) < 0;) {
}
for (; comparator.compare(a[--j], v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

}

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 Point implements Comparable<Point> {

public int x;
public int y;

public Point() {
this(0, 0);
}

public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}

public Point add(Point point) {
return new Point(x + point.x, y + point.y);
}

public Point subtract(Point point) {
return new Point(x - point.x, y - point.y);
}

public Point multiply(int a) {
return new Point(a * x, a * y);
}

public Point divide(int a) {
return new Point(x / a, y / a);
}

public double cross(Point point) {
return x * point.y - y * point.x;
}

public Point operator(Point a) {
return new Point(x * a.x - y * a.y, x * a.y + y * a.x);
}

@Override
public int compareTo(Point o) {
if (x == o.x) {
if (y == o.y) {
return 0;
} else if (y < o.y) {
return -1;
} else {
return 1;
}
} else if (x < o.x) {
return -1;
} else {
return 1;
}
}

@Override
public String toString() {
return "(" + x + "," + y + ")";
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
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;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

}

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

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 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 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;
description = null;
}

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

public void setDescription(String description) {
if (this.description != null) {
if (this.description.hashCode() != description.hashCode()) {
throw new AssertionError();
}
if (!this.description.equals(description)) {
throw new AssertionError();
}
} else {
this.description = description;
}
}

public String getDescription() {
return description;
}
}