Algorithm Round 1B Thursday, August 30, 2007 Match summaryCoders 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 ProblemsPopularityUsed as: Division One  Level One:
In this problem we need to sort an array of Strings. To do that, we must
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:
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 ith 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:
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:
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. 
