EvbCFfp1XB

problem and my answer.


点の座標を決める問題なので、CirclesSeparation (2013 TCO Marathon Round 3) と同じ問題だと思いました。

シミュレーテッドアニーリングしました。
最後にヒルクライミングしました。

シミュレーテッドアニーリング
  • 遷移確率は random[0,1) < exp(相対誤差/温度)
  • 温度は 0.2 -> 0 に線形に冷ます
  • 近傍の範囲も 128 -> 1 に線形に減らす


近傍

  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、前回選んだ点を中心に対称の座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 (1 + random[0,1) *
    近傍の範囲) の8方向で、スコアを最も良くする座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 {近傍の範囲*1/8, 近傍の範囲*2/8, 近傍の範囲*3/8, 近傍の範囲*4/8, 近傍の範囲*5/8, 近傍の範囲*6/8, 近傍の範囲*7/8, 近傍の範囲*8/8, } * 8方向で、スコアを最も良くする座標に移動する。
  • 前回選んだ点からつながっている点で最もスコアを悪くしている点を選んで、 (1 + random[0,1) *
    近傍の範囲) の8方向の内ランダムに移動する。
  • 前回選んだ点を、数千回に1回、最小レシオまたは最大レシオの辺の4点からランダムに1点選んで、更新する。最小レシオ,最大レシオもいっしょに更新する。
  • スコアは、最小レシオ,最大レシオを覚えておいて、選んだ点の辺のみ計算する。


ヒルクライミング

近傍

  • 改めて計算し直した、最小レシオまたは最大レシオの辺の4点からランダムに1点選んで、8近傍で最も問題のスコアが良くなる座標に移動する。

English(Google Translate)


Since it is a matter of determining the coordinates of the point, I thought it was the same problem as CirclesSeparation (2013 TCO Marathon Round 3).

I simulated annealed.
Finally I did hill climbing.

Simulated annealing

    
The transition probability is random [0, 1) <exp (relative error / temperature)
    
Cool the temperature linearly to 0.2 -> 0
    
Reduce the neighborhood range linearly to 128 -> 1


Neighborhood

    
Choose the point with the worst score at the point connected from the last point chosen, and move to the symmetrical coordinates around the last point chosen.
    
Select the point that has the worst score at the point connected from the last point chosen, and (1 + random [0, 1) *
    
Move to the coordinates that maximize the score in 8 directions of the neighborhood).
    
Select the point that has the worst score at the point connected from the last point chosen, and select {Point in the neighborhood * 1/8, the range in the vicinity * 2/8, the range in the vicinity * 3/8, the range in the vicinity * 4/8, the range of the neighborhood * 5/8, the range of the neighborhood * 6/8, the range of the neighborhood * 7/8, the range of the neighborhood * 8/8,} * Moving.
    
Select the point that has the worst score at the point connected from the last point chosen, and (1 + random [0, 1) *
    
A range in the vicinity) within the eight directions.
    
Select one point at the last time randomly from four points of the minimum ratio or the maximum ratio side once every several thousand times and update it. Update minimum ratio, maximum ratio together.
    
For the score, remember the minimum ratio, the maximum ratio, and calculate only the side of the selected point.



Hill climbing

Neighborhood

    
Randomly select one point from the four points on the minimum ratio or maximum ratio ratio that was recalculated anew and move to the coordinates with the best problem score in 8 neighborhood.



source code

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

