EvbCFfp1XB

problem and my answer.

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

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

}

Rank 171 / 3508

Approach


最初に最短経路を求めておく。
各ターンは次のような貪欲法:
  • 5ターン目に最初の爆弾をプロダクションが最も大きい最も近い相手の工場に投げる。
    最初の爆弾が届いたら次の爆弾を送る。
  • 軍隊をシミュレーションして、自分の工場が相手のものにならないように、近くの工場から、できるだけ少ない軍隊で助ける。
  • プロダクションが0より大きいニュートラルの工場にできるだけ少ない軍隊を最短経路で送る。
  • プロダクションをできるだけ上げる。
  • 最も近い相手の工場に残りの軍隊を最短経路で送る。

Approach in Engliish(Google Translate)

First find the shortest path.

Each turn is like the following greedy:

  • On the fifth turn, the first bomb is thrown to the closest opponent's factory whose production is the largest.
  • When the first bomb arrives, send the next bomb.
  • Simulate the army and help with as few armies as possible from the nearby factory so that your factory will not be your opponent.
  • Send the fewest possible troops to the neutral factory whose production is greater than 0 on the shortest path.
  • Increase production as much as possible.
  • Send the remaining troops to the closest partner 's factory with the shortest route.


source code


Codingame はソースそのままはダメなんだね。どうりでないと思った。


このページのトップヘ