August 25, 2018 2018 TCO Algorithm Wildcard Round Editorials

TCO18 Algorithm Wildcard Round was held on August 25 at 12:00 UTC -4. Top two from this round will qualify to compete in TCO18 Finals to be held in Dallas, Texas!. Hope you enjoyed the problems!

Easy – CubesOnATable

Three cubes have 18 faces. We can make at most 7 of those invisible (by placing all three cubes on the table and making two pairs of cubes touch), hence three cubes will always have at least 11 visible faces. Thus, if surface <= 10, we can only use one or two cubes.
With one cube the only possible surface is 5. With two cubes the possible surfaces are 8 (next to each other), 9 (on top of each other), and 10 (both on the table without touching).
Thus, for surface in {1,2,3,4,6,7} there is no solution.
Note that we already know how to construct configurations with surface 8, 9, 10, and 11. If you have a configuration with surface x, you can construct a configuration with surface x+4k by placing a vertical stack of k cubes on top of one of its cubes. This solves all the remaining cases.

public class CubesOnATable {
    void add(ArrayList answer, int x, int y, int z) { answer.add(x); answer.add(y); answer.add(z); }
    public int[] placeCubes(int surface) {
        // general solution
        if (surface < 8 && surface != 5) return new int[0];
        ArrayList answer = new ArrayList();
        if (surface % 4 == 0) { add(answer,1,0,0); }
        if (surface % 4 == 1) {}
        if (surface % 4 == 2) { add(answer,2,0,0); }
        if (surface % 4 == 3) { add(answer,1,0,0); add(answer,2,0,0); }
        int cubes = (surface+1) / 4 - answer.size() / 3;
        for (int i=0; i<cubes; ++i) add(answer,0,0,i);
        int[] primitive = new int[ answer.size() ];
        for (int i=0; i<primitive.length; ++i) primitive[i] = answer.get(i);
        return primitive;
    }
};

Medium – Gangsters

There are P gangsters standing in a circle, numbered from 0 to P-1; each gangster is aiming at the next gangster in a circle. We need to calculate the number of permutations of shooting which results in leaving exactly A gangsters alive.
No matter which gangster starts shooting, the situation will be perfectly symmetric. Thus let’s assume that gangster number P-2 shoot first, and at the end we will multiply obtained answer by P.
Next we see, that since gangster P-2 shot gangster P-1, the latter will no longer be able to shoot, no matter where he is in the permutation. Thus we can forget about him, and at the end multiply the answer by P-1, since there are P-1 places for him in the permutation.
Therefore we have reduced the problem on a circle to a problem on a line, in which we have P-2 gangsters who didn’t shoot followed by one gangster who already shot. The first gangster will stay alive for sure.
Now we are ready to use dynamic programming. Let D[N,K] denotes the number of permutations for line situation with N gangsters who didn’t shoot (followed by a gangster who shot) which results that at the end exactly K gangsters stay alive. For N=0 we have only one gangster (which obviously stays alive), and for N=1 we have that gangster 0 must shoot gangster 1 (and 0 stays alive).
Thus D[N,K] = [K=1] for N <= 1. Let N >= 2 and 0 <= i < N be the number of gangster which shoots next. If i=N-1 then he just shoot gangster N and we are left with a line one gangster shorter.
For i < N-1 we get two independent line situations with i gangsters and N-i-2 gangsters respectively. Gangster i is the first in the permutation and he shoot gangster i-1, so gangster i-1 can be in any of N-1 positions (we multiply the answer by N-1). We have to consider all partitions of K over these situations.
Moreover, we can arbitrarily shuffle permutations resulted from these two situations, so there are binom(N-2,i) ways to distribute i values from the first permutation into resulting permutation of size N-2. Thus we get the following recurrence formula:

The final answer is P * (P-1) * D[P-2,A]. Time complexity of the algorithm is O(P^2 * A^2). Note that we can decrease the constant by observing that D[N,K]=0 for K > N/2 (no two consecutive gangsters can stay alive).