public class GraphDrawing {
static final Watch watch = new Watch();
static final XorShift rng = new XorShift(System.nanoTime());
private SAState sa = new SAState();
private static final int size = 701;

private double score;
private double bestScore;

private Point[] points;
private Edge[] edges;
private byte[][] usedPoint = new byte[size][size];
private Point[] bestPoints;

private double[] pointIndexToScore;
private IntArray[] pointIndexToEdgeIndexes;
private int numVertices;
private int numEdges;

private static final int[] dr = new int[] { -1, -1, -1, 0, 1, 1, 1, 0, };
private static final int[] dc = new int[] { -1, 0, 1, 1, 1, 0, -1, -1, };
private int countUsed = 0;
private int countOutOfRange = 0;

public int[] plot(int numVertices, int[] edgeInformations) {
init(numVertices, edgeInformations);

solve();

int[] solution = makeSolution();

Utils.debug("time", watch.getSecond(), "score", calculateScore(), "countUsed", countUsed, "countOutOfRange", countOutOfRange);
return solution;
}

private void solve() {
points = new Point[numVertices];
for (int pointIndex = 0; pointIndex < points.length; pointIndex++) {
for (;;) {
int r = (int) (size * rng.nextDouble());
int c = (int) (size * rng.nextDouble());
assert usedPoint[r][c] >= 0;
if (usedPoint[r][c] == 0) {
points[pointIndex] = new Point(r, c);
usedPoint[r][c]++;
break;
}
}
}

bestPoints = new Point[numVertices];
for (int i = 0; i < bestPoints.length; i++) {
bestPoints[i] = new Point(0, 0);
}

pointIndexToScore = new double[numVertices];
for (int pointIndex = 0; pointIndex < points.length; pointIndex++) {
pointIndexToScore[pointIndex] = calculateLocalScore(pointIndex);
}

score = calculateScore();

SA();

greedy();
}

private void init(int numVertices, int[] edgeInformations) {
this.numVertices = numVertices;

assert edgeInformations.length % 3 == 0;
this.numEdges = edgeInformations.length / 3;

Utils.debug("numVertices", numVertices, "numEdges", numEdges);

edges = new Edge[numEdges];
for (int i = 0; i < numEdges; i++) {
edges[i] = new Edge(edgeInformations[3 * i + 0], edgeInformations[3 * i + 1], edgeInformations[3 * i + 2]);
}

pointIndexToEdgeIndexes = new IntArray[numVertices];
for (int i = 0; i < pointIndexToEdgeIndexes.length; i++) {
pointIndexToEdgeIndexes[i] = new IntArray(16);
}
for (int i = 0; i < edges.length; i++) {
pointIndexToEdgeIndexes[edges[i].pointIndex1].add(i);
pointIndexToEdgeIndexes[edges[i].pointIndex2].add(i);
}
}

private int[] makeSolution() {
int[] solution = new int[2 * numVertices];
for (int i = 0; i < numVertices; i++) {
solution[2 * i + 0] = points[i].r;
solution[2 * i + 1] = points[i].c;
}
return solution;
}

private void SA() {
double second = 1;
int mask10 = (1 << 10) - 1;
int mask14 = (1 << 14) - 1;
int mask = 1;
{
int n = 1;
while (n < edges.length) {
n <<= 1;
}
mask = n - 1;
}
for (sa.loop = 0;; sa.loop++) {

if ((sa.loop & mask10) == 0) {
if ((sa.loop & mask14) == 0) {
sa.updateTime();

if (sa.isTLE()) {
saveBest();
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
break;
}

sa.updateTemperature();
sa.updateRange();
}

adjustMargins();

if ((sa.loop & mask) == 0) {
pointIndexOfWorstScore();
int edgeIndex = rng.nextDouble() < 0.5 ? minRatioEdgeIndex : maxRatioEdgeIndex;
previousPointIndex = rng.nextDouble() < 0.5 ? edges[edgeIndex].pointIndex1 : edges[edgeIndex].pointIndex2;

saveBest();
}

if (sa.time > second) {
second++;
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
}
}

if (rng.nextDouble() < 0.1) {
selectAPointAndMoveToASymmetricCoordinateForOnePoint();
continue;
}
if (rng.nextDouble() < 0.1) {
selectAPointAndMoveToBestDirection();
continue;
}
if (rng.nextDouble() < 0.01) {
selectAPointAndMoveToBestDirectionAndLength();
continue;
}
selectAPointAndMoveToNearCoordinate();

}
}

private void greedy() {

sa.startTime = 9.5;
sa.endTime = 9.8;
sa.startRange = sa.endRange;
sa.startTemperature = sa.endTemperature;
sa.countChange = 0;
sa.countAccept = 0;
for (sa.loop = 0;; sa.loop++) {

sa.updateTime();

if (sa.isTLE()) {
saveBest();
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", score), String.format("%.6f", sa.temperature), String.format("%.0f", sa.range), countOutOfRange);
break;
}

adjustMargins();

selectAPointAndMoveToBestDirectionGreedy();
}
}

private int previousPointIndex;

private void selectAPointAndMoveToBestDirection() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int length = (1 + (int) (sa.range * rng.nextDouble()));

double bestScore = -1;
int bestR = -1;
int bestC = -1;

for (int d = 0; d < dr.length; d++) {

int nextR = currentR + length * dr[d];
int nextC = currentC + length * dc[d];

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

sa.countChange++;
if (bestScore >= currentScore || sa.accept(bestScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = bestScore;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToBestDirectionGreedy() {
pointIndexOfWorstScore();
int pointIndex = (sa.loop & 1) == 0 ? (rng.nextDouble() < 0.5 ? edges[minRatioEdgeIndex].pointIndex1 : edges[minRatioEdgeIndex].pointIndex2) : (rng.nextDouble() < 0.5 ? edges[maxRatioEdgeIndex].pointIndex1 : edges[maxRatioEdgeIndex].pointIndex2);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;
double currentScore = minRatio / maxRatio;

int length = 1;

double bestScore = -1;
int bestR = -1;
int bestC = -1;

for (int d = 0; d < dr.length; d++) {

int nextR = currentR + length * dr[d];
int nextC = currentC + length * dc[d];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
continue;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateScore();

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

if (bestR == -1) {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
return;
}

sa.countChange++;
if (bestScore > currentScore) {
sa.countAccept++;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;

score = bestScore;
saveBestDoNotUpdateScore();
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToBestDirectionAndLength() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int bestR = -1;
int bestC = -1;

double bestScore = -1;
int bestDirection = -1;
for (int d = 0; d < dr.length; d++) {

int nextR = currentR + dr[d];
int nextC = currentC + dc[d];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
continue;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
bestDirection = d;
}
}

if (bestDirection == -1) {
return;
}

int deltaLength = (int) (Math.ceil(sa.range / 8.0));
for (int i = 0; i < 8; i++) {

int length = i * deltaLength;
int nextR = currentR + length * dr[bestDirection];
int nextC = currentC + length * dc[bestDirection];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
countOutOfRange++;
break;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
continue;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

if (nextScore > bestScore) {
bestScore = nextScore;
bestR = nextR;
bestC = nextC;
}
}

sa.countChange++;
if (bestScore >= currentScore || sa.accept(bestScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = bestScore;

points[pointIndex].r = bestR;
points[pointIndex].c = bestC;

usedPoint[currentR][currentC]--;
usedPoint[bestR][bestC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}
}

private void selectAPointAndMoveToNearCoordinate() {
int pointIndex = pointIndexOfLocalWorstScore(previousPointIndex);
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int direction = (int) (dr.length * rng.nextDouble());
int length = (1 + (int) (sa.range * rng.nextDouble()));
int nextR = currentR + length * dr[direction];
int nextC = currentC + length * dc[direction];

if (nextR < 0 || nextR >= size || nextC < 0 || nextC >= size) {
direction = (direction + (dr.length >>> 1)) % dr.length;
nextR = currentR + length * dr[direction];
nextC = currentC + length * dc[direction];
}

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
return;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

sa.countChange++;
if (nextScore >= currentScore || sa.accept(nextScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = nextScore;
usedPoint[currentR][currentC]--;
usedPoint[nextR][nextC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}

}

private void selectAPointAndMoveToASymmetricCoordinateForOnePoint() {
int edgeIndex = edgeIndexOfLocalWorstScore(previousPointIndex);
int pointIndex = edges[edgeIndex].pointIndex1 == previousPointIndex ? edges[edgeIndex].pointIndex2 : edges[edgeIndex].pointIndex1;
int pointIndex2 = edges[edgeIndex].pointIndex1 == previousPointIndex ? edges[edgeIndex].pointIndex1 : edges[edgeIndex].pointIndex2;
assert pointIndex2 == previousPointIndex;
previousPointIndex = pointIndex;

int currentR = points[pointIndex].r;
int currentC = points[pointIndex].c;

double currentScore = pointIndexToScore[pointIndex];

int nextR = points[pointIndex].r + 2 * (points[pointIndex2].r - points[pointIndex].r);
int nextC = points[pointIndex].c + 2 * (points[pointIndex2].c - points[pointIndex].c);

if (nextR < 0) {
nextR = 0;
} else if (nextR >= size) {
nextR = size - 1;
}
if (nextC < 0) {
nextC = 0;
} else if (nextC >= size) {
nextC = size - 1;
}

if (usedPoint[nextR][nextC] > 0) {
countUsed++;
return;
}

points[pointIndex].r = nextR;
points[pointIndex].c = nextC;

double nextScore = calculateLocalScore(pointIndex);

sa.countChange++;
if (nextScore >= currentScore || sa.accept(nextScore, currentScore)) {
sa.countAccept++;

pointIndexToScore[pointIndex] = nextScore;
usedPoint[currentR][currentC]--;
usedPoint[nextR][nextC]++;
} else {
points[pointIndex].r = currentR;
points[pointIndex].c = currentC;
}

}

private double calculateScore() {
double min = 1e99;
double max = -1e99;
for (int i = 0; i < edges.length; i++) {
double ratio = calculateSquaredDistance(edges[i]) * edges[i].inverseSquaredDesiredLength;
min = Math.min(min, ratio);
max = Math.max(max, ratio);
}
return Math.sqrt(min / max);
}

private double minRatio;
private double maxRatio;
private int minRatioEdgeIndex;
private int maxRatioEdgeIndex;

private void pointIndexOfWorstScore() {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < edges.length; i++) {
double ratio = calculateSquaredDistance(edges[i]) * edges[i].inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = i;
}
if (ratio > max) {
max = ratio;
maxi = i;
}
}
minRatio = Math.sqrt(min);
maxRatio = Math.sqrt(max);
minRatioEdgeIndex = mini;
maxRatioEdgeIndex = maxi;
}

private double calculateLocalScore(int pointIndex) {
double min = 1e99;
double max = -1e99;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
Edge edge = edges[pointIndexToEdgeIndexes[pointIndex].values[i]];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
min = Math.min(min, ratio);
max = Math.max(max, ratio);
}
return Math.min(Math.sqrt(min) / maxRatio, minRatio / Math.sqrt(max));
}

private int pointIndexOfLocalWorstScore(int pointIndex) {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
int edgeIndex = pointIndexToEdgeIndexes[pointIndex].values[i];
Edge edge = edges[edgeIndex];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = edgeIndex;
}
if (ratio > max) {
max = ratio;
maxi = edgeIndex;
}
}
return (Math.sqrt(min) / maxRatio < minRatio / Math.sqrt(max) ? (edges[mini].pointIndex1 == pointIndex ? edges[mini].pointIndex2 : edges[mini].pointIndex1) : (edges[maxi].pointIndex1 == pointIndex ? edges[maxi].pointIndex2 : edges[maxi].pointIndex1));
}

private int edgeIndexOfLocalWorstScore(int pointIndex) {
double min = 1e99;
int mini = -1;
double max = -1e99;
int maxi = -1;
for (int i = 0; i < pointIndexToEdgeIndexes[pointIndex].length; i++) {
int edgeIndex = pointIndexToEdgeIndexes[pointIndex].values[i];
Edge edge = edges[edgeIndex];
double ratio = calculateSquaredDistance(edge) * edge.inverseSquaredDesiredLength;
if (ratio < min) {
min = ratio;
mini = edgeIndex;
}
if (ratio > max) {
max = ratio;
maxi = edgeIndex;
}
}
return (Math.sqrt(min) / maxRatio < minRatio / Math.sqrt(max) ? mini : maxi);
}

private double calculateSquaredDistance(Edge edge) {
int dr = points[edge.pointIndex1].r - points[edge.pointIndex2].r;
int dc = points[edge.pointIndex1].c - points[edge.pointIndex2].c;
return (dr * dr + dc * dc);
}

private void loadBest() {
score = bestScore;
for (int i = 0; i < points.length; i++) {
points[i].r = bestPoints[i].r;
points[i].c = bestPoints[i].c;
}
}

private void saveBest() {
score = calculateScore();
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < points.length; i++) {
bestPoints[i].r = points[i].r;
bestPoints[i].c = points[i].c;
}
}
}

private void saveBestDoNotUpdateScore() {
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < points.length; i++) {
bestPoints[i].r = points[i].r;
bestPoints[i].c = points[i].c;
}
}
}

