I've been working on this problem for a while but can't find an efficient solution. So far my solution runs in about 40 seconds worst case. However the time limit is only 6 seconds. There seems to be no editorial for this contest and it went unsolved during the contest. My solution is bellow. Basically I am doing a backtracking solution that has some amount of memoization, and uses Hungarian matching to do heavy pruning. I was wondering if anyone has solved this problem or could offer some insight to how to solve it. Thank you!
MY CODE :
import java.util.*;
public class b {
static int next[][] = new int[26][26];
static int tot[] = new int[27];
static int cost[][] = new int[26][26];
static int best[] = new int[1 << 26];
static int reMap[] = new int[26];
static int cheapest = Integer.MAX_VALUE;
static long count[] = new long[4];
static int idx = 0, components = 26;
static long factorials[][];
static final long mod[] = { (long) 1e9 + 7, (long) 1e9 + 9, (long) 1e9 + 21, (long) 1e9 + 33 };
static int done;
static HashMap<Long, Integer> states = new HashMap<>();
static class Hungarian {
static int inf = 100000000;
int[][] c;
int[] lx, ly, xy, yx, s, sx, p, q;
int n, m;
boolean[] S, T;
public Hungarian(int[][] cost) {
c = cost;
n = c.length;
m = c[0].length;
S = new boolean[n];
T = new boolean[m];
lx = new int[n];
ly = new int[m];
xy = new int[n];
yx = new int[m];
s = new int[m];
sx = new int[m];
p = new int[n];
q = new int[n];
}
void augment() {
int x, y, root = -1, wr = 0, rd = 0;
Arrays.fill(S, false);
Arrays.fill(T, false);
for (x = 0; x < n; x++) {
if (xy[x] == -1) {
q[wr++] = root = x;
p[x] = -2;
S[x] = true;
break;
}
}
for (y = 0; y < m; y++) {
s[y] = lx[root] + ly[y] - c[root][y];
sx[y] = root;
}
while (y >= m) {
while (rd < wr && y >= m) {
x = q[rd++];
for (y = 0; y < m; y++) {
if (c[x][y] == lx[x] + ly[y] && !T[y]) {
if (yx[y] == -1)
break;
T[y] = true;
q[wr++] = yx[y];
addToTree(yx[y], x);
}
}
}
if (y < m)
break;
updateLabels();
wr = rd = 0;
for (y = 0; y < m; y++) {
if (!T[y] && s[y] == 0) {
if (yx[y] == -1) {
x = sx[y];
break;
} else {
T[y] = true;
if (!S[yx[y]]) {
q[wr++] = yx[y];
addToTree(yx[y], sx[y]);
}
}
}
}
}
for (int cx = x, cy = y, ty; cx != -2; cx = p[cx], cy = ty) {
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
}
void updateLabels() {
int x, y, delta = inf;
for (y = 0; y < m; y++)
delta = Math.min(delta, !T[y] ? s[y] : inf);
for (x = 0; x < n; x++)
lx[x] -= S[x] ? delta : 0;
for (y = 0; y < m; y++) {
ly[y] += T[y] ? delta : 0;
s[y] -= !T[y] ? delta : 0;
}
}
void addToTree(int x, int prevX) {
S[x] = true;
p[x] = prevX;
for (int y = 0; y < m; y++) {
if (lx[x] + ly[y] - c[x][y] < s[y]) {
s[y] = lx[x] + ly[y] - c[x][y];
sx[y] = x;
}
}
}
int run() {
Arrays.fill(xy, -1);
Arrays.fill(yx, -1);
for (int x = 0; x < n; x++)
for (int y = 0; y < m; y++)
lx[x] = Math.max(lx[x], c[x][y]);
for (int i = 0; i < n; i++)
augment();
int ret = 0;
for (int x = 0; x < n; x++)
ret += c[x][xy[x]];
return ret;
}
}
static int bestCase(int bm) {
if (best[bm] != -1)
return best[bm];
int n = idx - Integer.bitCount(bm);
if (n < 1)
return 0;
int cost[][] = new int[n][n];
int rmap[] = new int[n];
int c = 0;
for (int i = 0; i < idx; i++) {
if ((bm & (1 << i)) == 0) {
rmap[c++] = i;
}
}
for (int i = 0; i < n; i++) {
int v = reMap[rmap[i]];
for (int j = 0; j < n; j++) {
int w = reMap[rmap[j]];
if (i == j)
cost[i][j] = -tot[v];
else
cost[i][j] = -(tot[v] - next[v][w]);
}
}
Hungarian h = new Hungarian(cost);
return best[bm] = -h.run();
}
static long getState(long bm, long last, long letter) {
return bm | (last << 30) | (letter << 40);
}
public static int go(int bm, int last, int cost, int letter) {
if (bm == done) {
cost += tot[last];
if (cheapest == cost) {
for (int i = 0; i < 4; i++) {
count[i] += factorials[i][components];
if (count[i] >= mod[i])
count[i] -= mod[i];
}
} else if (cheapest > cost) {
cheapest = cost;
for (int i = 0; i < 4; i++) {
count[i] = factorials[i][components];
}
}
return tot[last];
}
long st = getState(bm, last, letter);
Integer vals = states.get(st);
if (vals != null) {
if (vals + cost > cheapest) {
return vals;
}
}
int ans = 100;
int bc = 0;
if (vals == null) {
if (last != 26) {
bc = tot[last];
for (int i = 0; i < idx; i++) {
if ((bm & (1 << i)) == 0) {
int ri = reMap[i];
bc = Math.min(bc, tot[last] - next[last][ri]);
}
}
}
if (cost + bestCase(bm) + bc > cheapest)
return bestCase(bm) + bc;
}
if (last == 26) {
for (int i = 0; i < idx; i++) {
int ri = reMap[i];
if ((bm & (1 << i)) == 0) {
ans = Math.min(go(bm | (1 << i), ri, cost, ri + 1), ans);
}
}
return ans;
}
for (int i = 0; i < idx; i++) {
int ri = reMap[i];
if ((bm & (1 << i)) == 0) {
if (next[last][ri] != 0) {
components--;
ans = Math.min(ans, go(bm | (1 << i), ri, cost + (tot[last] - next[last][ri]), letter) + tot[last]- next[last][ri]);
components++;
} else if (next[last][ri] == 0 && ri >= letter) {
ans = Math.min(ans, go(bm | (1 << i), ri, cost + tot[last], ri + 1)+tot[last]);
}
}
}
states.put(st, ans);
return ans;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
Arrays.fill(best, -1);
for (int i = 0; i < s.length() - 1; i++) {
next[s.charAt(i) - 'A'][s.charAt(i + 1) - 'A']++;
tot[s.charAt(i) - 'A']++;
}
Arrays.fill(reMap, -1);
for (int i = 0; i < 26; i++) {
for (char c : s.toCharArray()) {
if (c == 'A' + i) {
reMap[idx++] = i;
break;
}
}
}
for (int i = 0; i < 26; i++)
next[i][i] = 0;
factorials = new long[4][30];
for (int j = 0; j < 4; j++) {
factorials[j][0] = 1l;
for (int i = 1; i < 30; i++) {
factorials[j][i] = factorials[j][i - 1] * i;
factorials[j][i] %= mod[j];
}
}
done = (1 << idx) - 1;
go(0, 26, 0, 0);
for (int j = 0; j < 4; j++)
System.out.print(count[j] + " ");
}
}
