JOIN
 Match Editorial
SRM 296
Monday, April 3, 2006

Match summary

This was one of the last SRMs before the ACM-ICPC 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, first-timer 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 Problems

EratosthenSieve2
Used as: Division Two - Level One:
 Value 250 Submission Rate 320 / 421 (76.01%) Success Rate 279 / 320 (87.19%) High Score cypressx for 246.89 points (3 mins 11 secs) Average Score 177.09 (for 279 correct submissions)

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 k-th 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) {
List lst = new LinkedList();
for (int i = 0; i < 1000; i++) lst.add(i + 1);
for (int i = 2; i <= 10; i++) {
int pos = 0;
while (pos < lst.size() - i + 1) {
pos += (i - 1);
lst.remove(pos);
}
}
return lst.get(n - 1);
}
}
```

DollSets
Used as: Division Two - Level Two:
 Value 500 Submission Rate 250 / 421 (59.38%) Success Rate 101 / 250 (40.40%) High Score cypressx for 491.11 points (3 mins 50 secs) Average Score 373.04 (for 101 correct submissions)

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:
 Value 1000 Submission Rate 217 / 421 (51.54%) Success Rate 19 / 217 (8.76%) High Score Hutafeng for 967.21 points (5 mins 15 secs) Average Score 635.79 (for 19 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 290 / 305 (95.08%) Success Rate 67 / 290 (23.10%) High Score marek.cygan for 244.87 points (4 mins 7 secs) Average Score 185.72 (for 67 correct submissions)

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 DP-solution or shoot for a constant-time 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 non-divisible-by-13 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.

StringReplacements
Used as: Division One - Level Two:
 Value 500 Submission Rate 174 / 305 (57.05%) Success Rate 83 / 174 (47.70%) High Score Petr for 441.36 points (10 mins 38 secs) Average Score 258.05 (for 83 correct submissions)

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 single-letter string will become a string of 3k 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 3k - 1 characters after (k - 1) replacements. Therefore the first 3k - 1 characters of the answer will be the characters received from string "a" after (k - 1) replacements, next 3k - 1 characters will be received from "c", and, finally, the last 3k - 1 characters will be received from "b". In other words, "a" will create the substring [0, 3k - 1) of the final string, "c" will create the substring [3k - 1, 2*3k - 1), and "b" will create the last third ([2*3k - 1, 3k)). 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:
 Value 1000 Submission Rate 66 / 305 (21.64%) Success Rate 25 / 66 (37.88%) High Score AdrianKuegel for 687.28 points (21 mins 19 secs) Average Score 536.72 (for 25 correct submissions)

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 non-equal faces wins. To find the best answer for all bricks, iterate through all 76 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 76 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 76 * 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 (76 * N * 24), but a much smaller number of rotations (76 * 24). This is more than enough to make it work in time even for slow java and C#.

By Olexiy
TopCoder Member