EvbCFfp1XB

problem and my answer.


Approach

問題を読んでSAで良さそうだなと思った。

Visualizer の int[][] component が何回も初期化されていたのを、一回だけ初期化して使いまわして高速化した。
中央の Component 1個だけ score を計算して高速化した。

近傍は Visualizer で言うと int[] perm のランダムに2つ選んで交換するだけ。

seed3 のスコアは約1.6e6

ここまでが submission1 SA

制限時間を10倍にすると、seed3 のスコアは約2e6 になった。
高速化に効果があることが分かったが、
Visuallizer を見ると思ったより小さいエリアしか使えていなかった。

スコアを計算する範囲を中央の方から広げて, greedy に解を作ることにする。
0回目のループ  perm[S/2] と perm[j] を交換して、[S/2,S/2]*[S/2,S/2] のスコアが最もよい j を選ぶ (0<=j<S)。
1回目のループ  perm[S/2-1] と perm[j] を交換して、[S/2-1,S/2]*[S/2-1,S/2] のスコアが最もよい j を選ぶ (0<=j<S)。
2回目のループ  perm[S/2+1] と perm[j] を交換して、[S/2-1,S/2+1]*[S/2-1,S/2+1] のスコアが最もよい j を選ぶ (0<=j<S)。
.
.
.
S-1回目のループ  perm[0またはS-1] と perm[j] を交換して、[0,S-1]*[0,S-1] のスコアが最もよい j を選ぶ (0<=j<S)。

seed3 のスコアは約5e6

”スコアが最もよい j ”は、既に決めたところから選ばれることがほとんどなかったので、選ばないようにした。
そうすると、スコアを差分だけ計算して高速化できた。

ここまでが submission2 greedy

greedy より beam search の方がいいはず。

制限時間を無視して、ビーム幅 10 で seed3 のスコアは7e6以上、
ビーム幅 100 で 8e6以上出ることもあった。

時間調整して、平均ビーム幅約8 seed3 のスコアは約6e6

ここまでが submission3 beam search

バグを修正したりしてコーディングフェーズ終わり、submission4

結局、seed1 は beam search より SA の方が良かったので、もう一週間あればSAの高速化を頑張ったかも。

以上。


追記 beam search を中央からじゃなくて左上から右下にしたら約7%良くなった。








source code (submission4 ) 左上から右下バージョンは次です

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

public class ConnectedComponent {
private static final int[] dr = { 0, 1, 0, -1, };
private static final int[] dc = { -1, 0, 1, 0, };

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

private SAState sa = new SAState();

private int S;
private int[][] original;

private double score;
private double bestScore;
private int[] solution;
private int[] bestSolution;

public int[] permute(int[] matrix) {
init(matrix);

solve();

Utils.debug("time", watch.getSecond(), "score", score, "countSets", countSets);

return solution;
}

private void init(int[] matrix) {
S = (int) Math.sqrt(matrix.length);

original = new int[S][S];
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
original[r][c] = matrix[r * S + c];
}
}

int numElements = 0;
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
if (original[r][c] != 0) {
numElements++;
}
}
}

component = new int[S][S];

moveHistory = new int[S];

hashHistory = new long[S];

Utils.debug("S", S, "numElements", numElements, String.format("%.1f%%", 100.0 * numElements / (S * S)));
}

private void solve() {
solution = new int[S];
for (int i = 0; i < solution.length; i++) {
solution[i] = i;
}

sa.startTemperature = 1.0 / S;

{
int maxBeamWidth = (int) (50.0 + (10000.0 - 50.0) * (500.0 - S) / (500.0 - 50.0));
ArrayList<State> moves = beamsearch(S, maxBeamWidth);
assert turn == 0;

if (moves == null) {
Utils.debug("moves == null");
}
for (State state : moves) {
next(state.j);
}

sa.startTemperature = 1e-3;
}

score = calculateScoreFromCenter();

bestSolution = Arrays.copyOf(solution, solution.length);
bestScore = score;

Utils.debug();
Utils.debug("score", score);
Utils.debug();

SA();
}

private int[] is;
private int[] minRanges;
private int[] maxRanges;
private int countSets = 0;

private ArrayList<State> beamsearch(int maxDepth, int maxBeamWidth) {
{
is = new int[S];
minRanges = new int[S];
maxRanges = new int[S];

int minRange = S - 1;
int maxRange = 0;
for (int isi = 0, i = S / 2, delta = 0; i >= 0 && i < S; delta = (1 + Math.abs(delta)) * (Integer.signum(delta) >= 0 ? -1 : 1), i += delta) {
is[isi] = i;
minRange = Math.min(minRange, i);
maxRange = Math.max(maxRange, i);
minRanges[isi] = minRange;
maxRanges[isi] = maxRange;
isi++;
}
}

int mask = (1 << (int) (Math.sqrt(500 / S))) - 1;

ArrayList<State> currents = new ArrayList<>();
ArrayList<State> nexts = new ArrayList<>();
State best = null;
currents.add(null);

double startTime = watch.getSecond();
double endTime = 9.5;

double sum = (1.0 + 1.0) * (maxDepth) / 2.0;

double[] timelimits = new double[maxDepth];
for (int i = 0; i < maxDepth; i++) {
if (i == 0) {
timelimits[i] = (endTime - startTime) * (1.0 + (1.0 - 1.0) * (i - 0.0) / (maxDepth - 1 - 0.0)) / sum;
} else {
timelimits[i] = timelimits[i - 1] + (endTime - startTime) * (1.0 + (1.0 - 1.0) * (i - 0.0) / (maxDepth - 1 - 0.0)) / sum;
}
}

for (int depth = 0; depth < maxDepth; depth++) {
if (currents.size() == 0) {
break;
}

int beamWidth = Math.min(maxBeamWidth, currents.size());

CollectionsUtils.select(currents, 0, currents.size(), beamWidth);
CollectionsUtils.sort(currents, 0, beamWidth - 1);

for (int beam = 0; beam < beamWidth; beam++) {
State currentState = currents.get(beam);

if (currentState == null) {
} else {
if (best == null || currentState.compareTo(best) < 0) {
best = currentState;
}
}

if (depth == maxDepth - 1) {
break;
}

set(reverse(toList(currentState)), 0);
countSets++;

int currentSum = 0;
int currentSize = 0;
if (depth > 0) {
calculateScoreFromCenterUsingField2(minRanges[depth - 1], maxRanges[depth - 1]);
currentSum = sumBase;
currentSize = sizeBase;
} else {
}

int bestNComp = nComp;

int i = is[depth];
for (int j = 0; j < S; j++) {
if (j >= minRanges[depth] && j <= maxRanges[depth]) {
if (j == i) {
} else {
continue;
}
}

next(j);

calculateScoreForGreedyUpdateField(minRanges[depth], maxRanges[depth], currentSum, currentSize, depth == 0 ? 0 : (is[depth] - is[depth - 1]), bestNComp);
double score = (sum3 * Math.sqrt(size3));

State next = new State();
next.parent = currentState;
next.j = j;
next.score = score;
next.hash = hash;
nexts.add(next);

previous();
}
if ((beam & mask) == 0) {
if (watch.getSecond() >= timelimits[depth]) {
break;
}
}
}
{
ArrayList<State> swap = currents;
currents = nexts;
nexts = swap;
}
nexts.clear();
}

for (; turn > 0;) {
previous();
}

if (best == null) {
return null;
}

return reverse(toList(best));
}

