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!↵
↵
[PROBLEM & DATA ](https://acmicpc.unisa.edu.au/index.php/regional-contest-current/56-regional-contests/2017-regional-contests/153-2017-problem-sets) ↵
↵
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] + " ");↵
↵
}↵
↵
}↵
↵
↵
~~~~~↵
[MY CODE](https://pastebin.com/sGmsCwQD)↵
↵
[PROBLEM & DATA ](https://acmicpc.unisa.edu.au/index.php/regional-contest-current/56-regional-contests/2017-regional-contests/153-2017-problem-sets) ↵
↵
↵
~~~~~↵
↵
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] + " ");↵
↵
}↵
↵
}↵
↵
↵
~~~~~↵