private void adjustMargins() {
int minR = (int) 1e9;
int maxR = (int) -1e9;
int minC = (int) 1e9;
int maxC = (int) -1e9;
for (int i = 0; i < points.length; i++) {
minR = Math.min(minR, points[i].r);
maxR = Math.max(maxR, points[i].r);
minC = Math.min(minC, points[i].c);
maxC = Math.max(maxC, points[i].c);
}

int marginL = minC - 0;
int marginR = 700 - maxC;
int marginD = minR - 0;
int marginU = 700 - maxR;

int newMarginD = (marginD + marginU) / 2;
int deltaR = newMarginD - marginD;
int newMarginL = (marginL + marginR) / 2;
int deltaC = newMarginL - marginL;

for (int i = 0; i < points.length; i++) {
usedPoint[points[i].r][points[i].c]--;
points[i].r += deltaR;
points[i].c += deltaC;
usedPoint[points[i].r][points[i].c]++;
}

}

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

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

GraphDrawing gd = new GraphDrawing();
int[] ret = gd.plot(N, edges);

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 Point {
int r;
int c;

public Point(int r, int c) {
this.r = r;
this.c = c;
}
}

class Edge {
int pointIndex1;
int pointIndex2;
double inverseSquaredDesiredLength;

public Edge(int pointIndex1, int pointIndex2, int desiredLength) {
super();
this.pointIndex1 = pointIndex1;
this.pointIndex2 = pointIndex2;
this.inverseSquaredDesiredLength = 1.0 / (desiredLength * desiredLength);
}

@Override
public String toString() {
return "[" + pointIndex1 + "," + pointIndex2 + "]";
}

}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 9.5;
public double time = startTime;

public double startTemperature = 2 * 1e-1;
public double endTemperature = 0;
public double temperature = startTemperature;

public double startRange = 128;
public double endRange = 1;
public double range = startRange;

public int loop;
public int countChange;
public int countAccept;

public void updateTemperature() {
temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateRange() {
range = (endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
}

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

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore < 0;
assert temperature >= 0;
return GraphDrawing.rng.nextDouble() < StrictMath.exp((newScore - currentScore) / (currentScore * temperature));
}
}

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

}








ネットワークの構成を変えると、結果がどのように変わるか実験してみました。

FacialEmotions seed1

System test 1位(Psyho)と2位(wleite)




sse
Psyho


82.6467632504
wleite


80.3573356044



d = dropout
c = convolutional layer
b = batch normalization
r = rectified linear unit (ReLU)
m = max pooling
l = Linear layer (a.k.a. fully-connected layer)
s = softmax

convolutional layer を 3 回使います。
net epoch loss accuracy sse
crmcrmcrmlrls 10 0.862057242 0.6888581587 84.8293236042
crmcrmcrmlrls 20 0.2330729473 0.9241406559 110.2754166642


Batch Normalizationを使いました。
net epoch loss accuracy sse
cbrm cbrm cbrm lbr ls 10 0.0292957636 1 98.5088547936
 
Batch Normalization を使う位置を変えました。
net epoch loss accuracy sse
crbmcrbmcrbmlrbls 10 0.0161193058 1 103.3351983911
crmbcrmbcrmblbrls 10 0.0428612025 0.9990122481 104.5428854816

dropout を使いました。
net epoch loss accuracy sse
d cbrm cbrm cbrm lbr ls 10 0.6779491677 0.7741999208 127.6396549389
cdbrm cbrm cbrm lbr ls 10 0.1860714287 0.9697747926 97.3982535937
cbdrm cbrm cbrm lbr ls 10 0.1261851785 0.9891347294 90.293485705
cbrdm cbrm cbrm lbr ls 10 0.1165383348 0.9877518768 135.9137072744
cbrm d cbrm cbrm lbr ls 10 0.3982799557 0.8860134335 89.3255575127
cbrm cdbrm cbrm lbr ls 10 0.3108963729 0.9205847492 87.1665944558
cbrm cbdrm cbrm lbr ls 10 0.2976720617 0.9265112604 87.8945815325
cbrm cbrdm cbrm lbr ls 10 0.2908983695 0.9274990119 97.0035103791
cbrm cbrm d cbrm lbr ls 10 0.6466208026 0.7740023707 82.3041648362
cbrm cbrm d cbrm lbr ls 10 0.6593907256 0.7710391151 87.7033221745
cbrm cbrm cdbrm lbr ls 10 0.5000952218 0.8356380879 85.98265144
cbrm cbrm cbdrm lbr ls 10 0.4267725744 0.8735677599 83.6281797147
cbrm cbrm cbrdm lbr ls 10 0.4398758164 0.8619122878 87.4801027678
cbrm cbrm cbrm d lbr ls 10 0.7070338922 0.7443698141 85.7758809568
cbrm cbrm cbrm d lbr ls 10 0.7025089265 0.7459502175 83.1445387195
cbrm cbrm cbrm ldbr ls 10 0.6557939961 0.7773607272 98.114469585
cbrm cbrm cbrm lbdr ls 10 0.44960894 0.8561833265 105.3589899718
cbrm cbrm cbrm lbr d ls 10 0.4411115036 0.8555906757 84.4414017709
cbrm cbrm cbrm lbr l b s 10 0.350525047 0.9998024496 107.6956465493

dropout を2回以上使いました。

net epoch loss accuracy sse
cbrmDcbrmcbrmlbrDls 20 0.4687651145 0.8354405375 88.8934547861
cbrmDcbrmcbrmDlbrls 20 0.646407447 0.7635322005 83.6677099091
cbrmDcbrmDcbrmlbrls 20 0.4206087752 0.8668510471 88.9427621938
cbrmcbrmDcbrmlbrDls 20 0.697579882 0.7500987754 81.9197008873
cbrmcbrmDcbrmDlbrls 20 0.7615070114 0.7354800472 78.8430071664
cbrmcbrmcbrmDlbrDls 20 0.7329212929 0.7412090082 83.007588472
cbrmDcbrmDcbrmDlbrls 20 0.8634045921 0.6959699726 79.3253190373
cbrmDcbrmDcbrmlbrDls 20 0.8133866381 0.7044646383 79.0648046938
cbrmDcbrmcbrmDlbrDls 20 0.9094222649 0.6716712761 80.0929658934
cbrmcbrmDcbrmDlbrDls 20 0.9502801996 0.66851047 78.9084275277
cbrmDcbrmDcbrmDlbrDls 20 1.037415473 0.6309758988 79.860401207





source code (cbrmDcbrmDcbrmDlbrDls)


#coding: utf-8
import numpy as np
import sys
import chainer
from chainer import cuda
import chainer.functions as F
import chainer.links as L
from chainer import optimizers
import time
import pickle
import os.path


class Net(chainer.Chain):

def __init__(self, class_labels=7):
super(Net, self).__init__(
conv1=L.Convolution2D( 3, 64, 3, stride=1, pad=1),
bn1=L.BatchNormalization(64),
conv2=L.Convolution2D( 64, 64, 3, stride=1, pad=1),
bn2=L.BatchNormalization(64),
conv3=L.Convolution2D( 64, 64, 3, stride=1, pad=1),
bn3=L.BatchNormalization(64),

fc1=L.Linear(None, 64, nobias=True),
bn_fc1=L.BatchNormalization(64),
fc2=L.Linear(None, class_labels, nobias=True),
bn_fc2=L.BatchNormalization(class_labels)
)

def __call__(self, x, y, train=True):
h = self.conv1(x)
h = self.bn1(h, test=not train)
h = F.relu(h)
h = F.max_pooling_2d(h, ksize=2, stride=2)

