JOIN
 Match Editorial
2007 TopCoder Collegiate Challenge
Algorithm Round 1B

Thursday, August 30, 2007

## Match summary

Coders from Russia dominated this round, occupying the top 3 spots in the final table. Rating favorite Petr easily won this round, followed by TCO07 finalists darnley and Vitaliy.

# The Problems

Popularity
Used as: Division One - Level One:
 Value 250 Submission Rate 465 / 510 (91.18%) Success Rate 420 / 465 (90.32%) High Score misof for 248.57 points (2 mins 9 secs) Average Score 196.33 (for 420 correct submissions)

In this problem we need to sort an array of Strings. To do that, we must

• compute the popularity of each of the names
• sort the array to arrange the popularities in non-increasing order
• make sure that our sorting method is stable (that it preserves the order of the names of the same popularity)
To compute the popularity of each of the names, we first find the first name for each of the invitation letters. Then we create an array, with the i-th element storing the popularity of the i-th input name, and sort it according to the popularities. To make sure the sort algorithm is stable, we'll implement a simple bubble-sort. Please find a simple java-solution below (since the input array is at most 50 elements, we can compute all popularities from the scratch any time we need them):
```    public String[] sort(String[] data) {
for (int i = 0; i < data.length; i++)
for (int j = 0; j < data.length - 1; j++) {
int a1 = 0;
for (int k = 0; k < data.length; k++)
if (data[k].split(" ")[0].equals(data[j].split(" ")[0]))
a1++;
for (int k = 0; k < data.length; k++)
if (data[k].split(" ")[0].equals(data[j + 1].split(" ")[0]))
a1--;
if (a1 < 0) {
String v = data[j];
data[j] = data[j + 1];
data[j + 1] = v;
}
}
return data;
}

```

MutateTree
Used as: Division One - Level Two:
 Value 500 Submission Rate 266 / 510 (52.16%) Success Rate 176 / 266 (66.17%) High Score Soultaker for 424.32 points (12 mins 27 secs) Average Score 277.53 (for 176 correct submissions)

This problem can be solved in a number of ways. For example, you can transform the input into a tree structure (storing a father and a couple of children for each of the nodes), swap the subtrees and return a String representation of the resulting tree. Since all these algorithms are classical, we'll explain another approach.

In fact, to return the representation of the tree after the swap we don't need to construct the tree itself. We will find two substrings of the input, which completely describe the subtrees rooted with root1 and root2 respectively. Then we'll check whether the substrings intersect (checking for an overlap), swap them in the string and return the result.

If the input string represents a valid tree, then for each index K you can find another index L such that the substring between indices L and K will represent a subtree rooted at the vertex at position K. We'll create an array (first in the code below) and the i-th element of this array will represent the first character of the subtree rooted at vertex number i. This value can be easily found in the following way:

• If the i-th character of the input is an uppercase letter, then first[i] = i.
• Otherwise, the (i-1)-th character represents the right child of the i-th vertex, string between first[i - 1]-th and (i-1)-th characters represents the string rooted at the (i-1)-th vertex, and string between first[first[i - 1] - 1]-th and (first[i - 1] - 1)-th characters represent the subtree rooted at the left child of the i-th vertex. Therefore, first[i] = first[first[i - 1] - 1].
As we find that, the solution becomes quite obvious. We compute the elements of first iterating through the input string and checking whether the input tree is valid. If the input represents a valid tree, checking whether two input trees intersect is easy, as well as swapping the corresponding substrings in the output:

```    public String newTree(String tree, int r1, int r2) {
if (r1 > r2) {
int tmp = r1;
r1 = r2;
r2 = tmp;
}
int n = tree.length();
int[] first = new int[n];
for (int i = 0; i < n; i++) {
if (tree.charAt(i) >= 'A' && tree.charAt(i) <= 'Z') {
first[i] = i;
continue;
}
if (i - 1 < 0) return "BADTREE";
int j = first[i - 1] - 1;  //j is last in i's lc
if (j < 0) return "BADTREE";
first[i] = first[j];
}
if (first[n - 1] != 0) return "BADTREE";  //(fix)
int f1 = first[r1], f2 = first[r2];
if (f2 <= r1) return "OVERLAP";
return tree.substring(0, f1) + tree.substring(f2, r2 + 1) +
tree.substring(r1 + 1, f2) + tree.substring(f1, r1 + 1) + tree.substring(r2 + 1);
}
```
MarbleTop
Used as: Division One - Level Three:
 Value 1000 Submission Rate 102 / 510 (20.00%) Success Rate 21 / 102 (20.59%) High Score Petr for 864.90 points (11 mins 36 secs) Average Score 644.16 (for 21 correct submissions)

The first thing to observe in this problem is that the orders of length k are special ones - first, we can get plenty of them as a side effect of others orders, and, second, we can cut at least one marble of length k out of any stock marble of length > k. Therefore it might be a good idea to fill other orders first.

Obviously, if we can use several marbles from the stock to get a marble of some length m, the best way is to use the shortest available marble. This gives us a very simple algorithm to check the availability for all orders (except for those of length k) - sort all stock marbles, iterate through all orders. For each order[i], find the shortest stock marble of size (order[i] + i * k) and remove this marble from the stock. Of course, if there is no such marble for at least one order, the method should return -1. Also, count how many marbles of length k you cut during the process.

Now we need to fulfill the orders for the marbles of length k. First, compute the number of marbles of length k you already have (those you had in stock plus those you might have gotten some while fulfilling other orders). If you already have enough marbles, the process is over. Otherwise, you need to cut more marbles of length k from longer ones. The last trick to note is that cutting marbles of length divisible by k is better than others, so you should cut marbles of lengths i * k first. The implementation of this algorithm should be pretty easy; see Petr's solution as an example.

By Olexiy
TopCoder Member