Monday, April 3, 2006 Match summary This was one of the last SRMs before the ACMICPC World finals in San Antonio. Petr, who earned 2 gold medals in his two ACM finals, added another SRM win to his perfect record. krijgerje was second, almost 400 points from Petr, while bmerry, misof and xOberon rounded out the top five. In Division 2, firsttimer tuan won a really tough race against otoc (1948 points against 1940), followed by Gevor, ikabiljo and cypressx. All these coders will compete in Div 1 next time. The ProblemsEratosthenSieve2Used as: Division Two  Level One:
Choosing the proper data structure is the key for this problem. The problem asks you to take a ordered list of numbers, remove a number of elements from the middle of this list, and return the kth element in the resulting list. All these operations are supported by LinkedList (java, std::list for C++): public class EratosthenSieve2 { public int nthElement(int n) { ListDollSets Used as: Division Two  Level Two:
The first thing to do in this problem is to sort the input list. Then, you can apply the greedy approach, looking at dolls in increasing order from the smallest one and checking if you can form a set containing the current one. If you can  form it, and mark both dolls as "used". The correctness of this approach can be proven by contradiction (assume that the greedy approach fails at some point, choose the smallest doll on which it fails and prove that you can't build anything better than greedy does). Java implementation of this approach follows: public int maximumQuantity(int[] data, int K) { Arrays.sort(data); boolean[] used = new boolean[data.length]; int ans = 0; for (int i = 0; i < data.length; i++) if (!used[i]) { for (int j = i + 1; j < data.length; j++) if (!used[j] && data[j] == K * data[i] && !used[i]) { used[j] = used[i] = true; ans++; break; } } return ans; }NewAlbum Used as: Division Two  Level Three: Used as: Division One  Level One:
This problem looked misleadingly easy, so a lot of coders missed some special cases and failed it. Only 23 % of D1 and less than 10% of D2 submissions passed system tests. Coders had two major possibilities  write a simple DPsolution or shoot for a constanttime solution. The former is easier and faster, the latter is challenging. The first choice was simple for experienced topcoders. Keep an array representing the optimal answer for each number of songs between 1 and nSongs. The base for the DP will be the case with 0 songs, which obviously requires 0 disks. Then iterate from smaller numbers to larger ones, trying to fit every possible number of songs on a disk: int[] res = new int[nSongs + 1] ; int realCapacity = (cdCapacity + 1) / (length + 1) ; for (int i = 1; i <= nSongs; i++) { res[i] = 100000000 ; for (int j = 1; j <= Math.min(realCapacity, i); j++) if (j % 13 != 0) res[i] = Math.min(res[i], 1 + res[i  j]) ; } return res[n]; If you are bored with DP, the problem can be solved in another way. First, compute the maximal number of songs which can be written on a CD (taking into account the nondivisibleby13 rule). Then, greedily write all songs and see how many songs are written on the last disk. If the number of songs on the last disk is not divisible by 13, we are done. If it is divisible, need to change the number of songs on this disk. To reduce it, you'll need another disk to write the song (because all previous disks already full). To increase the number of songs on this disk, you need to get one song from any other disk. This is always possible with an exception for two cases  either you have exactly one disk (so there is no "other" disk to take a song from), or all other disks have exactly 1 song more than the last one (so moving the song will not change anything). Clearly, the latter 2 cases require 1 disk more than we expected. See Petr's solution for a clean implementation of this approach. StringReplacementsUsed as: Division One  Level Two:
This problem can be split in two parts. First, you need to know how many 'a's, 'b's and 'c's will be generated from the first letter after N steps. Second, you need only those letters which are between left and right characters. Lets solve these parts one by one. The first part can be solved using Dynamic Programming. The state for this DP will be (letter, t = number of seconds left), and the result will be an array of 3 integers (representing the number of 'a's, 'b's and 'c's in the final string received from letter after t seconds). If letter c is replaced by string "ABC", then f(c, n) will be equal to the sum of f(A, n  1) + f(B, n  1) + f(C, n  1): int[][] move = {{0, 2, 1}, {1, 0, 0}, {1, 2, 1}}; long[][][] memo = new long[nSeconds + 1][3][3]; long[] total(int level, int what) { if (memo[level][what][0] != 1) return memo[level][what]; Arrays.fill(memo[level][what], 0); if (level == 0) { memo[level][what][what] = 1; return memo[level][what]; } for (int i = 0; i < 3; i++) { long[] r = total(level  1, move[what][i]); for (int j = 0; j < 3; j++) memo[level][what][j] += r[j]; } return memo[level][what]; } One can easily see that any singleletter string will become a string of 3^{k} characters after k seconds. For example, let the input string be "a". Since each 'a' is replaced by "acb", then each of 'a', 'c' and 'b' will end up in a string of 3^{k  1} characters after (k  1) replacements. Therefore the first 3^{k  1} characters of the answer will be the characters received from string "a" after (k  1) replacements, next 3^{k  1} characters will be received from "c", and, finally, the last 3^{k  1} characters will be received from "b". In other words, "a" will create the substring [0, 3^{k  1}) of the final string, "c" will create the substring [3^{k  1}, 2*3^{k  1}), and "b" will create the last third ([2*3^{k  1}, 3^{k})). To find the answer for string "a" and k replacements, we find the intersections of [left, right] with each of three substrings. For each of these intersections, we recursively proceed to the case with the smaller time left, and sum up the results: long[] solve(int level, int what, long left, long right) { if (left >= right) return new long[3]; if (left <= 0 && right >= Math.pow(3, level)) return total(level, what); long[] ans = new long[3]; long tot = 0; for (int i = 0; i < 3; i++) { long[] add = solve( level  1, move[what][i], Math.max(0, left  tot), Math.min(right  tot, Math.round(Math.pow(3, level  1)))); tot += Math.pow(3, level  1); for (int j = 0; j < 3; j++) ans[j] += add[j]; } return ans; }ColoredBricks Used as: Division One  Level Three:
Lets start from dissecting this problem into parts. First, given two bricks, we need to check whether they look the same. Second, given the coloring of a brick, we need to find the fastest time to make all bricks look exactly the same as this coloring. Third, we need to optimize this approach a bit to make it run within 2 seconds. Now lets go through these steps one by one. First, to determine whether two bricks look the same we need to check every possible rotation of a brick. This is the same as to find every all bricks which look the same as "012345". My way to go here was to emulate two basic rotations of the brick and construct all possible rotations using these basic ones: int[] rotateLeft = {3, 0, 1, 2, 4, 5}; int[] rotateFront = {5, 1, 4, 3, 0, 2}; int[] apply(int[] o, int[] what) { int[] ans = new int[6]; for (int i = 0; i < 6; i++) ans[i] = o[what[i]]; return ans; } .... for (int i1 = 0; i1 < 4; i1++) for (int j1 = 0; j1 < 4; j1++) for (int k1 = 0; k1 < 4; k1++) { int[] pos = new int[6]; for (int i = 0; i < 6; i++) res[i] = i; for (int i = 0; i < i1; i++) res = apply(res, rotateLeft); for (int i = 0; i < j1; i++) res = apply(res, rotateFront); for (int i = 0; i < k1; i++) res = apply(res, rotateLeft); } // The rotation will be stored in res. ....Of course, there existed other ways. For example, misof was lucky to have a nice box nearby, so he just precoded all possible rotations. Anyway, if you want compare two boxes, you need to apply all possible rotations to one box, leaving the other one immovable, and compare the colors of all faces after each rotation. The next step is to find the optimal repainting of one brick into another. This also can be done with the list of transformations mentioned above. Rotate one of the bricks and compute the number of different faces between the bricks (the second brick isn't rotated). The rotation with the smallest number of nonequal faces wins. To find the best answer for all bricks, iterate through all 7^{6} possible colorings of a brick. For each coloring, iterate through all rotations of all input bricks, sum the optimal repaitings for each brick and return the minimal of these sums. Its worth mentioning that the best answer may require repainting at least one face on each brick, so we can't just check the N colorings of our bricks, and must verify all 7^{6} choices. Now lets look how this process can be optimized. First, we can save all possible rotations in an array  so we don't need to generate them all the time. Second, we may try the same coloring several times. To avoid this, hash all colorings into ints and save each coloring (with all possible rotations) in an array of boolean. Third, we can optimize the process of finding the answer for each of the colorings. The simple way to code this is the following: int ans = 6 * N; for each coloring { int sum = 0; for brick i between 0 and N  1{ int opt = 6; for each rotation j opt = min(opt, score for brick i with rotation j) sum += opt } ans = min(ans, sum) }This code requires 7^{6} * N * 24 comparisons of bricks (each brick comparison takes 6 int comparisons), and for each of these comparisons we need to perform a rotation of a brick. The way to speed it up is to rotate the coloring only instead of rotating each of the bricks (keeping the best result for each brick): int ans = 6 * N; for each coloring { int[] res = new int[N]; // Fill this array with big values for each rotation j rotate the coloring to get new coloring v for brick i between 0 and N  1{ int val = score for brick i and coloring v res[i] = min(res[i], val) } } ans = min(ans, sum of all values in res) }Here, we need the same number of comparisons (7^{6} * N * 24), but a much smaller number of rotations (7^{6} * 24). This is more than enough to make it work in time even for slow java and C#. 