h = F.dropout(h, ratio=0.5, train=train)

h = self.conv2(h)
h = self.bn2(h, test=not train)
h = F.relu(h)
h = F.max_pooling_2d(h, ksize=2, stride=2)

h = F.dropout(h, ratio=0.5, train=train)

h = self.conv3(h)
h = self.bn3(h, test=not train)
h = F.relu(h)
h = F.max_pooling_2d(h, ksize=2, stride=2)

h = F.dropout(h, ratio=0.5, train=train)

h = self.fc1(h)
h = self.bn_fc1(h, test=not train)
h = F.relu(h)

h = F.dropout(h, ratio=0.5, train=train)

h = self.fc2(h)
# h = self.bn_fc2(h, test=not train)
# h = F.relu(h)
# h = F.dropout(h, ratio=0.5, train=train)

if train:
return F.softmax_cross_entropy(h, y), F.accuracy(h, y)
else:
return F.softmax(h)

class FacialEmotions:
def __init__(self):
self.startTime = time.perf_counter();

# self.useModel = True
self.useModel = False

# self.train_size10 = True
self.train_size10 = False

self.train = []
self.train_result = []
self.train_index = 0
self.test = []
self.test_index = 0


self.batchsize = 128
self.useSmallImage = True
# self.useSmallImage = False
self.size = 64
self.model = Net()

self.folder = "./python/cbrmDcbrmDcbrmDlbrDls/"

# pkl_file = open(self.folder + "FacialEmotions.pkl", "rb")
# self.model = pickle.load(pkl_file)
# print("load model", file=sys.stderr)
# sys.stderr.flush()

def newImage(self, img):
three = self.oneDimensionToThreeDimension(img)

if self.useSmallImage == True:
three = self.smallImage(three)

