Approach beam search を使いました。
- ケーキを8個以下に切るときは、すべての切り方を試す。そうでないときは、長方形に切る。
- beam width : 切り方により, 10〜数千まで変わる。
- 評価関数 : 理想的な切り方ができたときのスコアにした。あと、親のスコアをちょっと足してみた、効果はなかった。
- 切るケーキの選び方 : 小さいものを選んだ。スコアを早く確定するのが良いらしい。
難しかったところ
- 高速化しても(beam width を増やしても)精度が良くならなかった。
- 重複の除去もうまくいってなかった。
- たまに、切れない形になって、0点を出す。
source code
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class CakeSharing { private static final double d = 0.01; private int count = 0; private int R; private int C; private int numCakes; private ArrayListpieces2; private ArrayList cuts2; public String[] cut(String[] roses, int NP) { init(roses, NP); solve(); Utils.debug("count", count); return makeSolution(); } TwoDimensionalCumulativeSum cumulativeSum; private void init(String[] roses, int NP) { Constants.watch.init(); numCakes = NP; R = roses.length; H = R; C = roses[0].length(); W = C; Utils.debug("R", R, "C", C, "NP", NP); this.roses = new char[R][C]; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { char charAt = roses[r].charAt(c); this.roses[r][c] = charAt; } } { int[][] values = new int[R][C]; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { values[r][c] = this.roses[r][c] == 'R' ? 1 : 0; } } cumulativeSum = new TwoDimensionalCumulativeSum(values); } pieces2 = new ArrayList<>(); cuts2 = new ArrayList<>(); ArrayList convexHull = new ArrayList<>(); convexHull.add(new Point(0, 0)); convexHull.add(new Point(0, R)); convexHull.add(new Point(C, R)); convexHull.add(new Point(C, 0)); pieces2.add(new Piece(convexHull, true)); } private void solve() { ArrayList beamsearch = beamsearch(numCakes - 1, 20); set(beamsearch, 0); } private ArrayList beamsearch(int maxDepth, int maxBeamWidth) { double meanArea = R * C / (double) numCakes; maxBeamWidth = 10000; MeanHelper widthHelper = new MeanHelper(); ArrayList currents = new ArrayList<>(); ArrayList nexts = new ArrayList<>(); currents.add(new State()); double[] timeLimits = getTimeLimits(maxDepth); for (int depth = 0; depth < maxDepth; depth++) { int beamWidth = Math.min(maxBeamWidth, currents.size()); Collections.sort(currents); widthLoop: for (int width = 0;; width++) { if (width >= beamWidth) { widthHelper.add(width); break; } State currentState = currents.get(width); if (depth % 10 == 0) { if (width == 0) { if (currentState != null) { Utils.debug("depth", depth, "score", currentState.score, "currents.size()", currents.size()); } } } set(reverse(toList(currentState)), 0); int maxIndex = getPieceIndex(); Piece piece = pieces2.get(maxIndex); int numCakes0 = (int) Math.round(piece.getPieceArea() / meanArea); MeanHelper areaHelper = new MeanHelper(); MeanHelper roseHelper = new MeanHelper(); for (Piece piece2 : pieces2) { if (piece2 == piece) { continue; } double area = piece2.getPieceArea(); int numCakes3 = (int) (Math.round(area / meanArea)); minAreaSD(area, numCakes3); areaHelper.add(this.area[0], number[0]); areaHelper.add(this.area[1], number[1]); int rose = piece2.countRose(); minRoseSD(rose, numCakes3); roseHelper.add(this.area[0], number[0]); roseHelper.add(this.area[1], number[1]); } if (numCakes0 > 8 && piece.isRectangle) { int maxX = (int) -1e9; int minX = (int) 1e9; int maxY = (int) -1e9; int minY = (int) 1e9; for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); maxX = Math.max(maxX, point.x); minX = Math.min(minX, point.x); maxY = Math.max(maxY, point.y); minY = Math.min(minY, point.y); } for (int r = minY + 1; r < maxY; r++) { Point p1 = new Point(minX, r); Point p2 = new Point(maxX, r); simulateCut(maxIndex, p1, p2); if (areaAndRose[0] == -1) { continue; } if (pruning(meanArea, areaHelper)) { continue; } int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea)); int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea)); double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2); setNext(nexts, currentState, piece, p1, p2, expectedScore); if (Constants.watch.getSecond() > timeLimits[depth]) { widthHelper.add(width); break widthLoop; } } for (int c = minX + 1; c < maxX; c++) { Point p1 = new Point(c, minY); Point p2 = new Point(c, maxY); simulateCut(maxIndex, p1, p2); if (areaAndRose[0] == -1) { continue; } if (pruning(meanArea, areaHelper)) { continue; } int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea)); int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea)); double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2); setNext(nexts, currentState, piece, p1, p2, expectedScore); if (Constants.watch.getSecond() > timeLimits[depth]) { widthHelper.add(width); break widthLoop; } } } else { for (int i = 0; i < piece.pointSize(); i++) { Point p1 = piece.getPoint(i); for (int j = i + 1; j < piece.pointSize(); j++) { Point p2 = piece.getPoint(j); if (numCakes0 > 8) { if (p2.x != p1.x && p2.y != p1.y) { continue; } } simulateCut(maxIndex, p1, p2); if (areaAndRose[0] == -1) { continue; } if (pruning(meanArea, areaHelper)) { continue; } int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea)); int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea)); double expectedScore = calculateExpectedScore(areaHelper, roseHelper, numCakes1, numCakes2); setNext(nexts, currentState, piece, p1, p2, expectedScore); if (Constants.watch.getSecond() > timeLimits[depth]) { widthHelper.add(width); break widthLoop; } } } } } { ArrayList swap = currents; currents = nexts; nexts = swap; } nexts.clear(); } Utils.debug("mean width", widthHelper.mean()); Collections.sort(currents); State best = currents.get(0); Utils.debug("time", Constants.watch.getSecondString(), "score", best.score); return reverse(toList(best)); } private boolean pruning(double meanArea, MeanHelper areaHelper) { int numCakes1p = (int) (Math.round(d + areaAndRose[0] / meanArea)); int numCakes1m = (int) (Math.round(-d + areaAndRose[0] / meanArea)); if (numCakes1p != numCakes1m) { count++; return true; } int numCakes1 = (int) (Math.round(areaAndRose[0] / meanArea)); int numCakes2p = (int) (Math.round(d + areaAndRose[2] / meanArea)); int numCakes2m = (int) (Math.round(-d + areaAndRose[2] / meanArea)); if (numCakes2p != numCakes2m) { count++; return true; } int numCakes2 = (int) (Math.round(areaAndRose[2] / meanArea)); if (areaHelper.count() + numCakes1 + numCakes2 != numCakes) { return true; } if (numCakes1 < 1) { return true; } if (numCakes2 < 1) { return true; } return false; } private double calculateExpectedScore(MeanHelper areaHelper, MeanHelper roseHelper, int numCakes1, int numCakes2) { double expectedScore = 0; { minAreaSD(areaAndRose[0], numCakes1); areaHelper.add(this.area[0], number[0]); areaHelper.add(this.area[1], number[1]); minAreaSD(areaAndRose[2], numCakes2); areaHelper.add(this.area[0], number[0]); areaHelper.add(this.area[1], number[1]); double sdArea = areaHelper.standardDeviation(1e9); areaHelper.add(this.area[0], -number[0]); areaHelper.add(this.area[1], -number[1]); minAreaSD(areaAndRose[0], numCakes1); areaHelper.add(this.area[0], -number[0]); areaHelper.add(this.area[1], -number[1]); minRoseSD((int) areaAndRose[1], numCakes1); roseHelper.add(this.area[0], number[0]); roseHelper.add(this.area[1], number[1]); minRoseSD((int) areaAndRose[3], numCakes2); roseHelper.add(this.area[0], number[0]); roseHelper.add(this.area[1], number[1]); double sdRose = roseHelper.standardDeviation(1e9); roseHelper.add(this.area[0], -number[0]); roseHelper.add(this.area[1], -number[1]); minRoseSD((int) areaAndRose[1], numCakes1); roseHelper.add(this.area[0], -number[0]); roseHelper.add(this.area[1], -number[1]); expectedScore = (1.0 + sdArea) * (1.0 + sdRose); if (Double.isNaN(expectedScore)) { expectedScore = 1e9; } } return expectedScore; } private void setNext(ArrayList nexts, State currentState, Piece piece, Point p1, Point p2, double expectedScore) { { State nextState = new State(); nextState.parent = currentState; nextState.piece = piece; nextState.cut = new Cut(p1, p2); nextState.score = 0.9 * expectedScore + 0.1 * currentState.score; nexts.add(nextState); } } private double[] area = new double[2]; private int[] number = new int[2]; private void minAreaSD(double area, int numCakes) { double meanArea = area / (double) numCakes; double less = 0.5 * ((int) (2 * meanArea)); double more = Math.abs(less - meanArea) < 1e-5 ? less : (less + 0.5); int numMore = (int) (1e-9 + (area - less * numCakes) / 0.5); int numLess = numCakes - numMore; this.area[0] = less; this.area[1] = more; number[0] = numLess; number[1] = numMore; assert Math.abs(area - (less * numLess + more * numMore)) < 1e-5; } private void minRoseSD(int rose, int numCakes) { double meanRose = rose / (double) numCakes; double less = Math.floor(1e-9 + meanRose); double more = Math.ceil(-1e-9 + meanRose); int numMore = (int) (1e-9 + (rose - less * numCakes)); int numLess = numCakes - numMore; this.area[0] = less; this.area[1] = more; number[0] = numLess; number[1] = numMore; assert Math.abs(rose - (less * numLess + more * numMore)) < 1e-5; } private double[] getTimeLimits(int maxDepth) { double[] timeLimits = new double[maxDepth]; double end = 9.5; double start = Constants.watch.getSecond(); for (int i = 0; i < maxDepth; i++) { timeLimits[i] = start + (end - start) * ((i + 1.0) / maxDepth); } return timeLimits; } private Piece getMaxAreaPiece() { Piece piece = null; for (int i = 0; i < pieces2.size(); i++) { Piece piece2 = pieces2.get(i); if (piece == null || piece2.getPieceArea() > piece.getPieceArea()) { piece = piece2; } } return piece; } private int getMaxAreaPieceIndex() { int maxIndex = 0; for (int i = 0; i < pieces2.size(); i++) { if (pieces2.get(i).getPieceArea() > pieces2.get(maxIndex).getPieceArea()) { maxIndex = i; } } return maxIndex; } private int getMinAreaPieceIndex() { double meanArea = R * C / (double) numCakes; int minIndex = -1; for (int i = 0; i < pieces2.size(); i++) { if (pieces2.get(i).getPieceArea() / meanArea < 1.5) { continue; } if (minIndex == -1 || pieces2.get(i).getPieceArea() < pieces2.get(minIndex).getPieceArea()) { minIndex = i; } } return minIndex; } private int getPieceIndex() { double meanArea = R * C / (double) numCakes; int bestIndex = -1; double bestZ = (int) 1e9; for (int i = 0; i < pieces2.size(); i++) { Piece piece = pieces2.get(i); if (piece.getPieceArea() / meanArea < 1.5) { continue; } int minZ = (int) 1e9; int sumZ = 0; for (int j = 0; j < piece.convexHull.size(); j++) { Point point = piece.convexHull.get(j); int z = point.y + point.x; minZ = Math.min(minZ, z); sumZ += z; } double meanZ = sumZ / (double) piece.convexHull.size(); if (bestIndex == -1 || pieces2.get(i).getPieceArea() < pieces2.get(bestIndex).getPieceArea()) { bestIndex = i; bestZ = meanZ; } else if (Math.abs(pieces2.get(i).getPieceArea() - pieces2.get(bestIndex).getPieceArea()) < 1e-5 && meanZ < bestZ) { bestIndex = i; bestZ = meanZ; } } return bestIndex; } private double[] areaAndRose = new double[4]; private void simulateCut(int ind, Point p1, Point p2) { if (p1.equals(p2)) { areaAndRose[0] = -1; return; } if (!isInside(p1) || !isInside(p2)) { areaAndRose[0] = -1; return; } int i1 = -1, i2 = -1; Piece piece = pieces2.get(ind); i1 = piece.isOnPieceEdge(p1); i2 = piece.isOnPieceEdge(p2); if (i1 > i2) { int t = i2; i2 = i1; i1 = t; Point tmp = p2; p2 = p1; p1 = tmp; } ArrayList pnew = new ArrayList (); for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); int index = piece.points.indexOf(z(point.y, point.x)); if (index > i1 && index < i2) { pnew.add(point); } if (index >= i2) { break; } } pnew.add(p2); pnew.add(p1); Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y)); double anew = newPiece.getPieceArea(); if (anew < 0.25) { areaAndRose[0] = -1; return; } double aold = piece.getPieceArea() - newPiece.getPieceArea(); if (aold < 0.25) { areaAndRose[0] = -1; return; } ArrayList pold_updated = new ArrayList (); for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); int index = piece.points.indexOf(z(point.y, point.x)); if (index < i1) { pold_updated.add(point); } else { break; } } pold_updated.add(p1); pold_updated.add(p2); for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); int index = piece.points.indexOf(z(point.y, point.x)); if (index > i2) { pold_updated.add(point); } } Piece newPiece2 = new Piece(pold_updated, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y)); areaAndRose[0] = newPiece.getPieceArea(); areaAndRose[1] = newPiece.countRose(); areaAndRose[2] = piece.getPieceArea() - newPiece.getPieceArea(); areaAndRose[3] = newPiece2.countRose(); } private void simulateCutFast(int ind, Point p1, Point p2) { if (p1.equals(p2)) { areaAndRose[0] = -1; return; } if (!isInside(p1) || !isInside(p2)) { areaAndRose[0] = -1; return; } int i1 = -1, i2 = -1; Piece piece = pieces2.get(ind); i1 = piece.isOnPieceEdge(p1); i2 = piece.isOnPieceEdge(p2); if (i1 > i2) { int t = i2; i2 = i1; i1 = t; Point tmp = p2; p2 = p1; p1 = tmp; } ArrayList pnew = new ArrayList (); for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); int index = piece.points.indexOf(z(point.y, point.x)); if (index > i1 && index < i2) { pnew.add(point); } } pnew.add(p2); pnew.add(p1); Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y)); double anew = newPiece.getPieceArea(); if (anew < 0.25) { areaAndRose[0] = -1; return; } double aold = piece.getPieceArea() - newPiece.getPieceArea(); if (aold < 0.25) { areaAndRose[0] = -1; return; } areaAndRose[0] = newPiece.getPieceArea(); areaAndRose[1] = newPiece.countRose(); areaAndRose[2] = piece.getPieceArea() - newPiece.getPieceArea(); areaAndRose[3] = piece.countRose() - newPiece.countRose(); } private int turn = 0; private void next(Cut cut) { makeCut(cut.start, cut.end); turn++; } private void previous() { turn--; pieces2.set(indHistory[turn], pieceHistory[turn]); pieces2.remove(pieces2.size() - 1); cuts2.remove(cuts2.size() - 1); } private void set(ArrayList list, int startIndex) { int startIndexMinus1 = startIndex - 1; for (int i = 0; i < list.size() && startIndex + i < cuts2.size(); i++) { State state = list.get(i); if (state.cut.equals(cuts2.get(startIndex + i))) { startIndexMinus1 = startIndex + i; continue; } break; } for (; turn > startIndexMinus1 + 1;) { previous(); } for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) { State state2 = list.get(i); next(state2.cut); } } private ArrayList reverse(ArrayList list) { for (int l = 0, r = list.size() - 1; l < r; l++, r--) { list.set(r, list.set(l, list.get(r))); } return list; } private ArrayList toList(State state2) { ArrayList res = new ArrayList<>(); for (State current = state2; current.parent != null; current = current.parent) { res.add(current); } return res; } private static int cross(int x, int y, int x2, int y2) { return x * y2 - y * x2; } private String[] makeSolution() { ArrayList res = new ArrayList<>(); for (int i = 0; i < cuts2.size(); i++) { Cut cut = cuts2.get(i); res.add(cut.start.x + " " + cut.start.y + " " + cut.end.x + " " + cut.end.y); } return (String[]) res.toArray(new String[res.size()]); } private int H, W; private char[][] roses; private Piece[] pieceHistory = new Piece[321]; private int[] indHistory = new int[321]; private boolean isInside(Point p) { return (p.y >= 0 && p.y <= H && p.x >= 0 && p.x <= W); } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } private String makeCut(Point p1, Point p2) { if (p1.equals(p2)) { Utils.debug("A"); return "The cut must have non-zero length."; } if (!isInside(p1) || !isInside(p2)) { Utils.debug("B"); return "The cut can not start or end outside the cake."; } int ind = -1, i1 = -1, i2 = -1; for (int i = 0; i < pieces2.size(); ++i) { Piece piece = pieces2.get(i); i1 = piece.isOnPieceEdge(p1); if (i1 == -1) continue; i2 = piece.isOnPieceEdge(p2); if (i2 == -1) { i1 = -1; continue; } ind = i; break; } if (ind == -1) { Utils.debug("C"); return "The cut must divide one piece in two pieces."; } Piece piece = pieces2.get(ind); if (i1 > i2) { int t = i2; i2 = i1; i1 = t; Point tmp = p2; p2 = p1; p1 = tmp; } ArrayList pnew = new ArrayList (); for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); int index = piece.points.indexOf(z(point.y, point.x)); if (index > i1 && index < i2) { pnew.add(point); } if (index >= i2) { break; } } pnew.add(p2); pnew.add(p1); Piece newPiece = new Piece(pnew, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y)); double anew = newPiece.getPieceArea(); if (anew < 0.25) { return "The pieces produced by the cut must have non-zero area."; } ArrayList pold_updated = new ArrayList (); for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); int index = piece.points.indexOf(z(point.y, point.x)); if (index < i1) { pold_updated.add(point); } else { break; } } pold_updated.add(p1); pold_updated.add(p2); for (int i = 0; i < piece.convexHull.size(); i++) { Point point = piece.convexHull.get(i); int index = piece.points.indexOf(z(point.y, point.x)); if (index > i2) { pold_updated.add(point); } } Piece newPiece2 = new Piece(pold_updated, piece.isRectangle && (p1.x == p2.x || p1.y == p2.y)); double aold = newPiece2.getPieceArea(); if (aold < 0.25) { return "The pieces produced by the cut must have non-zero area."; } indHistory[turn] = ind; pieceHistory[turn] = pieces2.set(ind, newPiece); pieces2.add(newPiece2); cuts2.add(new Cut(p1, p2)); return ""; } public static void main(String[] args) { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { int size = Integer.parseInt(br.readLine()); String[] roses = new String[size]; for (int i = 0; i < size; ++i) { roses[i] = br.readLine(); } int NP = Integer.parseInt(br.readLine()); CakeSharing cs = new CakeSharing(); String[] ret = cs.cut(roses, NP); 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 Piece { ArrayList convexHull; IntSet points; boolean isRectangle; public Piece(ArrayList convexHull, boolean isRectangle) { super(); this.convexHull = convexHull; this.isRectangle = isRectangle; } @Override public String toString() { return convexHull.toString(); } public boolean isConvexHull(Point point) { for (int i = 0; i < convexHull.size(); i++) { if (convexHull.get(i).equals(point)) { return true; } } return false; } public int pointSize() { if (points == null) { initPoints(); } return points.size(); } public Point getPoint(int i) { if (points == null) { initPoints(); } int z = points.get(i); return new Point(c(z), r(z)); } private int isOnPieceEdge(Point p) { if (points == null) { initPoints(); } return points.indexOf(z(p.y, p.x)); } private void initPoints() { points = new IntSet((R + 1) * (C + 1)); for (int i = 0; i < convexHull.size(); i++) { int j = (i + 1) % convexHull.size(); Point p1 = convexHull.get(i); Point p2 = convexHull.get(j); addPointsOnCut(p1, p2); } } private void addPointsOnCut(Point p1, Point p2) { assert p1.x != p2.x || p1.y != p2.y : Utils.toString("p1.x", p1.x, "p2.x", p2.x, "p1.y", p1.y, "p2.y", p2.y); int dx = p2.x - p1.x, dy = p2.y - p1.y; int g = Math.abs(gcd(dx, dy)); for (int i = 0; i <= g; ++i) { int x = p1.x + (dx / g) * i; int y = p1.y + (dy / g) * i; points.add(z(y, x)); } } private double area = -1; private double getPieceArea() { if (area < 0) { area = 0; for (int i = 0; i < convexHull.size(); ++i) { Point p1 = convexHull.get(i); Point p2 = convexHull.get((i + 1) % convexHull.size()); area += cross(p1.x, p1.y, p2.x, p2.y); } area = 0.5 * Math.abs(area); } return area; } private int countRose = -1; private int countRose() { if (countRose < 0) { int maxX = (int) -1e9; int minX = (int) 1e9; int maxY = (int) -1e9; int minY = (int) 1e9; for (int i = 0; i < convexHull.size(); i++) { Point point = convexHull.get(i); maxX = Math.max(maxX, point.x); minX = Math.min(minX, point.x); maxY = Math.max(maxY, point.y); minY = Math.min(minY, point.y); } if (isRectangle) { countRose = cumulativeSum.cumulativeSum(minY, minX, maxY, maxX); } else { int n = 0; for (int r = minY; r < maxY; ++r) for (int c = minX; c < maxX; ++c) { if (roses[r][c] != 'R') { continue; } if (isRoseInsidePiece(new Point(2 * c + 1, 2 * r + 1))) { n++; } } countRose = n; } } return countRose; } private boolean isRoseInsidePiece(Point point) { for (int i = 0; i < convexHull.size(); i++) { Point p = convexHull.get(i); Point p2 = convexHull.get((i + 1) % convexHull.size()); if (cross(2 * (p2.x - p.x), 2 * (p2.y - p.y), point.x - 2 * p.x, point.y - 2 * p.y) >= 0) { return false; } } return true; } } private int c(int z) { return z % (C + 1); } private int r(int z) { return z / (C + 1); } private int z(int r, int c) { return r * (C + 1) + c; } class State implements Comparable { State parent; Piece piece; Cut cut; double score; @Override public int compareTo(State o) { if (score < o.score) { return -1; } if (score > o.score) { return 1; } return 0; } } } class Constants { public static final XorShift rng = new XorShift(System.nanoTime()); public static final Watch watch = new Watch(); } 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 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) { assert value < valueToIndex.length : Utils.toString("value", value, "valueToIndex.length", valueToIndex.length); 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; } int swap = indexToValue[index]; indexToValue[index] = indexToValue[size - 1]; indexToValue[size - 1] = swap; valueToIndex[indexToValue[index]] = index; 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 int get(int index) { 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; } } class Point { public int x, y; public Point(int px, int py) { x = px; y = py; } public boolean equals(Point p) { return x == p.x && y == p.y; } public String toString() { return "(" + x + "," + y + ")"; } } class Cut { public Point start, end; public Cut(Point s, Point e) { start = s; end = e; } public Cut(int x1, int y1, int x2, int y2) { start = new Point(x1, y1); end = new Point(x2, y2); } public boolean equals(Cut obj) { return (start.equals(obj.start) && end.equals(obj.end)) || (start.equals(obj.end) && end.equals(obj.start)); } public String toString() { return start + " - " + end; } } class Pair , S> implements Comparable > { 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 other = (Pair ) 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 o) { return first.compareTo(o.first); } } 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, int 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) { double variance = variance(defaultValue); if (Math.abs(variance) < 1e-9) { return 0; } return Math.sqrt(variance); } 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 TwoDimensionalCumulativeSum { private int[][] sum; public TwoDimensionalCumulativeSum(int[][] values) { int R = values.length; int C = values[0].length; sum = new int[R + 1][C + 1]; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { sum[r + 1][c + 1] = sum[r + 1][c] + sum[r][c + 1] - sum[r][c] + values[r][c]; } } } public int cumulativeSum(int startRInclusive, int startCInclusive, int endRExclusive, int endCExclusive) { return sum[startRInclusive][startCInclusive] - sum[endRExclusive][startCInclusive] - sum[startRInclusive][endCExclusive] + sum[endRExclusive][endCExclusive]; } }