Algorithm Round 1C Saturday, September 1, 2007 Match summaryOnline Round 1C of the 2007 TopCoder Collegiate Challenge was a bit better attended than Rounds 1A and 1B, with 514 participants. The problem set was somewhat different from the previous two rounds as well, with the first two problems easier and the last problem harder. As a result, the cutoff was quite high  306.61 points  so correct solutions on both easy and medium were needed to advance. The top spots were taken by the 11 coders who correctly solved the hard problem. Among them was ACRush in first place, Per in second, and pparys in third. The ProblemsDifDifUsed as: Division One  Level One:
The most straightforward solution of this problem is to brute force all possible next values of the sequence and see which one will produce 0 in the last difference sequence. The tricky part of such a solution is to set correct limits on the answer. Example 3 shows that the answer can be as large as 1,023,000. It's also not hard to see, that the answer can be as small as 1,023,000 (it's enough to negate all numbers in example 3 to obtain the test with such an answer). So we can make a guess that it will be enough to brute force the answer from 1,023,000 to 1,023,000, inclusive. Now it's possible to implement a working solution using this guess. The Java code below works for 0.870 seconds in the worst case: public int predict(int[] seq) { int N = seq.length; int[] A = new int[N+1]; // brute force next value for (int x = 1023000; x <= 1023000; x++) { // append next value to the end of the sequence for (int i=0; i < N; i++) A[i] = seq[i]; A[N] = x; // calculate the bottom difference sequence for (int i=0; i < N; i++) for (int j=0; j < Ni; j++) A[j] = A[j+1]  A[j]; // if it consists of 0, then we found the answer if (A[0] == 0) return x; } return 1; } Of course, this solution is far from safe, because we just made a guess and didn't find any proof of it. In order to obtain safer and faster solution, let's do some simple math. If we take the sequence (5, 4, 12, 23) from the problem statement, append unknown number x to its end and generate all difference sequences, we'll get the following triangle: 5 4 12 23 x 9 16 11 x23 25 5 x2311 30 x2311(5) x2311(5)(30) We see that, in order to calculate the value in the bottom difference sequence, we need to subsequently subtract from x numbers 23, 11, 5 and 30, i.e. the rightmost numbers from the rows of the original triangle. As we wish the bottom value to be 0, we need to set x as the sum of all subtracted numbers. So we can just generate the original triangle and sum the rightmost numbers from all its rows to get the answer. The implementation of this approach is pretty short: public int predict(int[] seq) { int res=0, N = seq.length; for (int i=0; i < N; i++) { res += seq[Ni1]; for (int j=0; j < Ni1; j++) seq[j] = seq[j+1]  seq[j]; } return res; }Prefixes Used as: Division One  Level Two:
As the algorithm for producing the desired partition is described in the problem statement, we just need to implement it. The constraints are quite low, so the implementation can be completely straightforward. One iteration of the algorithm's cycle can be implemented as follows. In order to find the longest prefix that appears in at least 2 unassigned strings, we simply iterate through all prefixes of all unassigned strings. For every prefix we iterate through all unassigned strings and check in how many of them it appears. From those prefixes that appear in 2 or more strings we choose the longest one. If there are many longest prefixes, we prefer the lexicographically first among them, as we need to list the groups with the samelength common prefix alphabetically. After the prefix is chosen, we form the group of all unassigned strings with this prefix, listed alphabetically, make all these strings assigned and proceed with the next iteration of the algorithm. Commented Java code follows: public String[] prefixList(String[] protein) { // add all strings to a list and sort it alphabetically ListCircleCount Used as: Division One  Level Three:
I'll describe the solution of this problem in three steps. Step 1  Getting rid of cyclicity. As cars are on the circular track, we always have two possible directions to move a car to its destination  clockwise and counterclockwise. If the track was straight, we would always have one direction instead of two. Let's try to make track straight in order to simplify the problem. To do this, we iterate through all possible cars and assume for each car that it will be moved earlier than all other cars to its unloading position. If there's no way to move the car in any of 2 directions, we simply skip it, otherwise we move the car to its unloading position and consider the situation after this. As the car is already moved, it won't be moved anymore, so it will always block one of 2 possible movement directions for all other cars. It means, that we can "cut" the track at the unloading position of the car and treat it as straight after this. The example below illustrates this idea: e A E B e A E b a D a D G b > G B > D F d f c g C G a e A E C F C F g c f d g c f d initial track car b was moved equivalent straight track Step 2  Investigating configurations without solution. Now, given a configuration on the straight track, let's investigate when it won't have any solution. We define car interval as the interval of the track between the start and finish positions of the car. Suppose that one car interval completely lies inside the other car interval, like in the example below: . . a . . B . . b . . A . . ** ** It's obvious in this case, that car b will always block the path for car a, so configurations with one car interval inside another are always not solvable. Let's call two car intervals badly overlapped it they have points in common, are not one inside another, and one interval starts from a lowercase letter and another starts from an uppercase letter. Two possible cases of bad overlap are illustrated below: . . a . . B . . A . . b . . . . A . . b . . a . . B . . ** ** ** ** In the first case if we first move car a, it will then block the path for car b, and vice versa, if we first move car b, it will block the path for car a. In the second case cars a and b initially block the paths for each other. We see that configurations with bad overlap are also now always not solvable. Now let's prove that if the configuration doesn't contain two intervals, one of which is inside another, and doesn't contain bad overlaps, than it is solvable. We consider the graph with the set of vertices consisting of all cars. Two vertices are connected by an edge, if the corresponding car intervals have common points. Let's call every connected component of this graph a group. For example, the configuration "ABaCbcdeDfEF" has two groups  one of cars a, b, c and another of cars d, e, f. By definition, two car intervals from different groups don't have common points, so each group occupies a separate part of the track. If we sort the intervals within one group in increasing order of their start positions, the finished positions of the intervals will also be sorted in increasing order (as no interval lies inside another). Taking the absence of bad overlaps into account, we see that every group has the following (unique) solution:
So, the configuration is solvable if and only if it doesn't contain two intervals, one of which is inside another, and doesn't contain bad overlaps. Now let's count the number of solutions. Step 3  A bit of combinatorics. Let the configuration consists of k groups, numbered from 1 to k, and ith group contains L_{i} cars. The solution for each group is unique, but for all configuration there can be many possible solutions, as moves for different groups can be mixed together in any possible order. So every solution can be described by the sequence of L_{1} + L_{2} + ... + L_{k} numbers from 1 to k, where each number i indicates one move for ith group. The valid sequences are exactly those which contain L_{i} entries of number i for every i from 1 to k, inclusive. This looks like some well known combinatorial object, so let's check the latest tutorial about the basics of combinatorics. Here (in the section on "permutations with repetition") we will see that the number of different solutions is described by the formula (L_{1} + L_{2} + ... + L_{k})! / (L_{1}! * L_{2}! * ... * L_{k}!). Commented Java implementation of the solution follows: public final long INF = 10000000000l; // this class represents one car interval class Interval { char lC, rC; int l, r; public Interval(int l, char lC, int r, char rC) { this.l = l; this.lC = lC; this.r = r; this.rC = rC; } } // number of solutions for the straight track public long cnt(String S) { // find all intervals Interval[] ints = new Interval[S.length()]; int intCnt = 0; for (int i=0; i < S.length(); i++) for (int j=i+1; j < S.length(); j++) if (Character.toUpperCase(S.charAt(i)) == Character.toUpperCase(S.charAt(j))) ints[intCnt++] = new Interval(i, S.charAt(i), j, S.charAt(j)); // try to find one interval inside another for (int i=0; i < intCnt; i++) for (int j=0; j < intCnt; j++) if (ints[i].l < ints[j].l && ints[j].r < ints[i].r) return 0; // try to find bad overlap for (int i=0; i < intCnt; i++) for (int j=0; j < intCnt; j++) if (Math.max(ints[i].l, ints[j].l) < Math.min(ints[i].r, ints[j].r) && Character.isLowerCase(ints[i].lC) != Character.isLowerCase(ints[j].lC)) return 0; // construct graph and its transitive closure boolean[][] adj = new boolean[intCnt][intCnt]; for (int i=0; i < intCnt; i++) adj[i][i] = true; for (int i=0; i < intCnt; i++) for (int j=0; j < intCnt; j++) if (Math.max(ints[i].l, ints[j].l) < Math.min(ints[i].r, ints[j].r)) adj[i][j] = true; for (int k=0; k < intCnt; k++) for (int i=0; i < intCnt; i++) for (int j=0; j < intCnt; j++) if (adj[i][k] && adj[k][j]) adj[i][j] = true; // find groups boolean[] used = new boolean[intCnt]; int[] L = new int[S.length()]; int cnt = 0; for (int i=0; i < intCnt; i++) { if (used[i]) continue; for (int j=0; j < intCnt; j++) if (adj[i][j]) { L[cnt]++; used[j] = true; } cnt++; } // find count of solutions long res = 1, X = 0; for (int i=0; i < cnt; i++) for (int j=0; j < L[i]; j++) { res *= (++X); res /= (j + 1); if (res >= INF) return INF; } return res; } public int countOrder(String c) { long res = 0; // iterate through the first car to move for (int i=0; i < c.length(); i++) for (int j=i+1; j < c.length(); j++) if (Character.toUpperCase(c.charAt(i)) == Character.toUpperCase(c.charAt(j))) { // check, whether car can be moved boolean ok1 = true, ok2 = true; for (int k=i+1; k < j; k++) if (Character.isLowerCase(c.charAt(k))) ok1 = false; for (int k=0; k < i; k++) if (Character.isLowerCase(c.charAt(k))) ok2 = false; for (int k=j+1; k < c.length(); k++) if (Character.isLowerCase(c.charAt(k))) ok2 = false; // if car can be moved, than solve the problem on the straight track if (ok1  ok2) { String S = (Character.isLowerCase(c.charAt(i)) ? c.substring(j+1) + c.substring(0, i) + c.substring(i+1, j) : c.substring(i+1, j) + c.substring(j+1) + c.substring(0, i)); res += cnt(S); if (res >= INF) return 1; } } return (res > 2000000000 ? 1 : (int)res); } 