return self.cropImage(three, (len(three[0])//2) - (self.size//2), (len(three[0][0])//2) - (self.size//2), self.size, self.size)

def cropImage(self, img, startR, startC, sizeR, sizeC):
crop = np.zeros((3, sizeR, sizeC))
for color in range(3):
for r in range(sizeR):
for c in range(sizeC):
crop[color][r][c] = img[color][startR + r][startC + c]
return crop

def smallImage(self, img):
sizeR = len(img[0])//2
sizeC = len(img[0][0])//2
# print("sizeR : {}, sizeC : {}\n".format(sizeR , sizeC), file=sys.stderr)
# sys.stderr.flush()
small = np.zeros((3, sizeR, sizeC))
for color in range(3):
for r in range(sizeR):
for c in range(sizeC):
small[color][r][c] = img[color][2 * r + 0][2 * c + 0]
small[color][r][c] += img[color][2 * r + 0][2 * c + 1]
small[color][r][c] += img[color][2 * r + 1][2 * c + 0]
small[color][r][c] += img[color][2 * r + 1][2 * c + 1]
small[color][r][c] /= 4
return small

def oneDimensionToThreeDimension(self, img):
three = np.zeros((3, 250, 250))
for r in range(250):
for c in range(250):
value = img[r * 250 + c]
red = (value >> 16) & 255
green = (value >> 8) & 255
blue = (value >> 0) & 255
three[0][r][c] = red
three[1][r][c] = green
three[2][r][c] = blue
return three

def flipImage(self, img):
sizeR = len(img[0])
sizeC = len(img[0][0])
flip = np.zeros((3, sizeR, sizeC))
for color in range(3):
for r in range(sizeR):
for c in range(sizeC):
flip[color][r][c] = img[color][r][(sizeC - 1) - c]
return flip

def training(self, img, emot):
if self.useModel == True:
return 1

elif os.path.isfile("./python/training_seed1.pkl"):
pkl_file = open("./python/training_seed1.pkl", "rb")
self.train = pickle.load(pkl_file)
pkl_file = open("./python/training_result_seed1.pkl", "rb")
self.train_result = pickle.load(pkl_file)
print("load training data", file=sys.stderr)
sys.stderr.flush()
return 1

if self.train_index % 100 == 0:
print(self.train_index, file=sys.stderr)

image = self.newImage(img)
self.train.append(image)
# self.train.append(self.flipImage(image))

emotion = 0
for i in range(7):
emotion += (i+0) * emot[i]
self.train_result.append(emotion)
# self.train_result.append(emotion)

self.train_index+=1

if self.train_size10 == True and self.train_index == 10:
return 1

return 0

def training2(self):
if os.path.isfile("./python/training_seed1.pkl") == False:
pickle.dump(self.train, open("./python/training_seed1.pkl", "wb"), -1)
pickle.dump(self.train_result, open("./python/training_result_seed1.pkl", "wb"), -1)
print("save training data", file=sys.stderr)
sys.stderr.flush()

self.train = np.array(self.train, dtype=np.float32)
self.train_result = np.array(self.train_result, dtype=np.int32)

self.train /= 255.0

optimizer = optimizers.Adam()
optimizer.setup(self.model)

batchsize = self.batchsize
n_epoch = 20

x_train = self.train
y_train = self.train_result
N = len(y_train)

elapse = int(time.perf_counter() - self.startTime)
print("start, time: {}:{}:{}".format(elapse//(60*60), (elapse%(60*60))//(60), elapse%60), file=sys.stderr)
sys.stderr.flush()
for epoch in range(1, n_epoch + 1):

perm = np.random.permutation(N)
sum_loss = 0
sum_accuracy = 0
for i in range(0, N, batchsize):
x_batch = np.asarray(x_train[perm[i:i + batchsize]])
y_batch = np.asarray(y_train[perm[i:i + batchsize]])

optimizer.zero_grads()
loss, accuracy = self.model(x_batch, y_batch, train=True)
loss.backward()
optimizer.update()
sum_loss += float(loss.data) * len(y_batch)
sum_accuracy += float(accuracy.data) * len(y_batch)

pickle.dump(self.model.to_cpu(), open(self.folder + "FacialEmotions" + str(epoch) + ".pkl", "wb"), -1)
print("save model", file=sys.stderr)
sys.stderr.flush()

elapse = int(time.perf_counter() - self.startTime)
print("epoch: {}, time: {}:{}:{}, loss: {}, accuracy: {}".format(epoch, elapse//(60*60), (elapse%(60*60))//(60), elapse%60, sum_loss / N, sum_accuracy / N), file=sys.stderr)
sys.stderr.flush()

pickle.dump(self.model.to_cpu(), open(self.folder + "FacialEmotions.pkl", "wb"), -1)
print("save model", file=sys.stderr)
sys.stderr.flush()


def testing(self, img,*args):
if self.test_index % 10 == 0:
print(self.test_index, file=sys.stderr)
sys.stderr.flush()

if self.useModel == True and self.test_index == 0:
pkl_file = open(self.folder + "FacialEmotions.pkl", "rb")
self.model = pickle.load(pkl_file)
print("load model", file=sys.stderr)
sys.stderr.flush()

elif self.test_index == 0:
self.training2()

self.test_index += 1

newImg = self.newImage(img)

test = []
test.append(newImg)
test = np.array(test, dtype=np.float32)
test /= 255.0

prediction = self.model(test, None, train=False)

return prediction.data[0]

if __name__ == "__main__":

fe = FacialEmotions()
N = int(input())
for i in range(N):
S = int(input())
imageData = []
for j in range(S):
imageData.append(int(input()))
emotions = []
for j in range(7):
emotions.append(float(input()))
ret = fe.training(imageData, emotions)
print(ret)
sys.stdout.flush()
if ret == 1:
break

M = int(input())
for i in range(M):
S = int(input())
imageData = []
for j in range(S):
imageData.append(int(input()))
emotions = fe.testing(imageData)
for emotion in emotions:
print(emotion)
sys.stdout.flush()






Rank 11/80

アプローチ stitch の数が多いとき:
  1. cross stitch 単位で、任意の cross stitch からの距離が0の imaginary cross stitch を加えて Travelling Salesman Problem として解く。
  2. 直前の cross stitch と次の cross stitch からの距離が短い縫い方を貪欲法で見つける。
  3. 2opt で改善する。
stitch の数が少ないとき:
  1. stitch 単位で、任意の stitch からの距離が0の imaginary stitch を加えて、 Travelling Salesman Problem として解く。

Approach(Google Translate) When the number of stitches is large:

  1. In cross stitch unit, add imaginary cross stitch with distance 0 from arbitrary cross stitch and solve it as Traveling Salesman Problem.
  2. Find greedy how to sew a short distance from the previous cross stitch and the next cross stitch.
  3. Improve by 2opt.

When the number of stitches is small:

  1. Add imaginary stitch with distance 0 from arbitrary stitch in stitch unit and solve it as Traveling Salesman Problem.


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

public class CrossStitch {
private double lengthFront;
private double lengthBack;

private int S;
private Watch watch = new Watch();
private HashMap<Integer, ArrayList<Point>> colorToPoints = new HashMap<>();
private HashMap<Integer, ArrayList<Stitch>> colorToStitches = new HashMap<>();

private int numStitches;
private XorShift xorShift = new XorShift(System.nanoTime());
private double[][] distancesStitchTo4PointOfStitch;
private int[] index2stitch;
private int[] stitch2index;
private IntArray[] stitch2nearestStitches;
private boolean[] startFromUpper;
private HashMap<Integer, HashMap<Integer, Integer>> stitch2nearestStitchIndex2index;

private int sumLoops;
private int sumTries;
private int sumAccepts;
private ArrayList<Stitch> stitches;

public String[] embroider(String[] pattern) {
init(pattern);

ArrayList<String> ret = new ArrayList<>();

double initTime = watch.getSecond();

double eachColorTime = (1 * 9.5 - initTime) / colorToPoints.keySet().size();

double sumBackLength = 0;

for (Integer color : colorToPoints.keySet()) {

eachColorWatch.init();

if (colorToPoints.get(color).size() < 750) {

ArrayList<Stitch> stitches = colorToStitches.get(color);
stitches.add(new Stitch(new Point(-1, -1), new Point(-1, -1)));
this.stitches = stitches;

numStitches = stitches.size();

setDistance(stitches);

initializeIndex(stitches);

improve(eachColorTime, stitches);

sumBackLength += calculateScore();

numStitches--;
int startIndex = -1;
for (int i = 0; i < index2stitch.length; i++) {
if (index2stitch[i] == numStitches) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Stitch> path = new ArrayList<>();
boolean[] isUpper2 = new boolean[numStitches];
for (int i = startIndex + 1; i < startIndex + index2stitch.length; i++) {
path.add(stitches.get(index2stitch[i % index2stitch.length]));
isUpper2[i - (startIndex + 1)] = startFromUpper[index2stitch[i % index2stitch.length]];
}

makeResult(ret, color, path, isUpper2);

} else {
ArrayList<Point> points = colorToPoints.get(color);

int[] x = new int[points.size() + 1];
int[] y = new int[points.size() + 1];
for (int i = 0; i < points.size(); i++) {
x[i] = points.get(i).c;
y[i] = points.get(i).r;
}
x[points.size()] = -2;
y[points.size()] = -2;

EuclideanTravellingSalesmanProblem tsp = new EuclideanTravellingSalesmanProblem();
int[] order = tsp.getOrder(x, y, eachColorTime);

sumLoops += tsp.loop;
sumTries += tsp.tries;
sumAccepts += tsp.ac;

int startIndex = -1;
for (int i = 0; i < order.length; i++) {
if (order[i] == points.size()) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Point> pathStitch = new ArrayList<>();
for (int i = startIndex + 1; i < startIndex + order.length; i++) {
pathStitch.add(points.get(order[i % order.length]));
}

ArrayList<Stitch> stitches = greedy(color, pathStitch);
stitches.add(new Stitch(new Point(-2, -2), new Point(-2, -2)));

boolean[] startFromUpper = new boolean[stitches.size()];
for (int i = 0; i < stitches.size(); i++) {
startFromUpper[i] = true;
Stitch stitch = stitches.get(i);
if (stitch.upper.r < stitch.lower.r) {
startFromUpper[i] = !true;

Point swap = stitch.upper;
stitch.upper = stitch.lower;
stitch.lower = swap;
}
}

for (int k = 0; k < 5; k++) {
greedy2opt(stitches, startFromUpper);
}
startIndex = -1;
for (int i = 0; i < stitches.size(); i++) {
if (stitches.get(i).upper.r < 0) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Stitch> path = new ArrayList<>();
boolean[] isUpper2 = new boolean[stitches.size() - 1];
for (int i = startIndex + 1; i < startIndex + stitches.size(); i++) {
path.add(stitches.get(i % stitches.size()));
isUpper2[i - (startIndex + 1)] = startFromUpper[i % stitches.size()];
}

makeResult(ret, color, path, isUpper2);
}

}

int numPoints = 0;
for (Integer color : colorToPoints.keySet()) {
numPoints += colorToPoints.get(color).size();
}
lengthFront = Math.sqrt(2) * 2 * numPoints;

double score = calculateRawScore(lengthFront, lengthBack);
Utils.debug("score", (int) (1e6 * score), "front", (int) (1e2 * lengthFront), "back", (int) (1e2 * lengthBack), "time", watch.getSecondString());
Utils.debug("score", (int) (1e6 * calculateRawScore(lengthFront, sumBackLength)), "front", (int) (1e2 * lengthFront), "back", (int) (1e2 * sumBackLength), "time", watch.getSecondString());
Utils.debug("sumLoops", sumLoops, "try/loop", String.format("%.1f%%", (double) 100.0 * sumTries / sumLoops), "AC/try", String.format("%.1f%%", (double) 100.0 * sumAccepts / sumTries));

return (String[]) ret.toArray(new String[ret.size()]);
}

private ArrayList<Stitch> greedy(Integer color, ArrayList<Point> path) {

ArrayList<Stitch> ret = new ArrayList<>();
if (path.size() == 1) {

Point point = path.get(0);

int minD = 0;

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2]), new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4])));

return ret;
}

Point previousPoint = null;
for (int i = 0; i < path.size() - 1; i++) {
Point point = path.get(i);
Point nextPoint = path.get(i + 1);

if (i == 0) {

double minDistance = 1e9;
int minD = -1;
for (int d = 0; d < dr.length; d++) {
double distance = distance(point.r + dr[d], point.c + dc[d], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distance < minDistance) {
minDistance = distance;
minD = d;
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4]), new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2]), new Point(point.r + dr[minD], point.c + dc[minD])));

previousPoint = new Point(point.r + dr[minD], point.c + dc[minD]);

} else {

double minDistance = 1e9;
int minD = -1;
int minD2 = -1;
for (int d = 0; d < dr.length; d++) {
if (point.r + dr[d] == previousPoint.r && point.c + dc[d] == previousPoint.c) {
continue;
}
double distanceToPrevious = distance(point.r + dr[d], point.c + dc[d], previousPoint.r, previousPoint.c);

{
int d2 = (d + 1) % 4;
double distance = distance(point.r + dr[d2], point.c + dc[d2], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distanceToPrevious + distance < minDistance) {
minDistance = distanceToPrevious + distance;
minD = d;
minD2 = d2;
}
}
{
int d2 = (d + 3) % 4;
double distance = distance(point.r + dr[d2], point.c + dc[d2], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distanceToPrevious + distance < minDistance) {
minDistance = distanceToPrevious + distance;
minD = d;
minD2 = d2;
}
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[minD2 ^ 2], point.c + dc[minD2 ^ 2]), new Point(point.r + dr[minD2], point.c + dc[minD2])));

previousPoint = new Point(point.r + dr[minD2], point.c + dc[minD2]);

}
}
{

Point point = path.get(path.size() - 1);

double minDistance = 1e9;
int minD = -1;
for (int d = 0; d < dr.length; d++) {
if (previousPoint != null && point.r + dr[d] == previousPoint.r && point.c + dc[d] == previousPoint.c) {
continue;
}
double distanceToPrevious = distance(point.r + dr[d], point.c + dc[d], previousPoint.r, previousPoint.c);
if (distanceToPrevious < minDistance) {
minDistance = distanceToPrevious;
minD = d;
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2]), new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4])));