private ArrayList<State> reverse(ArrayList<State> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

private ArrayList<State> toList(State state2) {
ArrayList<State> res = new ArrayList<>();
for (State current = state2; current != null; current = current.parent) {
res.add(current);
}
return res;
}

private int[] moveHistory;
private int turn = 0;
private long[] hashHistory;
private long hash;

private void next(int j) {
moveHistory[turn] = j;
hashHistory[turn] = hash;

swap(is[turn], j);

hash = hash * 503 + j;

turn++;
}

private void previous() {
turn--;
swap(is[turn], moveHistory[turn]);
hash = hashHistory[turn];
}

private void set(ArrayList<State> list, int startIndex) {
int startIndexMinus1 = startIndex - 1;
for (int i = 0; i < list.size() && startIndex + i < moveHistory.length; i++) {
int j = moveHistory[startIndex + i];
State state = list.get(i);
if (state.j == j) {
startIndexMinus1 = startIndex + i;
continue;
}
break;
}

for (; turn > startIndexMinus1 + 1;) {
previous();
}
for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
State state2 = list.get(i);
next(state2.j);
}
}

private void SA() {
double second = 1;
int mask = (1 << 5) - 1;

sa.startTime = watch.getSecond();
sa.endTime = 9.5;

for (sa.loop = 0;; sa.loop++) {

if ((sa.loop & mask) == 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("%.4f", bestScore), String.format("%.6f", sa.temperature));
break;
}

sa.updateTemperature();
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("%.4f", bestScore), String.format("%.6f", sa.temperature));
}
}

swap();

}
}

private void swap() {
int i = (int) (S * rng.nextDouble());
int j = (int) ((S - 1) * rng.nextDouble());
if (j >= i) {
j++;
}

assert j != i;

swap(i, j);

double newScore = calculateScoreFromCenter();

sa.countChange++;
if (newScore >= score || sa.accept(newScore, score)) {
sa.countAccept++;

score = newScore;

saveBest();

} else {
swap(i, j);
}
}

private void swap(int i, int j) {
int swap = solution[i];
solution[i] = solution[j];
solution[j] = swap;
}

private int[][] component;
private static final int[] queue = new int[500 * 500];
private int nComp = 0;

