South Pacific Regional Finals 2017 Problem B: Banner Help

Revision en1, by sturdyplum, 2018-03-26 18:19:03

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

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] + " "); } }

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English sturdyplum 2018-03-26 18:21:31 6296
en1 English sturdyplum 2018-03-26 18:19:03 7071 Initial revision (published)