previousPoint = new Point(point.r + dr[minD], point.c + dc[minD]);

}
return ret;
}

private int greedyLoop = 0;
private int greedyTry = 0;
private int greedyAC = 0;
private int greedyImprove = 0;

private void greedy2opt(ArrayList<Stitch> stitches, boolean[] startFromUpper) {
for (int i = 0; i < stitches.size(); i++) {
for (int i2 = i + 1; i2 <= i + 64; i2++) {
greedyLoop++;
if (i2 < 0 || i2 >= stitches.size()) {
continue;
}

int B = i;
int A = B - 1;
if (A < 0) {
A = stitches.size() - 1;
}

int C = i2;
int D = C + 1;
if (D == stitches.size()) {
D = 0;
}

Point pointA = startFromUpper[A] ? stitches.get(A).lower : stitches.get(A).upper;
Point pointB = startFromUpper[B] ? stitches.get(B).upper : stitches.get(B).lower;
double distanceAB = distance(pointA.r, pointA.c, pointB.r, pointB.c);
if (distanceAB < 1e-9) {
distanceAB = 1e9;
}
if (pointA.r < 0 || pointB.r < 0) {
distanceAB = 0;
}
Point pointC = startFromUpper[C] ? stitches.get(C).lower : stitches.get(C).upper;
Point pointD = startFromUpper[D] ? stitches.get(D).upper : stitches.get(D).lower;
double distanceCD = distance(pointC.r, pointC.c, pointD.r, pointD.c);
if (distanceCD < 1e-9) {
distanceCD = 1e9;
}
if (pointC.r < 0 || pointD.r < 0) {
distanceCD = 0;
}
double AB_CD = distanceAB + distanceCD;
double distanceAC = distance(pointA.r, pointA.c, pointC.r, pointC.c);
if (distanceAC < 1e-9) {
continue;
}
if (pointA.r < 0 || pointC.r < 0) {
distanceAC = 0;
}
double distanceBD = distance(pointB.r, pointB.c, pointD.r, pointD.c);
if (distanceBD < 1e-9) {
continue;
}
if (pointB.r < 0 || pointD.r < 0) {
distanceBD = 0;
}
double AC_BD = distanceAC + distanceBD;

greedyTry++;
if (AC_BD < AB_CD) {
greedyAC++;
greedyImprove += AB_CD - AC_BD;
if (B <= C) {
for (int l = B, r = C; l <= r; l++, r--) {
if (l < r) {
Collections.swap(stitches, l, r);

boolean swap = !startFromUpper[l];
startFromUpper[l] = !startFromUpper[r];
startFromUpper[r] = swap;
} else {
startFromUpper[l] = !startFromUpper[l];
}
}
} else {
for (int l = C + 1, r = B - 1; l <= r; l++, r--) {
if (l < r) {
Collections.swap(stitches, l, r);

boolean swap = !startFromUpper[l];
startFromUpper[l] = !startFromUpper[r];
startFromUpper[r] = swap;
} else {
startFromUpper[l] = !startFromUpper[l];
}
}
}
}

}
}
}

private double calculateRawScore(double front, double back) {
return Math.max(0, Math.pow((5 - back / front) / 5, 3));
}

private void findNearestCities(ArrayList<Stitch> stitches) {
stitch2nearestStitches = new IntArray[numStitches];
for (int i = 0; i < numStitches; i++) {
ArrayList<Pair<Double, Integer>> list = new ArrayList<>();
for (int j = 0; j < numStitches; j++) {
if (j == i) {
continue;
}
list.add(new Pair<Double, Integer>(distancesStitchTo4PointOfStitch[2 * i][2 * j], j));
}
Collections.sort(list);
stitch2nearestStitches[i] = new IntArray();
for (int j = 0; j < Math.min(Math.max(20, 10000 / numStitches), list.size()); j++) {
stitch2nearestStitches[i].add(list.get(j).second);
}
}
}

Watch eachColorWatch = new Watch();

private void improve(double second, ArrayList<Stitch> stitches) {
double score = calculateScore();
double endTemperature = 0, startTemperature = 1e-3, expTemperature = 1.0, temperature = startTemperature;
double startTime = eachColorWatch.getSecond(), endTime = second, time = startTime;
int loop = 0;

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

for (;; loop++) {
if ((loop & mask) == mask) {
time = eachColorWatch.getSecond();

if (time >= endTime) {
sumLoops += loop;
break;
}

temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature);

}

if (xorShift.nextDouble() < 1.5) {
int B = 1 + (int) ((numStitches - 1) * xorShift.nextDouble());
int A = B - 1;
IntArray nearestStitches = stitch2nearestStitches[index2stitch[A]];
int randomIndex = (int) (nearestStitches.length * xorShift.nextDouble());
int stitch = nearestStitches.values[randomIndex];
int c = stitch2index[stitch];

int C = c;
int D = c + 1;
if (D == numStitches) {
D = 0;
}
double distanceAB = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 0 : 2));
double distanceCD = distance(index2stitch[C], index2stitch[D], (startFromUpper[index2stitch[C]] ? 1 : 0) + (startFromUpper[index2stitch[D]] ? 0 : 2));
double AB_CD = distanceAB + distanceCD;
double distanceAC = distance(index2stitch[A], index2stitch[C], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[C]] ? 2 : 0));
double distanceBD = distance(index2stitch[B], index2stitch[D], (startFromUpper[index2stitch[B]] ? 0 : 1) + (startFromUpper[index2stitch[D]] ? 0 : 2));
double AC_BD = distanceAC + distanceBD;

sumTries++;
if (AC_BD <= AB_CD || (-AC_BD + AB_CD > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-AC_BD + AB_CD) / (score * temperature)))) {
if (!isValidCurrentFlip(A, C)) {
sumTries--;
continue;
}
if (!isValidFlipCurrent(B, D)) {
sumTries--;
continue;
}
sumAccepts++;

score += (AC_BD - AB_CD);
if (B <= C) {
for (int l = B, r = C; l <= r; l++, r--) {
int swap = index2stitch[l];
index2stitch[l] = index2stitch[r];
index2stitch[r] = swap;

stitch2index[index2stitch[l]] = l;
stitch2index[index2stitch[r]] = r;

startFromUpper[index2stitch[l]] = !startFromUpper[index2stitch[l]];
if (l < r) {
startFromUpper[index2stitch[r]] = !startFromUpper[index2stitch[r]];
}
}
} else {
for (int l = C + 1, r = B - 1; l <= r; l++, r--) {
int swap = index2stitch[l];
index2stitch[l] = index2stitch[r];
index2stitch[r] = swap;

stitch2index[index2stitch[l]] = l;
stitch2index[index2stitch[r]] = r;

startFromUpper[index2stitch[l]] = !startFromUpper[index2stitch[l]];
if (l < r) {
startFromUpper[index2stitch[r]] = !startFromUpper[index2stitch[r]];
}
}
}
}
} else {

int A = (int) (numStitches * xorShift.nextDouble());
int B = A + 1;
if (B == numStitches) {
B = 0;
}
int C = B + 1;
if (C == numStitches) {
C = 0;
}

if (!isValidCurrentFlip(A, B)) {
continue;
}
if (!isValidFlipCurrent(B, C)) {
continue;
}
double ABC = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 0 : 2)) + distance(index2stitch[B], index2stitch[C], (startFromUpper[index2stitch[B]] ? 1 : 0) + (startFromUpper[index2stitch[C]] ? 0 : 2));
double nextABC = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 2 : 0)) + distance(index2stitch[B], index2stitch[C], (startFromUpper[index2stitch[B]] ? 0 : 1) + (startFromUpper[index2stitch[C]] ? 0 : 2));

if (nextABC <= ABC || (-nextABC + ABC > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-nextABC + ABC) / (score * temperature)))) {

score += (nextABC - ABC);

startFromUpper[index2stitch[B]] = !startFromUpper[index2stitch[B]];

}

}
}
}