public class Gangsters {
public int countOrderings(int people, int alive) {
  int MOD = 1000_000_007;
  int[][] binom = new int[people+1][people+1];
  int[][] dp = new int[people+1][people+1];
  for (int n = 0; n <= people; ++n) {
    binom[n][0] = binom[n][n] = 1;
    for (int k = 1; k < n; ++k) {
      binom[n][k] = (binom[n-1][k-1] + binom[n-1][k]) % MOD;
    }
  }
  dp[0][1] = 1;
  dp[1][1] = 1;
  for (int n = 2; n <= people; ++n) {
    for (int k = 1; k <= people/2; ++k) {
      long cnt = dp[n-1][k];
      for (int i = 0; i < n-1; ++i) {
        long part = 0;
        for (int j = 0; j <= k; ++j) {
          part += (long)dp[i][j] * dp[n-i-2][k-j] % MOD;
        }
        cnt += part % MOD * binom[n-2][i] % MOD * (n-1);
      }
      dp[n][k] = (int)(cnt % MOD);
    }
  }
  return (int)((long)people * (people-1) % MOD * dp[people-2][alive] % MOD);
}
};

Hard – CommonPalindromicSubsequences

We are given two strings A and B of lengths N and M respectively. We need to find the number of strings S such that S is a subsequence of both A and B and S is a palindrome.
Once again, we will use dynamic programming. Denote by dp[la,ra,lb,rb] the number of different common palindromic subsequences (including empty subsequence) of substrings A[la .. ra-1] and B[lb .. rb-1].
Let’s consider subsequences which start and end in a fixed letter c. There is at least one such subsequence only if firstA[la,c] <= lastA[ra,c] and firstB[lb,c] <= lastB, where firstA[i,c] denotes the position of the first character c in A[i .. N-1] and lastA[i,c] denotes the position of the last character c in A[0 .. i-1] (similarly for firstB and lastB). Note that we can easily compute arrays firstA, lastA, firstB and lastB in time O((N+M)*C) where C is the size of the alphabet.
Moreover, if at least one of the above inequalities is indeed an equality, then the only subsequence which starts and ends in letter c is the one-letter string c. Otherwise, we can append letter c to any common palindromic subsequence of substrings A[firstA[la,c]+1 .. lastA[ra,c]-1] and B[firstB[lb,c]+1 .. lastB-1] and there are exactly dp[firstA[la,c]+1, lastA[ra,c], firstB[lb,c]+1, lastB] of them.
Thus the time complexity of the algorithm is O(N^2 * M^2 * C).
As an interesting fact we show a different dynamic programming recurrence, which doesn’t depend on the size of the alphabet.
Let’s calculate dp[la,ra,lb,rb] and assume that ra-la >=2 and rb-lb >=2 (other cases are simple). If all border letters are equal (that is c = A[la] = A[ra-1] = B[lb] = B[rb-1]), then we have D = dp[la+1,ra-1,lb+1,rb-1] palindromic subsequences of As = A[la+1 .. ra-2] and Bs = B[lb+1 .. rb-2] which can be extended by adding c on both sides. So it seems that taking dp[la,ra,lb,rb] = 2*D would be a good idea, but unfortunately such formula would count some subsequences twice, namely those which can be extended by letters c which are located inside As and Bs. Thus if we have at least two letters c in both As and Bs, we must subtract dp[firstA[la+1,c]+1, lastA[ra-1,c], firstB[lb+1,c]+1, lastB[rb-1,c]]. Finally, there is one more special case: if As does not contain c or Bs does not contain c, then one-letter subsequence c will not be counted in D, but should be counted in dp[la,ra,lb,rb].
If border letters are not equal, we know that some of them will not be part of a subsequence, so we can use inclusion-exclusion principle. Abusing notation slightly let’s call these letters la, ra, lb and rb. We iterate over all non-empty subsets Z of border letters and remove the letters in the subset, thus we calculate:
dp[la,ra,lb,rb] = \sum_{Z} (-1)^{|Z|+1} dp[la + [la in Z], ra – [ra in Z], lb + [lb in Z], rb – ].
Time complexity of this recurrence is O(N^2 * M^2 * 2^4).