private double calculateScoreFromCenter() {
int currentNumComponents = nComp;
double maxSum = -1e9;
for (int i = S / 2 - 1; i <= S / 2 + 1; i++) {
for (int j = S / 2 - 1; j <= S / 2 + 1; j++) {
if (original[solution[i]][solution[j]] == 0)
continue;
if (component[i][j] > currentNumComponents)
continue;

int size = 0;
double sum = 0;
nComp++;

component[i][j] = nComp;
queue[size] = (i << 10) | (j);
size++;
sum += original[solution[i]][solution[j]];

for (int ind = 0; ind < size; ind++) {
for (int d = 0; d < 4; d++) {
int newr = ((queue[ind] >>> 10) & 1023) + dr[d];
int newc = (queue[ind] & 1023) + dc[d];
if (newr < 0 || newc < 0 || newr >= S || newc >= S)
continue;
if (component[newr][newc] > currentNumComponents || original[solution[newr]][solution[newc]] == 0) {
continue;
}
component[newr][newc] = nComp;
queue[size] = (newr << 10) | (newc);
size++;
sum += original[solution[newr]][solution[newc]];
}
}
sum *= Math.sqrt(size);
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}

private int sumBase;
private int sizeBase;

private void calculateScoreFromCenterUsingField2(int minRange, int maxRange) {

int currentNumComponents = nComp;
int i = S / 2;
int j = S / 2;

sizeBase = 0;
sumBase = 0;
nComp++;

if (original[solution[i]][solution[j]] == 0) {
return;
}

component[i][j] = nComp;
queue[sizeBase] = (i << 10) | (j);
sizeBase++;
sumBase += original[solution[i]][solution[j]];

for (int ind = 0; ind < sizeBase; ind++) {
int r = (queue[ind] >>> 10) & 1023;
int c = queue[ind] & 1023;
for (int d = 0; d < 4; d++) {
int newr = r + dr[d];
if (newr < minRange || newr > maxRange) {
continue;
}
int newc = c + dc[d];
if (newc < minRange || newc > maxRange) {
continue;
}
if (component[newr][newc] > currentNumComponents || original[solution[newr]][solution[newc]] == 0) {
continue;
}

component[newr][newc] = nComp;
queue[sizeBase] = (newr << 10) | (newc);
sizeBase++;
sumBase += original[solution[newr]][solution[newc]];
}
}
}

private int sum3;
private int size3;

private void calculateScoreForGreedyUpdateField(int minRange, int maxRange, int currentSum, int currentSize, int sign, int parentNComp) {
size3 = 0;
sum3 = 0;
nComp++;

if (sign < 0) {
{
int c = minRange;
for (int r = minRange + 1; r <= maxRange; r++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((c + 1 < S && (component[r][c + 1] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
{
int r = minRange;
for (int c = minRange; c <= maxRange; c++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((r + 1 < S && (component[r + 1][c] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
for (int ind = 0; ind < size3; ind++) {
int r = (queue[ind] >>> 10) & 1023;
int c = queue[ind] & 1023;
for (int d = 0; d < 4; d++) {
int newr = r + dr[d];
int newc = c + dc[d];

if (newr < minRange || newr > maxRange || newc < minRange || newc > maxRange) {
continue;
}
if (original[solution[newr]][solution[newc]] == 0 || component[newr][newc] == nComp || component[newr][newc] == parentNComp) {
continue;
}

component[newr][newc] = nComp;
queue[size3] = (newr << 10) | (newc);
sum3 += original[solution[newr]][solution[newc]];
size3++;
}
}
} else if (sign > 0) {
{
int c = maxRange;
for (int r = minRange; r <= maxRange - 1; r++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((c - 1 >= 0 && (component[r][c - 1] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
{
int r = maxRange;
for (int c = minRange; c <= maxRange; c++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((r - 1 >= 0 && (component[r - 1][c] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
for (int ind = 0; ind < size3; ind++) {
int r = (queue[ind] >>> 10) & 1023;
int c = queue[ind] & 1023;
for (int d = 0; d < 4; d++) {
int newr = r + dr[d];
int newc = c + dc[d];

if (newr < minRange || newr > maxRange || newc < minRange || newc > maxRange) {
continue;
}
if (original[solution[newr]][solution[newc]] == 0 || component[newr][newc] == nComp || component[newr][newc] == parentNComp) {
continue;
}

component[newr][newc] = nComp;
queue[size3] = (newr << 10) | (newc);
sum3 += original[solution[newr]][solution[newc]];
size3++;
}
}
} else {
if (original[solution[S / 2]][solution[S / 2]] != 0) {
component[S / 2][S / 2] = nComp;
sum3 += original[solution[S / 2]][solution[S / 2]];
size3++;
}
}
sum3 += currentSum;
size3 += currentSize;
}

private void loadBest() {
score = bestScore;
for (int i = 0; i < solution.length; i++) {
solution[i] = bestSolution[i];
}
}

private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < solution.length; i++) {
bestSolution[i] = solution[i];
}
}
}

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

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

ConnectedComponent cc = new ConnectedComponent();
int[] ret = cc.permute(matrix);

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 SAState {

public static final boolean useTime = true;

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

public double startTemperature = 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 ? ConnectedComponent.watch.getSecond() : loop;
}

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

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore < 0;
assert temperature >= 0;
return ConnectedComponent.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 State implements Comparable<State> {
State parent;
int j;
double score;
long hash;

@Override
public int compareTo(State o) {
if (score > o.score) {
return -1;
}
if (score < o.score) {
return 1;
}
if (hash < o.hash) {
return -1;
}
if (hash > o.hash) {
return 1;
}
return 0;
}

@Override
public String toString() {
return Utils.toString("j", j, "score", score);
}
}

class CollectionsUtils {
private CollectionsUtils() {
}

public static final <T> void shuffle(ArrayList<T> list, Random rng) {
for (int i = list.size() - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
CollectionsUtils.swap(list, i, j);
}
}

public static final <T> void shuffle(ArrayList<T> list, XorShift rng) {
for (int i = list.size() - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
CollectionsUtils.swap(list, i, j);
}
}

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

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

public static final <T extends Comparable<T>> void select0(ArrayList<T> a, int l, int r, int k) {
while (l < r) {
int i = CollectionsUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

public static final <T extends Comparable<T>> void select(ArrayList<T> a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final <T> void swap(ArrayList<T> a, int i, int j) {
T swap = a.set(i, a.get(j));
a.set(j, swap);
}

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

public static final <T extends Comparable<T>> void sort3(ArrayList<T> a, int i, int j, int k) {
if (a.get(i).compareTo(a.get(j)) > 0) {
swap(a, i, j);
}
if (a.get(i).compareTo(a.get(k)) > 0) {
swap(a, i, k);
}
if (a.get(j).compareTo(a.get(k)) > 0) {
swap(a, j, k);
}
}

public static final <T> int partition3(ArrayList<T> a, int l, int r, Comparator<T> comparator) {
int center = (l + r) >>> 1;
sort3(a, l, center, r, comparator);
swap(a, center, r - 1);
if (r - l < 3) {
return l;
}
int r1 = r - 1;
T v = a.get(r1);
int i = l - 1;
int j = r1;
for (;;) {
for (; comparator.compare(a.get(++i), v) < 0;) {
}
for (; comparator.compare(a.get(--j), v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final <T extends Comparable<T>> int partition3(ArrayList<T> a, int l, int r) {
int center = (l + r) >>> 1;
sort3(a, l, center, r);
swap(a, center, r - 1);
if (r - l < 3) {
return l;
}
int r1 = r - 1;
T v = a.get(r1);
int i = l - 1;
int j = r1;
for (;;) {
for (; a.get(++i).compareTo(v) < 0;) {
}
for (; a.get(--j).compareTo(v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final <T extends Comparable<T>> int partition(ArrayList<T> a, int l, int r) {
int i = l - 1, j = r;
T v = a.get(r);
for (;;) {
while (a.get(++i).compareTo(v) < 0)
;
while (v.compareTo(a.get(--j)) < 0)
if (j == l)
break;
if (i >= j)
break;
swap(a, i, j);
}
swap(a, i, r);
return i;
}

public static final <T> void sort(ArrayList<T> a, int lInclusive, int rInclusive, Comparator<T> comparator) {
if (lInclusive >= rInclusive) {
return;
}
int k = partition3(a, lInclusive, rInclusive, comparator);
sort(a, lInclusive, k - 1, comparator);
sort(a, k + 1, rInclusive, comparator);
}

public static final <T extends Comparable<T>> void sort(ArrayList<T> a, int lInclusive, int rInclusive) {
if (lInclusive >= rInclusive) {
return;
}
int k = partition3(a, lInclusive, rInclusive);
sort(a, lInclusive, k - 1);
sort(a, k + 1, rInclusive);
}

public static final <T> ArrayList<T> reverse(ArrayList<T> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

public static final <T> ArrayList<T> newReverse(ArrayList<T> list) {
ArrayList<T> res = new ArrayList<>();
for (int i = list.size() - 1; i >= 0; i--) {
res.add(list.get(i));
}
return res;
}

}


source code (左上から右下)


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

public class ConnectedComponent {
private static final int[] dr = { 0, 1, 0, -1, };
private static final int[] dc = { -1, 0, 1, 0, };

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

private SAState sa = new SAState();

private int S;
private int[][] original;

private double score;
private double bestScore;
private int[] solution;
private int[] bestSolution;

public int[] permute(int[] matrix) {
init(matrix);

solve();

Utils.debug("time", watch.getSecond(), "score", score, "countSets", countSets);

return solution;
}

private void init(int[] matrix) {
S = (int) Math.sqrt(matrix.length);

original = new int[S][S];
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
original[r][c] = matrix[r * S + c];
}
}

int numElements = 0;
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
if (original[r][c] != 0) {
numElements++;
}
}
}

component = new int[S][S];

moveHistory = new int[S];

hashHistory = new long[S];

Utils.debug("S", S, "numElements", numElements, String.format("%.1f%%", 100.0 * numElements / (S * S)));
}

private void solve() {
solution = new int[S];
for (int i = 0; i < solution.length; i++) {
solution[i] = i;
}

sa.startTemperature = 1.0 / S;

{
int maxBeamWidth = (int) (50.0 + (10000.0 - 50.0) * (500.0 - S) / (500.0 - 50.0));
ArrayList<State> moves = beamsearch(S, maxBeamWidth);
assert turn == 0;

if (moves == null) {
Utils.debug("moves == null");
}
for (State state : moves) {
next(state.j);
}

sa.startTemperature = 1e-3;
}

score = calculateScoreFromCenter();

bestSolution = Arrays.copyOf(solution, solution.length);
bestScore = score;

Utils.debug();
Utils.debug("score", score);
Utils.debug();

SA();
}

private int[] is;
private int[] minRanges;
private int[] maxRanges;
private int countSets = 0;

private ArrayList<State> beamsearch(int maxDepth, int maxBeamWidth) {
{
is = new int[S];
minRanges = new int[S];
maxRanges = new int[S];

int minRange = S - 1;
int maxRange = 0;
// for (int isi = 0, i = S / 2, delta = 0; i >= 0 && i < S; delta = (1 + Math.abs(delta)) * (Integer.signum(delta) >= 0 ? -1 : 1), i += delta) {
for (int isi = 0, i = 0; i < S; i += 1) {
is[isi] = i;
minRange = Math.min(minRange, i);
maxRange = Math.max(maxRange, i);
minRanges[isi] = minRange;
maxRanges[isi] = maxRange;
isi++;
}
}

int mask = (1 << (int) (Math.sqrt(500 / S))) - 1;

ArrayList<State> currents = new ArrayList<>();
ArrayList<State> nexts = new ArrayList<>();
State best = null;
currents.add(null);

double startTime = watch.getSecond();
double endTime = 9.5;

double sum = (1.0 + 1.0) * (maxDepth) / 2.0;

double[] timelimits = new double[maxDepth];
for (int i = 0; i < maxDepth; i++) {
if (i == 0) {
timelimits[i] = (endTime - startTime) * (1.0 + (1.0 - 1.0) * (i - 0.0) / (maxDepth - 1 - 0.0)) / sum;
} else {
timelimits[i] = timelimits[i - 1] + (endTime - startTime) * (1.0 + (1.0 - 1.0) * (i - 0.0) / (maxDepth - 1 - 0.0)) / sum;
}
}

for (int depth = 0; depth < maxDepth; depth++) {
if (currents.size() == 0) {
break;
}

int beamWidth = Math.min(maxBeamWidth, currents.size());

CollectionsUtils.select(currents, 0, currents.size(), beamWidth);
CollectionsUtils.sort(currents, 0, beamWidth - 1);

for (int beam = 0; beam < beamWidth; beam++) {
State currentState = currents.get(beam);

if (currentState == null) {
} else {
if (best == null || currentState.compareTo(best) < 0) {
best = currentState;
}
}

if (depth == maxDepth - 1) {
break;
}

set(reverse(toList(currentState)), 0);
countSets++;

int currentSum = 0;
int currentSize = 0;
if (depth > 0) {
calculateScoreFromCenterUsingField2(minRanges[depth - 1], maxRanges[depth - 1]);
currentSum = sumBase;
currentSize = sizeBase;
} else {
}

int bestNComp = nComp;

int i = is[depth];
for (int j = 0; j < S; j++) {
if (j >= minRanges[depth] && j <= maxRanges[depth]) {
if (j == i) {
} else {
continue;
}
}

next(j);

calculateScoreForGreedyUpdateField(minRanges[depth], maxRanges[depth], currentSum, currentSize, depth == 0 ? 0 : (is[depth] - is[depth - 1]), bestNComp);
double score = (sum3 * Math.sqrt(size3));

State next = new State();
next.parent = currentState;
next.j = j;
next.score = score;
next.hash = hash;
nexts.add(next);

previous();
}
if ((beam & mask) == 0) {
if (watch.getSecond() >= timelimits[depth]) {
break;
}
}
}
{
ArrayList<State> swap = currents;
currents = nexts;
nexts = swap;
}
nexts.clear();
}

for (; turn > 0;) {
previous();
}

if (best == null) {
return null;
}

return reverse(toList(best));
}

private ArrayList<State> reverse(ArrayList<State> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

private ArrayList<State> toList(State state2) {
ArrayList<State> res = new ArrayList<>();
for (State current = state2; current != null; current = current.parent) {
res.add(current);
}
return res;
}

private int[] moveHistory;
private int turn = 0;
private long[] hashHistory;
private long hash;

private void next(int j) {
moveHistory[turn] = j;
hashHistory[turn] = hash;

swap(is[turn], j);

hash = hash * 503 + j;

turn++;
}

private void previous() {
turn--;
swap(is[turn], moveHistory[turn]);
hash = hashHistory[turn];
}

private void set(ArrayList<State> list, int startIndex) {
int startIndexMinus1 = startIndex - 1;
for (int i = 0; i < list.size() && startIndex + i < moveHistory.length; i++) {
int j = moveHistory[startIndex + i];
State state = list.get(i);
if (state.j == j) {
startIndexMinus1 = startIndex + i;
continue;
}
break;
}

for (; turn > startIndexMinus1 + 1;) {
previous();
}
for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
State state2 = list.get(i);
next(state2.j);
}
}

private void SA() {
double second = 1;
int mask = (1 << 5) - 1;

sa.startTime = watch.getSecond();
sa.endTime = 9.5;

for (sa.loop = 0;; sa.loop++) {

if ((sa.loop & mask) == 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("%.4f", bestScore), String.format("%.6f", sa.temperature));
break;
}

sa.updateTemperature();
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("%.4f", bestScore), String.format("%.6f", sa.temperature));
}
}

swap();

}
}

private void swap() {
int i = (int) (S * rng.nextDouble());
int j = (int) ((S - 1) * rng.nextDouble());
if (j >= i) {
j++;
}

assert j != i;

swap(i, j);

double newScore = calculateScoreFromCenter();

sa.countChange++;
if (newScore >= score || sa.accept(newScore, score)) {
sa.countAccept++;

score = newScore;

saveBest();

} else {
swap(i, j);
}
}

private void swap(int i, int j) {
int swap = solution[i];
solution[i] = solution[j];
solution[j] = swap;
}

private int[][] component;
private static final int[] queue = new int[500 * 500];
private int nComp = 0;

private double calculateScoreFromCenter() {
int currentNumComponents = nComp;
double maxSum = -1e9;
for (int i = 1 - 1; i <= 1 + 1; i++) {
for (int j = 1 - 1; j <= 1 + 1; j++) {
if (original[solution[i]][solution[j]] == 0)
continue;
if (component[i][j] > currentNumComponents)
continue;

int size = 0;
double sum = 0;
nComp++;

component[i][j] = nComp;
queue[size] = (i << 10) | (j);
size++;
sum += original[solution[i]][solution[j]];

for (int ind = 0; ind < size; ind++) {
for (int d = 0; d < 4; d++) {
int newr = ((queue[ind] >>> 10) & 1023) + dr[d];
int newc = (queue[ind] & 1023) + dc[d];
if (newr < 0 || newc < 0 || newr >= S || newc >= S)
continue;
if (component[newr][newc] > currentNumComponents || original[solution[newr]][solution[newc]] == 0) {
continue;
}
component[newr][newc] = nComp;
queue[size] = (newr << 10) | (newc);
size++;
sum += original[solution[newr]][solution[newc]];
}
}
sum *= Math.sqrt(size);
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}

private int sumBase;
private int sizeBase;

private void calculateScoreFromCenterUsingField2(int minRange, int maxRange) {

int currentNumComponents = nComp;
int i = 0;
int j = 0;

sizeBase = 0;
sumBase = 0;
nComp++;

if (original[solution[i]][solution[j]] == 0) {
return;
}

component[i][j] = nComp;
queue[sizeBase] = (i << 10) | (j);
sizeBase++;
sumBase += original[solution[i]][solution[j]];

for (int ind = 0; ind < sizeBase; ind++) {
int r = (queue[ind] >>> 10) & 1023;
int c = queue[ind] & 1023;
for (int d = 0; d < 4; d++) {
int newr = r + dr[d];
if (newr < minRange || newr > maxRange) {
continue;
}
int newc = c + dc[d];
if (newc < minRange || newc > maxRange) {
continue;
}
if (component[newr][newc] > currentNumComponents || original[solution[newr]][solution[newc]] == 0) {
continue;
}

component[newr][newc] = nComp;
queue[sizeBase] = (newr << 10) | (newc);
sizeBase++;
sumBase += original[solution[newr]][solution[newc]];
}
}
}

private int sum3;
private int size3;

private void calculateScoreForGreedyUpdateField(int minRange, int maxRange, int currentSum, int currentSize, int sign, int parentNComp) {
size3 = 0;
sum3 = 0;
nComp++;

if (sign < 0) {
{
int c = minRange;
for (int r = minRange + 1; r <= maxRange; r++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((c + 1 < S && (component[r][c + 1] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
{
int r = minRange;
for (int c = minRange; c <= maxRange; c++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((r + 1 < S && (component[r + 1][c] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
for (int ind = 0; ind < size3; ind++) {
int r = (queue[ind] >>> 10) & 1023;
int c = queue[ind] & 1023;
for (int d = 0; d < 4; d++) {
int newr = r + dr[d];
int newc = c + dc[d];

if (newr < minRange || newr > maxRange || newc < minRange || newc > maxRange) {
continue;
}
if (original[solution[newr]][solution[newc]] == 0 || component[newr][newc] == nComp || component[newr][newc] == parentNComp) {
continue;
}

component[newr][newc] = nComp;
queue[size3] = (newr << 10) | (newc);
sum3 += original[solution[newr]][solution[newc]];
size3++;
}
}
} else if (sign > 0) {
{
int c = maxRange;
for (int r = minRange; r <= maxRange - 1; r++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((c - 1 >= 0 && (component[r][c - 1] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
{
int r = maxRange;
for (int c = minRange; c <= maxRange; c++) {
if (original[solution[r]][solution[c]] == 0) {
continue;
}
if ((r - 1 >= 0 && (component[r - 1][c] == parentNComp))) {
component[r][c] = nComp;

queue[size3] = (r << 10) | (c);
sum3 += original[solution[r]][solution[c]];
size3++;
}
}
}
for (int ind = 0; ind < size3; ind++) {
int r = (queue[ind] >>> 10) & 1023;
int c = queue[ind] & 1023;
for (int d = 0; d < 4; d++) {
int newr = r + dr[d];
int newc = c + dc[d];

if (newr < minRange || newr > maxRange || newc < minRange || newc > maxRange) {
continue;
}
if (original[solution[newr]][solution[newc]] == 0 || component[newr][newc] == nComp || component[newr][newc] == parentNComp) {
continue;
}

component[newr][newc] = nComp;
queue[size3] = (newr << 10) | (newc);
sum3 += original[solution[newr]][solution[newc]];
size3++;
}
}
} else {
if (original[solution[0]][solution[0]] != 0) {
component[0][0] = nComp;
sum3 += original[solution[0]][solution[0]];
size3++;
}
}
sum3 += currentSum;
size3 += currentSize;
}

private void loadBest() {
score = bestScore;
for (int i = 0; i < solution.length; i++) {
solution[i] = bestSolution[i];
}
}

private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int i = 0; i < solution.length; i++) {
bestSolution[i] = solution[i];
}
}
}

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

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

ConnectedComponent cc = new ConnectedComponent();
int[] ret = cc.permute(matrix);

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 SAState {

public static final boolean useTime = true;

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

public double startTemperature = 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 ? ConnectedComponent.watch.getSecond() : loop;
}

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

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore < 0;
assert temperature >= 0;
return ConnectedComponent.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 State implements Comparable<State> {
State parent;
int j;
double score;
long hash;

@Override
public int compareTo(State o) {
if (score > o.score) {
return -1;
}
if (score < o.score) {
return 1;
}
if (hash < o.hash) {
return -1;
}
if (hash > o.hash) {
return 1;
}
return 0;
}

@Override
public String toString() {
return Utils.toString("j", j, "score", score);
}
}

class CollectionsUtils {
private CollectionsUtils() {
}

public static final <T> void shuffle(ArrayList<T> list, Random rng) {
for (int i = list.size() - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
CollectionsUtils.swap(list, i, j);
}
}

public static final <T> void shuffle(ArrayList<T> list, XorShift rng) {
for (int i = list.size() - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
CollectionsUtils.swap(list, i, j);
}
}

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

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

public static final <T extends Comparable<T>> void select0(ArrayList<T> a, int l, int r, int k) {
while (l < r) {
int i = CollectionsUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

public static final <T extends Comparable<T>> void select(ArrayList<T> a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final <T> void swap(ArrayList<T> a, int i, int j) {
T swap = a.set(i, a.get(j));
a.set(j, swap);
}

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

public static final <T extends Comparable<T>> void sort3(ArrayList<T> a, int i, int j, int k) {
if (a.get(i).compareTo(a.get(j)) > 0) {
swap(a, i, j);
}
if (a.get(i).compareTo(a.get(k)) > 0) {
swap(a, i, k);
}
if (a.get(j).compareTo(a.get(k)) > 0) {
swap(a, j, k);
}
}

public static final <T> int partition3(ArrayList<T> a, int l, int r, Comparator<T> comparator) {
int center = (l + r) >>> 1;
sort3(a, l, center, r, comparator);
swap(a, center, r - 1);
if (r - l < 3) {
return l;
}
int r1 = r - 1;
T v = a.get(r1);
int i = l - 1;
int j = r1;
for (;;) {
for (; comparator.compare(a.get(++i), v) < 0;) {
}
for (; comparator.compare(a.get(--j), v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final <T extends Comparable<T>> int partition3(ArrayList<T> a, int l, int r) {
int center = (l + r) >>> 1;
sort3(a, l, center, r);
swap(a, center, r - 1);
if (r - l < 3) {
return l;
}
int r1 = r - 1;
T v = a.get(r1);
int i = l - 1;
int j = r1;
for (;;) {
for (; a.get(++i).compareTo(v) < 0;) {
}
for (; a.get(--j).compareTo(v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final <T extends Comparable<T>> int partition(ArrayList<T> a, int l, int r) {
int i = l - 1, j = r;
T v = a.get(r);
for (;;) {
while (a.get(++i).compareTo(v) < 0)
;
while (v.compareTo(a.get(--j)) < 0)
if (j == l)
break;
if (i >= j)
break;
swap(a, i, j);
}
swap(a, i, r);
return i;
}

public static final <T> void sort(ArrayList<T> a, int lInclusive, int rInclusive, Comparator<T> comparator) {
if (lInclusive >= rInclusive) {
return;
}
int k = partition3(a, lInclusive, rInclusive, comparator);
sort(a, lInclusive, k - 1, comparator);
sort(a, k + 1, rInclusive, comparator);
}

public static final <T extends Comparable<T>> void sort(ArrayList<T> a, int lInclusive, int rInclusive) {
if (lInclusive >= rInclusive) {
return;
}
int k = partition3(a, lInclusive, rInclusive);
sort(a, lInclusive, k - 1);
sort(a, k + 1, rInclusive);
}

public static final <T> ArrayList<T> reverse(ArrayList<T> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

public static final <T> ArrayList<T> newReverse(ArrayList<T> list) {
ArrayList<T> res = new ArrayList<>();
for (int i = list.size() - 1; i >= 0; i--) {
res.add(list.get(i));
}
return res;
}

}





Approach

684468.79 RandomForest
689847.94 RandomForest + medianfilter +-1
693728.97 RandomForest + medianfilter +-5

RandomForest は 1 image あたり 15625 samples,
feature は +-delta(=4, 8) の正方形の色の{平均、歪度,尖度} * 正方形の中心{ (r,c), (r-delta,c-delta), (r-delta,c+delta), (r+delta,c-delta), (r+delta,c+delta)} * 4色{gray, red, green, blue}。


chainerは、 VOC2012 で練習中で間に合わなかった。



ダメだったアプローチ


 * 事前計算されたDP
  
各試験紙に同じ数のボトルを割り当てると仮定して、
   DP[毒の数][試験紙の数][残りラウンド数] = 期待値が最大になるようなボトルの割合。
   TLE。

 * 各試験紙に同じ数のボトルを割り当てると仮定して、SA, 深さ制限dfs with 黄金分割探索。


使ったアプローチ


 * 試験紙が毒の数より圧倒的に多いとき、
   二分探索のようにして、毒の範囲をしぼる。

 * 試験紙>=毒の数のとき、
   試験紙の補集合も一枚の試験紙のように使える。
   残りのラウンドを見て、試験紙にボトルを等分する。

 * その他
   毎ラウンド、シミュレーションして (再利用できる試験紙の数 ^ 残りラウンド数) * ボトルの数 が最大になるように、試験紙にボトルを割り当てる。




source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Objects;
import java.util.TimeZone;

public class PoisonedWine {
private static final int unknown = 0;
private static final int good = -1;
private static final int bad = -2;

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

private int numBottles;
private int numRounds;
private int numPoisonedBottles;
private int numPapers;

private int numGoods;
private int numBads;
private int availablePapers;
private int[] states;

public int[] testWine(int numBottles, int numPapers, int numRounds, int numPoisonedBottles) {
CalendarUtils.printDate(Constants.currentTime, Constants.endTime);

if (numPoisonedBottles > numPapers + 5) {
return new PoisonedWineSubmission3().testWine(numBottles, numPapers, numRounds, numPoisonedBottles);
}

init(numBottles, numPapers, numRounds, numPoisonedBottles);

solve();

int[] makeSolution = makeSolution(states);

Utils.debug("time", watch.getSecondString(), "score", calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods);
return makeSolution;
}

private int nextRestartRound = 0;

private void solve() {
Bottles unknownBottles = restart(numBottles, numPoisonedBottles, states);

Utils.debug("round", "numBottles", "score", "numGoods", "Papers", "size", "prob", "ev");

for (int round = 0; round < numRounds; round++) {

if (availablePapers == 0) {
break;
}
ArrayList<Group> groups = makeGroup(unknownBottles, round);

test(groups);

update(groups);

{
ArrayList<Integer> sizes = new ArrayList<>();
for (Group group : groups) {
sizes.add(group.bottles.get(0).indexes2.size());
}

if (!sizes.isEmpty()) {
Utils.debug(round, unknownBottles.indexes2.size(), (int) calculateScore(numBottles, numPoisonedBottles, numGoods), numGoods, availablePapers, sizes);
} else {
Utils.debug(round, unknownBottles.indexes2.size(), (int) calculateScore(numBottles, numPoisonedBottles, numGoods), numGoods, availablePapers);
}
}

if (groups.size() == 1) {
unknownBottles.indexes2 = groups.get(0).complement.indexes2;
unknownBottles.infBads = groups.get(0).complement.supBads;
unknownBottles.supBads = groups.get(0).complement.supBads;

if (unknownBottles.isAllGood()) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
} else if (round + 1 == nextRestartRound) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
} else {
}
} else {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
}
}

}

private void update(ArrayList<Group> groups) {
for (Group group : groups) {
for (Bottles bottles : group.bottles) {
if (bottles.isAllGood()) {
updateStateGood(bottles.indexes2);
}
if (bottles.isAllBad()) {
updateStateBad(bottles.indexes2);
}
updateExpectedProbability(bottles.indexes2, (double) bottles.infBads / bottles.indexes2.size());
}
{
if (group.complement.isAllGood()) {
updateStateGood(group.complement.indexes2);
}
if (group.complement.isAllBad()) {
updateStateBad(group.complement.indexes2);
}
updateExpectedProbability(group.complement.indexes2, (double) group.complement.supBads / group.complement.indexes2.size());
}
}
}

private Bottles restart(int numBottles, int numPoisonedBottles, int[] states) {
Bottles bottles = new Bottles();

for (int i = 0; i < numBottles; i++) {
if (states[i] == bad) {
} else if (states[i] == good) {
} else {
bottles.indexes2.add(i);
}
}

bottles.infBads = numPoisonedBottles;
bottles.supBads = numPoisonedBottles;

updateExpectedProbability(bottles.indexes2, (double) bottles.supBads / bottles.indexes2.size());

ArrayList<Pair<Double, Integer>> countAndIndexPairs = new ArrayList<>();
for (int i = 0; i < bottles.indexes2.size(); i++) {
int index = bottles.indexes2.get(i).intValue();
countAndIndexPairs.add(new Pair<Double, Integer>(maxExpectedProbability[index] + 1e-6 * rng.nextDouble(), index));
}
Collections.sort(countAndIndexPairs);

bottles.indexes2.clear();
for (int i = 0; i < countAndIndexPairs.size(); i++) {
bottles.indexes2.add(countAndIndexPairs.get(i).second.intValue());
}

numBottlesAtRestart = bottles.indexes2.size();

double paperPerPoison = (double) numPapers / numPoisonedBottles;
int restartRounds = (int) Math.ceil(numRounds / paperPerPoison);
nextRestartRound += restartRounds;

Utils.debug("restart", "unknowns.size()", bottles.indexes2.size(), "numPoisonedBottles - numBads", numPoisonedBottles + " - " + numBads + " = " + (numPoisonedBottles - numBads));

return bottles;
}

private int numBottlesAtRestart;
private double[] maxExpectedProbability;
private double[] minExpectedProbability;

private void updateExpectedProbability(ArrayList<Integer> indexes, double p) {
for (Integer index : indexes) {
maxExpectedProbability[index.intValue()] = Math.max(maxExpectedProbability[index.intValue()], p);
minExpectedProbability[index.intValue()] = Math.min(maxExpectedProbability[index.intValue()], p);
}
}

private void updateStateBad(ArrayList<Integer> indexes) {
for (Integer index : indexes) {
if (states[index.intValue()] == unknown) {
states[index.intValue()] = bad;
numBads++;
}
}
}

private void updateStateGood(ArrayList<Integer> indexes2) {
for (Integer index : indexes2) {
if (states[index.intValue()] == unknown) {
states[index.intValue()] = good;
numGoods++;
}
}
}

private void test(ArrayList<Group> groups) {
ArrayList<Bottles> bottles = new ArrayList<>();
ArrayList<Group> groups2 = new ArrayList<>();
for (Group group : groups) {
for (int j = 0; j < group.bottles.size(); j++) {
if (group.bottles.get(j).indexes2.size() == 0) {
continue;
}

bottles.add(group.bottles.get(j));
groups2.add(group);
}
}

boolean[] isPoisoned = useTestStrips(bottles);
assert isPoisoned.length == bottles.size();

for (int i = 0; i < isPoisoned.length; i++) {
if (isPoisoned[i]) {
bottles.get(i).supBads = groups2.get(i).supBads;
bottles.get(i).infBads = 1;

groups2.get(i).complement.supBads--;
groups2.get(i).complement.infBads = 0;
availablePapers--;
} else {
bottles.get(i).supBads = 0;
bottles.get(i).infBads = 0;
}
}

for (Group group : groups) {
int sumInfBads = 0;
for (Bottles bottles2 : group.bottles) {
sumInfBads += bottles2.infBads;
}
for (Bottles bottles2 : group.bottles) {
bottles2.supBads = Math.min(bottles2.supBads, group.supBads - (sumInfBads - bottles2.infBads));
}
}

}

private ArrayList<Group> makeGroup(Bottles bottles0, int round) {
if (bottles0.isAllGood() || bottles0.isAllBad()) {
return new ArrayList<>();
}

ArrayList<Group> groups2 = new ArrayList<>();

int numGroups = availablePapers / (2 * bottles0.supBads - 1);
numGroups /= numRounds - round;
if (numGroups == 0) {
numGroups = 1;
}

for (int i = 0; i < numGroups; i++) {
groups2.add(new Group(bottles0.infBads, bottles0.supBads));
}

int[] groupPapers = new int[numGroups];
for (int paper = 0; paper < availablePapers; paper++) {
groupPapers[paper % groups2.size()]++;
}

for (int i = 0; i < numGroups; i++) {
Group group = groups2.get(i);

Result bestResult = new Result();
double paperPerPoison = (double) numPapers / numPoisonedBottles;
int restartRounds = (int) Math.ceil(numRounds / paperPerPoison);
double eachRoundBottles = (double) numBottlesAtRestart / restartRounds;
int complement = (round + 1 == nextRestartRound) ? 1 : 0;
double size = eachRoundBottles / (groupPapers[i] + complement);

bestResult.bestSize = (int) Math.round(size);
if (bestResult.bestSize == 0) {
bestResult.bestSize = 1;
}

for (int paper = 0; paper < groupPapers[i]; paper++) {
group.bottles.add(new Bottles());
}

for (int sizeIndex = 0; sizeIndex < bottles0.indexes2.size(); sizeIndex++) {
int toIndex = sizeIndex;
for (int j = 0; j < i; j++) {
toIndex /= (group.bottles.size() + 1);
}
toIndex = toIndex % (group.bottles.size() + 1);
int value = bottles0.indexes2.get(sizeIndex).intValue();

if (toIndex >= 0 && toIndex < group.bottles.size() && group.bottles.get(toIndex).indexes2.size() < bestResult.bestSize) {
group.bottles.get(toIndex).indexes2.add(value);
} else {
group.complement.indexes2.add(value);
}
}

}
return groups2;
}

private void init(int numBottles, int numPapers, int numRounds, int numPoisonedBottles) {
Utils.debug("numBottles", numBottles, "numPapers", numPapers, "numRounds", numRounds, "numPoisonedBottles", numPoisonedBottles);

this.numBottles = numBottles;
this.numPapers = numPapers;
this.numRounds = numRounds;
this.numPoisonedBottles = numPoisonedBottles;

this.states = new int[numBottles];
Arrays.fill(states, unknown);
this.maxExpectedProbability = new double[numBottles];
Arrays.fill(maxExpectedProbability, 0);
this.minExpectedProbability = new double[numBottles];
Arrays.fill(minExpectedProbability, 1);

this.numGoods = 0;
this.numBads = 0;

this.availablePapers = numPapers;
}

private double calculateScore(int numBottles, int numPoisonedBottles, int numGoods) {
double d = (double) numGoods / (numBottles - numPoisonedBottles);
double score = 1e6 * d * d;
return score;
}

private int[] makeSolution(int[] states) {
ArrayList<Integer> unknownAndBad = new ArrayList<>();
for (int i = 0; i < states.length; i++) {
if (states[i] != good) {
unknownAndBad.add(i);
}
}
int[] ret = new int[unknownAndBad.size()];
for (int i = 0; i < unknownAndBad.size(); i++) {
ret[i] = unknownAndBad.get(i).intValue();
}
return ret;
}

private boolean[] useTestStrips(ArrayList<Bottles> bottles) {
String[] tests = new String[bottles.size()];
for (int i = 0; i < bottles.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < bottles.get(i).indexes2.size(); j++) {
if (j > 0) {
sb.append(",");
}
sb.append(bottles.get(i).indexes2.get(j));
}
tests[i] = sb.toString();
}

int[] testResults = PoisonTest.useTestStrips(tests);

boolean[] isPoisoned = new boolean[testResults.length];
for (int i = 0; i < isPoisoned.length; i++) {
isPoisoned[i] = testResults[i] == 1;
}
return isPoisoned;
}

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

int numBottles = BR.readInt();
int testPapers = BR.readInt();
int testRounds = BR.readInt();
int numPoison = BR.readInt();

PoisonedWine pw = new PoisonedWine();
int[] ret = pw.testWine(numBottles, testPapers, testRounds, numPoison);

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 Group {
ArrayList<Bottles> bottles;
Bottles complement;
int supBads;
int infBads;

public Group(int infBads, int supBads) {
bottles = new ArrayList<>();

this.supBads = supBads;
this.infBads = infBads;

complement = new Bottles();
complement.infBads = infBads;
complement.supBads = supBads;
}
}

class Bottles {
public boolean isComplement;
ArrayList<Integer> indexes2;
int supBads;
int infBads;

public Bottles() {
indexes2 = new ArrayList<>();
}

public boolean isAllGood() {
return supBads == 0;
}

public boolean isAllBad() {
return infBads >= indexes2.size();
}

@Override
public String toString() {
return Utils.toString("isComplement", isComplement, "supBads", supBads, "infBads", infBads, "size", indexes2.size());
}

}

class ArrayListInt {
private static final int DEFAULT_CAPACITY = 10;

private static final int[] EMPTY_ELEMENTDATA = {};

private static final int[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient int[] elementData;

private int size;

public ArrayListInt(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new int[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}

public ArrayListInt() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayListInt(ArrayListInt c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
elementData = Arrays.copyOf(elementData, size);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}

public void trimToSize() {
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}

public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public boolean contains(int o) {
return indexOf(o) >= 0;
}

public int indexOf(int o) {
for (int i = 0; i < size; i++)
if (o == elementData[i])
return i;
return -1;
}

public int lastIndexOf(int o) {
for (int i = size - 1; i >= 0; i--)
if (o == elementData[i])
return i;
return -1;
}

public Object clone() {
try {
ArrayListInt v = (ArrayListInt) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}

public int[] toArray() {
return Arrays.copyOf(elementData, size);
}

int elementData(int index) {
return elementData[index];
}

public int get(int index) {
rangeCheck(index);

return elementData(index);
}

public int set(int index, int element) {
rangeCheck(index);

int oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

public boolean add(int e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

public void add(int index, int element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}

public int removeByIndex(int index) {
rangeCheck(index);
int oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = 0;
return oldValue;
}

public boolean remove(int o) {
for (int index = 0; index < size; index++)
if (o == elementData[index]) {
fastRemove(index);
return true;
}
return false;
}

private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = 0;
}

public void clear() {
for (int i = 0; i < size; i++)
elementData[i] = 0;

size = 0;
}

public boolean addAll(ArrayListInt c) {
int[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

public boolean addAll(int index, ArrayListInt c) {
rangeCheckForAdd(index);

int[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

protected void removeRange(int fromIndex, int toIndex) {
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = 0;
}
size = newSize;
}

private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}

public boolean removeAll(ArrayListInt c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}

public boolean retainAll(ArrayListInt c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}

private boolean batchRemove(ArrayListInt c, boolean complement) {
final int[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
if (r != size) {
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = 0;
size = w;
modified = true;
}
}
return modified;
}
}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
System.err.flush();
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

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

}

final class Constants {
public static final boolean TIMER = true;
public static final boolean LOCAL = true;
public static final boolean DEBUG = true;
public static final boolean ASSERTION = true;

private static final String id = "GMT-4:00";
public static final Calendar currentTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
}

public static final Calendar startTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
startTime.set(2017, 7 - 1, 5, 21, 0, 0);
}

public static final Calendar endTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
endTime.set(2017, 7 - 1, 19, 21, 0, 0);
}

private Constants() {
}
}

class Result {
int bestSize;
double bestExpectedValue;
}

class CalendarUtils {
private CalendarUtils() {
}

public static final void printDate(Calendar currentTime, Calendar endTime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;

long end = endTime.getTimeInMillis();

long current = currentTime.getTimeInMillis();

long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);

int year = currentTime.get(Calendar.YEAR);
int month = 1 + currentTime.get(Calendar.MONTH);
int day = currentTime.get(Calendar.DAY_OF_MONTH);
int hour = currentTime.get(Calendar.HOUR_OF_DAY);
int minute = currentTime.get(Calendar.MINUTE);
int second = currentTime.get(Calendar.SECOND);

Utils.debug(String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes));
}

public static final String toStringDateAndTimeLeft(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes);
}

public static final String toStringDate(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("%02d/%02d/%02d %02d:%02d:%02d", year, month, day, hour, minute, second);
}

public static final String toStringTimeLeft(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("Time Left %d Hrs %d Mins", numHours, numMinutes);
}

}

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 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 PoisonedWineSubmission3 {
private static final int unknown = 0;
private static final int good = -1;
private static final int bad = -2;

private XorShift rng = new XorShift(System.nanoTime());

public int[] testWine(int numBottles, int numStrips, int numRounds, int numPoisonedBottles) {
Utils.debug("numBottles", numBottles, "numStrips", numStrips, "numRounds", numRounds, "numPoisonedBottles", numPoisonedBottles);

int[] states = new int[numBottles];
Arrays.fill(states, unknown);

int numGoods = 0;
int numBads = 0;

int availableStrips = numStrips;
ArrayListInt all = new ArrayListInt();
for (int i = 0; i < numBottles; i++) {
all.add(i);
}
int[] array = all.toArray();
shuffle(array, rng);
BottlesSubmission3 unknownBottles = new BottlesSubmission3(array, numPoisonedBottles, false);
for (int round = 0; round < numRounds; round++) {

if (availableStrips == 0) {
break;
}

if (unknownBottles.indexes.length == 0) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
}

if (unknownBottles.isAllBad() || unknownBottles.isAllGood()) {
if (unknownBottles.isAllGood()) {
for (int index : unknownBottles.indexes) {
states[index] = good;
numGoods++;
}
}
unknownBottles = restart(numBottles, numPoisonedBottles, states);
if (unknownBottles.isAllBad() || unknownBottles.isAllGood()) {
break;
}
}
boolean[] simpleModel = getSimpleModel(unknownBottles.indexes.length, unknownBottles.numBads);

int maxBatchSize = (int) (Math.ceil((double) unknownBottles.indexes.length / (availableStrips)));

double bestBatchSize2 = -1;
double bestNumGoods = -1;

for (int batchSize = 1; batchSize <= maxBatchSize; batchSize++) {

int nextStrips = 0;
for (int strip = 0; strip < availableStrips; strip++) {
if (isGood(simpleModel, batchSize, strip)) {
nextStrips++;
}
}

if (Math.pow(nextStrips, numRounds - round) * batchSize > bestNumGoods) {
bestNumGoods = Math.pow(nextStrips, numRounds - round) * batchSize;
bestBatchSize2 = batchSize;
}

}
int bestBatchSize = (int) bestBatchSize2;
LinkedList<Integer> availableIndexes = new LinkedList<>();
for (int index : unknownBottles.indexes) {
availableIndexes.addLast(index);
}

ArrayList<BottlesSubmission3> bottleSets = new ArrayList<>();
for (int stripIndex = 0; stripIndex < availableStrips; stripIndex++) {
ArrayListInt indexes2 = new ArrayListInt();
for (int i = 0; i < bestBatchSize; i++) {
if (availableIndexes.size() > 0) {
indexes2.add(availableIndexes.pollFirst().intValue());
}
}

if (indexes2.size() > 0) {
bottleSets.add(new BottlesSubmission3(indexes2.toArray(), 0, true));
}
}

boolean[] isPoisoned = test((BottlesSubmission3[]) bottleSets.toArray(new BottlesSubmission3[bottleSets.size()]));
int nextBads = unknownBottles.numBads;

assert isPoisoned.length == bottleSets.size();

for (int i = 0; i < isPoisoned.length; i++) {
if (isPoisoned[i]) {
bottleSets.get(i).numBads = 1;
nextBads--;

if (bottleSets.get(i).indexes.length == 1) {
for (int index : bottleSets.get(i).indexes) {
states[index] = bad;
numBads++;
}
} else {
}
availableStrips--;
} else {
for (int index : bottleSets.get(i).indexes) {
states[index] = good;
numGoods++;
}
}
}
int[] toArray = new int[availableIndexes.size()];
for (int i = 0; i < toArray.length; i++) {
toArray[i] = availableIndexes.pollFirst().intValue();
}
unknownBottles = new BottlesSubmission3(toArray, nextBads, false);

Utils.debug("round", round, "score", (int) calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods, "Strips", availableStrips, "size", bestBatchSize);
}
int[] makeSolution = makeSolution(states);
Utils.debug("time", PoisonedWine.watch.getSecondString(), "score", calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods);

return makeSolution;

}

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

private boolean[] getSimpleModel(int numBottles, int numPoisonedBottles) {
boolean[] simpleModel = new boolean[numBottles];
{
double badProbability = (double) numPoisonedBottles / numBottles;
double sumBadProbability = 1e-9;
for (int i = 0; i < simpleModel.length; i++) {
sumBadProbability += badProbability;
if (sumBadProbability >= 1) {
sumBadProbability -= 1;
simpleModel[i] = true;
}
}

int count = 0;
for (int i = 0; i < simpleModel.length; i++) {
if (simpleModel[i]) {
count++;
}
}
assert count == numPoisonedBottles : Utils.toString(count, numPoisonedBottles, numBottles);
}
return simpleModel;
}

private boolean isGood(boolean[] simpleModel, int batchSize, int strip) {
for (int i = 0; i < batchSize; i++) {
if (strip * batchSize + i < simpleModel.length && simpleModel[strip * batchSize + i]) {
return false;
}
}
return true;
}

private double calculateScore(int numBottles, int numPoisonedBottles, int numGoods) {
double d = (double) numGoods / (numBottles - numPoisonedBottles);
double score = 1e6 * d * d;
return score;
}

private BottlesSubmission3 restart(int numBottles, int numPoisonedBottles, int[] states) {
int numBads = 0;
ArrayListInt unknowns = new ArrayListInt();
for (int i = 0; i < numBottles; i++) {
if (states[i] == bad) {
numBads++;
} else if (states[i] == good) {
} else {
unknowns.add(i);
}
}
Utils.debug("restart", "unknowns.size()", unknowns.size(), "numPoisonedBottles - numBads", numPoisonedBottles + " - " + numBads + " = " + (numPoisonedBottles - numBads));
int[] array = unknowns.toArray();
shuffle(array, rng);
return new BottlesSubmission3(array, numPoisonedBottles - numBads, false);
}

private int[] makeSolution(int[] states) {
ArrayList<Integer> unknownAndBad = new ArrayList<>();
for (int i = 0; i < states.length; i++) {
if (states[i] != good) {
unknownAndBad.add(i);
}
}
int[] ret = new int[unknownAndBad.size()];
for (int i = 0; i < unknownAndBad.size(); i++) {
ret[i] = unknownAndBad.get(i).intValue();
}
return ret;
}

private boolean[] test(BottlesSubmission3[] bottleSets) {
String[] tests = new String[bottleSets.length];
for (int i = 0; i < bottleSets.length; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < bottleSets[i].indexes.length; j++) {
if (j > 0) {
sb.append(",");
}
sb.append(bottleSets[i].indexes[j]);
}
tests[i] = sb.toString();
}
int[] testRes = PoisonTest.useTestStrips(tests);
boolean[] isPoisoned = new boolean[testRes.length];
for (int i = 0; i < isPoisoned.length; i++) {
isPoisoned[i] = testRes[i] == 1;
}
return isPoisoned;
}
}

class BottlesSubmission3 {
int[] indexes;
int numBads;

public BottlesSubmission3(int[] indexes, int numBads, boolean isChecked) {
super();
this.indexes = indexes;
this.numBads = numBads;
}

public boolean isAllGood() {
return numBads <= 0;
}

public boolean isAllBad() {
return numBads >= indexes.length;
}

public double getGoodProbability() {
return 1 - getBadProbability();
}

public double getBadProbability() {
return (double) numBads / indexes.length;
}

}

このページのトップヘ