private boolean isValidCurrentFlip(int A, int C) {
if (startFromUpper[index2stitch[A]]) {
Point pointALower = stitches.get(index2stitch[A]).lower;
if (startFromUpper[index2stitch[C]]) {
Point pointCLooer = stitches.get(index2stitch[C]).lower;
if (pointALower.r == pointCLooer.r && pointALower.c == pointCLooer.c) {
return false;
}
} else {
Point pointCUpper = stitches.get(index2stitch[C]).upper;
if (pointALower.r == pointCUpper.r && pointALower.c == pointCUpper.c) {
return false;
}
}
} else {
Point pointAUpper = stitches.get(index2stitch[A]).upper;
if (startFromUpper[index2stitch[C]]) {
Point pointCLooer = stitches.get(index2stitch[C]).lower;
if (pointAUpper.r == pointCLooer.r && pointAUpper.c == pointCLooer.c) {
return false;
}
} else {
Point pointCUpper = stitches.get(index2stitch[C]).upper;
if (pointAUpper.r == pointCUpper.r && pointAUpper.c == pointCUpper.c) {
return false;
}
}
}
return true;
}

private boolean isValidFlipCurrent(int B, int D) {
if (startFromUpper[index2stitch[B]]) {
Point pointBUpper = stitches.get(index2stitch[B]).upper;
if (startFromUpper[index2stitch[D]]) {
Point pointDUpper = stitches.get(index2stitch[D]).upper;
if (pointBUpper.r == pointDUpper.r && pointBUpper.c == pointDUpper.c) {
return false;
}
} else {
Point pointDLower = stitches.get(index2stitch[D]).lower;
if (pointBUpper.r == pointDLower.r && pointBUpper.c == pointDLower.c) {
return false;
}
}
} else {
Point pointBLower = stitches.get(index2stitch[B]).lower;
if (startFromUpper[index2stitch[D]]) {
Point pointDUpper = stitches.get(index2stitch[D]).upper;
if (pointBLower.r == pointDUpper.r && pointBLower.c == pointDUpper.c) {
return false;
}
} else {
Point pointDLower = stitches.get(index2stitch[D]).lower;
if (pointBLower.r == pointDLower.r && pointBLower.c == pointDLower.c) {
return false;
}
}
}
return true;
}

private double distance(int AFrom, int BTo, int deltaIndex) {
if (stitches.get(AFrom).upper.r < 0 || stitches.get(BTo).upper.r < 0) {
return 0;
}
int r0 = (deltaIndex & 1) == 0 ? stitches.get(AFrom).upper.r : stitches.get(AFrom).lower.r;
int c0 = (deltaIndex & 1) == 0 ? stitches.get(AFrom).upper.c : stitches.get(AFrom).lower.c;
int r1 = (deltaIndex & 2) == 0 ? stitches.get(BTo).upper.r : stitches.get(BTo).lower.r;
int c1 = (deltaIndex & 2) == 0 ? stitches.get(BTo).upper.c : stitches.get(BTo).lower.c;
return distance(r0, c0, r1, c1);
}

private void initializeIndex(ArrayList<Stitch> stitches) {
index2stitch = new int[numStitches];
stitch2index = new int[numStitches];
startFromUpper = new boolean[numStitches];
for (int i = 0; i < index2stitch.length; i++) {
index2stitch[i] = i;
stitch2index[index2stitch[i]] = i;
startFromUpper[i] = true;
if (i == 0) {

} else {
if (startFromUpper[i - 1]) {
if (stitches.get(i).upper.r == stitches.get(i - 1).lower.r && stitches.get(i).upper.c == stitches.get(i - 1).lower.c) {
startFromUpper[i] = !true;
}
} else {
if (stitches.get(i).upper.r == stitches.get(i - 1).upper.r && stitches.get(i).upper.c == stitches.get(i - 1).upper.c) {
startFromUpper[i] = !true;
}
}
}
}

}