public class CommonPalindromicSubsequences {
public long count(String A, String B) {
  int n = A.length(), m = B.length(), ALPH = 26;
  int[] a = new int[n];
  int[] b = new int[m];
  int[] pos_a = new int[ALPH];
  int[] pos_b = new int[ALPH];
  int[] next_a = new int[n];
  int[] prev_a = new int[n];
  int[] next_b = new int[m];
  int[] prev_b = new int[m];
  for (int i = 0; i < ALPH; ++i) {
    pos_a[i] = pos_b[i] = -1;
  }
  for (int i = 0; i < n; ++i) {
    a[i] = A.charAt(i) - 'a';
    prev_a[i] = pos_a[a[i]];
    pos_a[a[i]] = i;
  }
  for (int i = 0; i < m; ++i) {
    b[i] = B.charAt(i) - 'a';
    prev_b[i] = pos_b[b[i]];
    pos_b[b[i]] = i;
  }
  for (int i = 0; i < ALPH; ++i) { pos_a[i] = n; pos_b[i] = m; } for (int i = n-1; i >= 0; --i) {
    next_a[i] = pos_a[a[i]];
    pos_a[a[i]] = i;
  }
  for (int i = m-1; i >= 0; --i) {
    next_b[i] = pos_b[b[i]];
    pos_b[b[i]] = i;
  }
  int BITS = 4;
  int[] sign = new int[1<<BITS];
  int[][] bits = new int[1<<BITS][BITS];
  sign[0] = -1;
  for (int mask = 1; mask < (1<<BITS); ++mask) { sign[mask] = (mask & 1) == 0 ? sign[mask>>1] : -sign[mask>>1];
    for (int i = 0; i < BITS; ++i) {
      bits[mask][i] = (mask & (1<<i)) >> i;
    }
  }
  long[][][][] dp = new long[n+1][n+1][m+1][m+1];
  for (int lena = 0; lena <= n; ++lena) {
    for (int lenb = 0; lenb <= m; ++lenb) {
      for (int la = 0; la + lena <= n; ++la) {
        for (int lb = 0; lb + lenb <= m; ++lb) {
          int ra = la + lena, rb = lb + lenb;
          if (la == ra || lb == rb) {
            dp[la][ra][lb] = 1;
          } else if (la+1 == ra) {
            dp[la][ra][lb] = a[la] == b[lb] ? 2 : dp[la][ra][lb+1];
          } else if (lb+1 == rb) {
            dp[la][ra][lb] = a[la] == b[lb] ? 2 : dp[la+1][ra][lb];
          } else {
            int c = a[la];
            if (c == a[ra-1] && c == b[lb] && c == b[rb-1]) {
              long inside = next_a[la] < prev_a[ra-1] && next_b[lb] < prev_b[rb-1] ?
                dp[next_a[la]+1][prev_a[ra-1]][next_b[lb]+1][prev_b[rb-1]] : 0;
              long single = next_a[la] == ra-1 || next_b[lb] == rb-1 ? 1 : 0;
              dp[la][ra][lb] = 2*dp[la+1][ra-1][lb+1][rb-1] - inside + single;
            } else {
              long cnt = 0;
              for (int mask = 1; mask < (1<<BITS); ++mask) {
                cnt += sign[mask] * dp[la+bits[mask][0]][ra-bits[mask][1]][lb+bits[mask][2]][rb-bits[mask][3]];
              }
              dp[la][ra][lb] = cnt;
            }
          }
        }
      }
    }
  }
  return dp[0][n][0][m] - 1;
}
};