public long minTime(int[] tubes, int[] coins) { long[][] dist = new long[1 + coins.length + tubes.length][1 + coins.length + tubes.length]; int start = coins.length + tubes.length; int[] pos = new int[1 + coins.length + tubes.length]; System.arraycopy(coins, 0, pos, 0, coins.length); System.arraycopy(tubes, 0, pos, coins.length, tubes.length); for (int i = 0; i < pos.length; ++i) for (int j = 0; j < pos.length; ++j) dist[i][j] = Math.abs(pos[i] - pos[j]); for (int i = 0; i < tubes.length; ++i) { int a = i + coins.length; int b = (i ^ 1) + coins.length; dist[a][b] = Math.min(dist[a][b], 1); } for (int k = 0; k < pos.length; ++k) for (int i = 0; i < pos.length; ++i) for (int j = 0; j < pos.length; ++j) dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); Random random = new Random(HIDDEN_SEED); long best = Long.MAX_VALUE; int[] path = new int[coins.length + 1]; path[0] = start; for (int i = 1; i <= coins.length; ++i) path[i] = i - 1; for (int i = 1; i < coins.length; ++i) { int j = i + random.nextInt(coins.length - i + 1); int tmp = path[i]; path[i] = path[j]; path[j] = tmp; } long cur = 0; for (int i = 0; i + 1 < path.length; ++i) cur += dist[path[i]][path[i + 1]]; best = Math.min(best, cur); int[] is = new int[path.length * path.length]; int[] js = new int[path.length * path.length]; while (true) { boolean any = false; int cnt = 0; for (int i = 1; i < path.length; ++i) for (int j = i + 1; j < path.length; ++j) { is[cnt] = i; js[cnt] = j; ++cnt; } for (int i = 0; i < cnt; ++i) { int j = random.nextInt(cnt - i) + i; int t = is[i]; is[i] = is[j]; is[j] = t; t = js[i]; js[i] = js[j]; js[j] = t; } for (int ii = 0; ii < cnt; ++ii) { int i = is[ii]; int j = js[ii]; long delta = dist[path[i - 1]][path[j]] - dist[path[i - 1]][path[i]]; if (j + 1 < path.length) { delta += dist[path[i]][path[j + 1]] - dist[path[j]][path[j + 1]]; } if (delta < 0) { any = true; cur += delta; best = Math.min(best, cur); for (int ai = i, aj = j; ai < aj; ++ai, --aj) { int t = path[ai]; path[ai] = path[aj]; path[aj] = t; } } } if (!any) break; } return best; }