Qualification Round 1 Saturday, August 18, 2007 Match summaryIn Qualification Round 1 of the 2007 TCCC, 1023 competitors were presented with a wellbalanced problemset. All the problems were quite solvable; by the end of the coding phase almost everybody submitted the easy, more than half of competitors managed to submit the medium, and there were as many as 204 submits on the hard. During the challenge phase there were 118 successful challenges, mostly on the medium problem. After the system tests were over, myprasanna placed first with fast solutions on all three problems and 2 successful challenges. Newcomer isd was about 90 points behind and took second place, with daveagp in third. The cutoff to advance was 247.28 points, so a fast solution on the easy was enough to move forward. Congratulations to all 550 coders who managed to advance to Online Round 1, and good luck to all other coders in the next Qualification Rounds! The ProblemsMovieRatingUsed as: Division One  Level One:
The solution for this problem is very straightforward. As the rating calculation algorithm is completely described in the problem statement, we just need to implement it. The correct Java code follows: public double calculate(int[] marks, int lowCount, int highCount) { // sort all individual ratings in nondecreasing order Arrays.sort(marks); // find the sum of all remaining individual ratings int sum = 0; for (int i=lowCount; i+highCount<marks.length; i++) sum += marks[i]; // divide the sum on the amount of ratings to obtain the average return sum / (double)(marks.lengthlowCounthighCount); }OptimalGroupMovement Used as: Division One  Level Two:
The first observation needed to solve the problem is that it's always better to move groups separately than it is to first merge some groups into a larger one then move them all together. This fact immediately follows from the inequality (X + Y)^{2} ≥ X^{2} + Y^{2}. The second observation is that if we fix the final state of the board, then it's always possible to move the groups to their final positions in such a way that two groups are never merged together into a large group unless they both will reach their final positions immediately after the move. To achieve this, we can first move those groups, which are to the left of their final positions, in righttoleft order, and then move the groups that are to the right of their final positions in lefttoright order. These two observations give us the solution. We iterate through every possible final state of the board. For every state, we calculate how many moves need to be made for every group in order to achieve this state and what the total cost of all those moves is. The answer is the minimum total cost of moves among all possible final states. Commented Java code follows: public int minimumCost(String board) { int N = board.length(), grCnt = 0, tot = 0; // find all groups on the board int[] grSt = new int[N], grFn = new int[N]; for (int i=0; i < N; i++) if (board.charAt(i) == 'X' && (i == 0  board.charAt(i1) == '.')) { grSt[grCnt] = i; grFn[grCnt] = i; while (grFn[grCnt] + 1 < N && board.charAt(grFn[grCnt]+1) == 'X') grFn[grCnt]++; tot += grFn[grCnt]  grSt[grCnt] + 1; grCnt++; } int best = 1000000000; // iterate through all possible start positions of the final group // and find the minimum among total costs of moves needed to reach // each final state of the board for (int st=0; st + tot <= N; st++) { int cost = 0, cur = st; for (int i=0; i < grCnt; i++) { int grSize = grFn[i]  grSt[i] + 1; cost += Math.abs(cur  grSt[i]) * grSize * grSize; cur += grFn[i]  grSt[i] + 1; } best = Math.min(best, cost); } return best; }ConstructionFromMatches Used as: Division One  Level Three:
This problem can be solved using dynamic programming. Let F(i, j, k) be the minimum cost of 2xi rectangle, which:
Let's find the recurrence for F(i, j, k). We consider all matches in the ith column of the rectangle and denote their lengths by letters a, b, c, d, e, as shown in the picture below: c   ...          ... a j     d    ...          ... b k     e    ...  Let's iterate through the possible values of a, b and c. Using equalities a + c + d + j = top[i1] and b + d + e + k = bottom[i1], we can find the values d and e, namely d = top[i1]  a  c  j and e = bottom[i1]  b  d  k. If d or e doesn't correspond to correct match thickness, then the current triple a, b, c won't give as any solutions and we need to continue with the next triple. Otherwise, we can find the minimum cost of 2xi rectangles for the current triple a, b, c. Obviously, the minimum cost of its first i1 columns is F(i1, a, b) and the cost of additional matches in ith column is cost[c1] + cost[d1] + cost[e1] + cost[j1] + cost[k1]. Altogether, the cost of all 2xi rectangle is F(i1, a, b) + cost[c1] + cost[d1] + cost[e1] + cost[j1] + cost[k1] and the minimum of this expression over all triples a, b, c will give us the value of F(i, j, k). Now, as we have the recurrence for F(i, j, k), we can start from F(0, j, k) = cost[j1] + cost[k1] and consequently find all values of F. Minimum of F(N, j, k) over all match thicknesses j and k will give us the answer for the problem (here N is the number of columns in the required rectangle). Java implementation of the described algorithm follows: public class ConstructionFromMatches { public int minimumCost(int[] cost, int[] top, int[] bottom) { int N = top.length, M = cost.length; int[][][] F = new int[N+1][M+1][M+1]; // initialization for (int j=1; j <= M; j++) for (int k=1; k <= M; k++) F[0][j][k] = cost[j1] + cost[k1]; // general recurrence for (int i=1; i <= N; i++) for (int j=1; j <= M; j++) for (int k=1; k <= M; k++) { F[i][j][k] = 1000000000; for (int a=1; a <= M; a++) for (int b=1; b <= M; b++) for (int c=1; c <= M; c++) { int d = top[i1]  a  c  j; int e = bottom[i1]  b  d  k; if (d < 1  d > M) continue; if (e < 1  e > M) continue; F[i][j][k] = Math.min(F[i][j][k], F[i1][a][b] + cost[c1] + cost[d1] + cost[e1] + cost[j1] + cost[k1]); } } // answer calculation int res = 1000000000; for (int j=1; j <= M; j++) for (int k=1; k <= M; k++) res = Math.min(res, F[N][j][k]); return (res == 1000000000 ? 1 : res); } } Note that this algorithm has complexity O(M^{5} * N), where M is the amount of different match thicknesses and N is the number of columns in the resulted rectangle. There is also an improvement of this solution, which lowers complexity to O(M^{4} * N). We leave the pleasure of finding this improvement to the readers. 