private void setDistance(ArrayList<Stitch> stitches) {
int n = 10;
int clusterSize = (S + 1) / n + ((S + 1) % n > 0 ? 1 : 0);
IntArray[][] cluster = new IntArray[clusterSize][clusterSize];
for (int r = 0; r < cluster.length; r++) {
for (int c = 0; c < cluster[r].length; c++) {
cluster[r][c] = new IntArray();
}
}
for (int i = 0; i < numStitches; i++) {
Stitch stitch = stitches.get(i);
int clusterR = stitch.upper.r / n;
int clusterC = stitch.upper.c / n;
cluster[clusterR][clusterC].add(i);
}

PriorityQueue[] distanceStitchToStitch = new PriorityQueue[numStitches];
for (int i = 0; i < distanceStitchToStitch.length; i++) {
distanceStitchToStitch[i] = new PriorityQueue<Pair<Double, Integer>>(new Comparator<Pair<Double, Integer>>() {
@Override
public int compare(Pair<Double, Integer> o1, Pair<Double, Integer> o2) {
if (o1.first.doubleValue() > o2.first.doubleValue()) {
return -1;
}
if (o1.first.doubleValue() < o2.first.doubleValue()) {
return 1;
}
return 0;
}
});
}
for (int i = 0; i < numStitches; i++) {
Stitch stitch = stitches.get(i);

int clusterR = stitch.upper.r / n;
int clusterC = stitch.upper.c / n;

for (int r = clusterR - 1; r <= clusterR + 1; r++) {
if (r < 0 || r >= cluster.length) {
continue;
}
for (int c = clusterC - 1; c <= clusterC + 1; c++) {
if (c < 0 || c >= cluster[r].length) {
continue;
}

for (int k = 0; k < cluster[r][c].length; k++) {

int j = cluster[r][c].values[k];
if (j == i) {
continue;
}
Stitch stitchJ = stitches.get(j);
if (stitch.upper.r < 0 || stitchJ.upper.r < 0) {
distanceStitchToStitch[i].add(new Pair<Double, Integer>(0.0, j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
} else {
double dx = stitchJ.upper.c - stitch.upper.c;
double dy = stitchJ.upper.r - stitch.upper.r;
distanceStitchToStitch[i].add(new Pair<Double, Integer>(Math.sqrt(dx * dx + dy * dy), j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
}

}

{

int j = numStitches - 1;
if (j == i) {
continue;
}
Stitch stitchJ = stitches.get(j);
if (stitch.upper.r < 0 || stitchJ.upper.r < 0) {
distanceStitchToStitch[i].add(new Pair<Double, Integer>(0.0, j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
} else {
double dx = stitchJ.upper.c - stitch.upper.c;
double dy = stitchJ.upper.r - stitch.upper.r;
distanceStitchToStitch[i].add(new Pair<Double, Integer>(Math.sqrt(dx * dx + dy * dy), j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
}

}

}
}
}

distancesStitchTo4PointOfStitch = new double[numStitches][4 * 32];
stitch2nearestStitches = new IntArray[numStitches];
stitch2nearestStitchIndex2index = new HashMap<Integer, HashMap<Integer, Integer>>();

for (int i = 0; i < numStitches; i++) {
stitch2nearestStitches[i] = new IntArray(32);
for (int j = 0; !distanceStitchToStitch[i].isEmpty(); j++) {
Pair<Double, Integer> distanceAndStitchIndexPair = (Pair<Double, Integer>) distanceStitchToStitch[i].poll();
int k = 4 * j;

Stitch stitchFrom = stitches.get(i);
Stitch stitchTo = stitches.get(distanceAndStitchIndexPair.second.intValue());
if (stitchFrom.upper.r < 0 || stitchTo.upper.r < 0) {
distancesStitchTo4PointOfStitch[i][k + 0] = 0;
distancesStitchTo4PointOfStitch[i][k + 1] = 0;
distancesStitchTo4PointOfStitch[i][k + 2] = 0;
distancesStitchTo4PointOfStitch[i][k + 3] = 0;
} else {
distancesStitchTo4PointOfStitch[i][k + 0] = distance(stitchFrom.upper.r, stitchFrom.upper.c, stitchTo.upper.r, stitchTo.upper.c);
distancesStitchTo4PointOfStitch[i][k + 1] = distance(stitchFrom.upper.r, stitchFrom.upper.c, stitchTo.lower.r, stitchTo.lower.c);
distancesStitchTo4PointOfStitch[i][k + 2] = distance(stitchFrom.lower.r, stitchFrom.lower.c, stitchTo.upper.r, stitchTo.upper.c);
distancesStitchTo4PointOfStitch[i][k + 3] = distance(stitchFrom.lower.r, stitchFrom.lower.c, stitchTo.lower.r, stitchTo.lower.c);
}
stitch2nearestStitches[i].add(distanceAndStitchIndexPair.second.intValue());

if (stitch2nearestStitchIndex2index.get(i) == null) {
stitch2nearestStitchIndex2index.put(i, new HashMap<Integer, Integer>());
}
stitch2nearestStitchIndex2index.get(i).put(distanceAndStitchIndexPair.second, k);
}
}
}

private double[] currentDistance;

private double calculateScore() {
double score = 0.0;
currentDistance = new double[numStitches];
for (int i = 0; i < numStitches; i++) {
int j = i + 1;
if (j == numStitches) {
j = 0;
}
int from = index2stitch[i];
int to = index2stitch[j];
double distance = distance(from, to, (startFromUpper[from] ? 1 : 0) + (startFromUpper[to] ? 0 : 2));
score += distance;
currentDistance[from] = distance;
}
return score;
}

private static final int[] dr = new int[] { 0, 0, 1, 1, };
private static final int[] dc = new int[] { 0, 1, 1, 0, };

private void makeResult(ArrayList<String> ret, Integer color, ArrayList<Stitch> path, boolean[] isUpper) {
ret.add("" + (char) (color + 'a'));

for (int i = 0; i < path.size(); i++) {

Stitch stitch = path.get(i);

if (isUpper[i]) {
ret.add(stitch.upper.r + " " + stitch.upper.c);
if (i == 0) {
lengthBack += 0;
} else {
Stitch previousStitch = path.get(i - 1);
if (isUpper[i - 1]) {
lengthBack += distance(stitch.upper.r, stitch.upper.c, previousStitch.lower.r, previousStitch.lower.c);
} else {
lengthBack += distance(stitch.upper.r, stitch.upper.c, previousStitch.upper.r, previousStitch.upper.c);
}
}
ret.add(stitch.lower.r + " " + stitch.lower.c);
lengthFront += Math.sqrt(2);
} else {
ret.add(stitch.lower.r + " " + stitch.lower.c);
if (i == 0) {
lengthBack += 0;
} else {
Stitch previousStitch = path.get(i - 1);
if (isUpper[i - 1]) {
lengthBack += distance(stitch.lower.r, stitch.lower.c, previousStitch.lower.r, previousStitch.lower.c);
} else {
lengthBack += distance(stitch.lower.r, stitch.lower.c, previousStitch.upper.r, previousStitch.upper.c);
}
}
ret.add(stitch.upper.r + " " + stitch.upper.c);
lengthFront += Math.sqrt(2);
}

}
}

private void init(String[] pattern) {
S = pattern.length;

for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {

char charAt = pattern[r].charAt(c);
if (charAt == '.') {
continue;
}

int color = charAt - 'a';

if (colorToPoints.get(color) == null) {
colorToPoints.put(color, new ArrayList<Point>());
}
colorToPoints.get(color).add(new Point(r, c));

if (colorToStitches.get(color) == null) {
colorToStitches.put(color, new ArrayList<Stitch>());
}
colorToStitches.get(color).add(new Stitch(new Point(r, c), new Point(r + 1, c + 1)));
colorToStitches.get(color).add(new Stitch(new Point(r + 1, c), new Point(r, c + 1)));
}
}

{
int numColors = colorToPoints.keySet().size();
int numPoints = 0;
for (Integer color : colorToPoints.keySet()) {
numPoints += colorToPoints.get(color).size();
}
Utils.debug("S", S, "numColors", numColors, "numPoints", numPoints);
}
}

private double distance(double r0, double c0, double r1, double c1) {
double dr = r1 - r0;
double dc = c1 - c0;
return Math.sqrt(dr * dr + dc * dc);
}

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

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

CrossStitch cs = new CrossStitch();
String[] ret = cs.embroider(pattern);

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 Point {
int r;
int c;

public Point(int r, int c) {
super();
this.r = r;
this.c = c;
}
}

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 EuclideanTravellingSalesmanProblem {
private int N;
private int[] x;
private int[] y;
private XorShift xorShift = new XorShift(System.nanoTime());
private double[][] distance;
private int[] index2city;
private int[] city2index;
private IntArray[] city2nearestCities;

private Watch watch = new Watch();

public int[] getOrder(int[] x, int[] y, double second) {
watch.init();

this.N = x.length;
this.x = x;
this.y = y;
setDistance();
findNearestCities();
initializeIndex();
improve(second);
return index2city;
}

private void findNearestCities() {
city2nearestCities = new IntArray[N];
for (int i = 0; i < N; i++) {
ArrayList<Pair<Double, Integer>> list = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (j == i) {
continue;
}
list.add(new Pair<Double, Integer>(distance[i][j], j));
}
Collections.sort(list);
city2nearestCities[i] = new IntArray();
for (int j = 0; j < Math.min(Math.max(20, 10000 / N), list.size()); j++) {
city2nearestCities[i].add(list.get(j).second);
}
}
}

int loop = 0;
int tries = 0;
int ac = 0;

private void improve(double second) {
double score = getScore();
double endTemperature = 0, startTemperature = 1e-3, expTemperature = 1.5, temperature = startTemperature;
double startTime = watch.getSecond(), endTime = second, time = startTime;

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

for (;; loop++) {
if ((loop & mask) == mask) {
time = watch.getSecond();

if (time >= endTime) {
break;
}

temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature);

}

int B = 1 + (int) ((N - 1) * xorShift.nextDouble());
int A = B - 1;
IntArray s = city2nearestCities[index2city[A]];
int c = city2index[s.values[(int) (s.length * xorShift.nextDouble())]];

int C = c;
int D = c + 1;
if (D == N) {
D = 0;
}
double ABCDEF = distance[index2city[A]][index2city[B]] + distance[index2city[C]][index2city[D]];
double ACBDEF = distance[index2city[A]][index2city[C]] + distance[index2city[B]][index2city[D]];
tries++;
if (ACBDEF <= ABCDEF || (-ACBDEF + ABCDEF > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-ACBDEF + ABCDEF) / (score * temperature)))) {
ac++;
score = score + (ACBDEF - ABCDEF);

if (B <= C) {
for (int l = B, r = C; l < r; l++, r--) {
int swap = index2city[l];
index2city[l] = index2city[r];
index2city[r] = swap;
city2index[index2city[l]] = l;
city2index[index2city[r]] = r;
}
} else {
for (int l = C + 1, r = B - 1; l < r; l++, r--) {
int swap = index2city[r];
index2city[r] = index2city[l];
index2city[l] = swap;
city2index[index2city[r]] = r;
city2index[index2city[l]] = l;
}
}
}
}
}

private void initializeIndex() {
index2city = new int[N];
city2index = new int[N];
for (int i = 0; i < index2city.length; i++) {
index2city[i] = i;
city2index[index2city[i]] = i;
}

}

private void setDistance() {
distance = new double[N][N];
for (int i = 0; i < distance.length; i++) {
for (int j = 0; j < i; j++) {
if (x[i] < 0 || x[j] < 0) {
distance[i][j] = 0;
} else {
double dx = x[i] - x[j];
double dy = y[i] - y[j];
distance[i][j] = Math.sqrt(dx * dx + dy * dy);
}
distance[j][i] = distance[i][j];
}
}
}

private double getScore() {
double score = 0.0;
for (int i = 0; i < N; i++) {
int j = i + 1;
if (j == N) {
j = 0;
}
int from = index2city[i];
int to = index2city[j];
score += distance[from][to];
}
return score;
}

}

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) {
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 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 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 Stitch {
Point upper;
Point lower;

public Stitch(Point a, Point b) {
super();
this.upper = a;
this.lower = b;
}

}

このページのトップヘ