JOIN
 Match Editorial
2005 TopCoder Collegiate Challenge
Qualification Problem Set 3

January 11-12, 2005

Summary

This was one of the harder problem sets, though the examples on the easy problem were sufficiently comprehensive to ensure that almost the full 100 advanced. lingo took top honors, with a narrow victory over Jan_Kupiers.

# The Problems

DictionarySorter
Used as: Division One - Level One:
 Value 250 Submission Rate 123 / 162 (75.93%) Success Rate 89 / 123 (72.36%) High Score Per for 234.32 points (5 mins 57 secs) Average Score 159.84 (for 89 correct submissions)

For those who had never heard of the ash and thorn characters, they are æ and þ, respectively, and occur often in most old germanic languages.

The best way to solve this problem is to use the built-in sort method that your language of choice provides. Then, all you have to do is write a comparator that tells which of two words should come first. There are a lot of different ways to write the comparator, but one observation will simplify things a little. You don't really need to worry about the fact that the escaped sequences count only as a single letter. If you are comparing "/ae" or "/th" to an unescaped sequence, the rest of the letters don't matter. Therefore, you can write the comparator with a single for loop:

```int value(string a, int idx){
if(a.charAt(idx) == '/')return a.charAt(idx+1)*2+1;
else return a.charAt(idx)*2;
}
int compare(string a, string b){
for(int i = 0; i<min(a.length(),b.length()); i++){
if(a.charAt(i) != b.charAt(i)){
int v1 = value(a,i);
int v2 = value(b,i);
return v1-v2;
}
}
return a.length()-b.length();
}
```
Finally, if you really knew your Java API well, you could use the relatively obscure java.text.RuleBasedCollator:
```RuleBasedCollator r = (RuleBasedCollator)
Collator.getInstance(new Locale("en","US",""));
Comparator c = new RuleBasedCollator(r.getRules() +
" & a < '/'ae < b & t < '/'th < u");
Arrays.sort(words,c);
return words;
```

TimeAnalysis
Used as: Division One - Level Three:
 Value 1000 Submission Rate 44 / 162 (27.16%) Success Rate 27 / 44 (61.36%) High Score dgarthur for 668.55 points (18 mins 0 secs) Average Score 488.23 (for 27 correct submissions)

This problem can best be broken into two parts. First, parse the expression, and calculate the result in nanoseconds. Then, pick the correct units, and adjust the result. The grammar for the equation was fairly simple, since it didn't have any parentheses in it (the ones from lg() don't really count, since they can only have a variable inside them). If there is a '+' in the eqation, you should split the equation at the plus, then recursively evaluate the two halves, and add the results together. Otherwise, if there is no plus, but there is an '*', you should again split the equation in half, recursively evaluate, and then multiply the results. If the equation has neither '*' nor '+' in it, then it must have one of the 4 possible TERM forms, each of which is relatively easy to evaluate (just be careful to do everything using doubles):

```double evaluate(string equation){
if(equation.contains('+')){
int idx = equation.indexOf('+');
string a = equation.substring(0,idx);
string b = equation.substring(idx+1);
return evaluate(a)+evaluate(b);
}else if(equation.contains('*')){
int idx = equation.indexOf('*');
string a = equation.substring(0,idx);
string b = equation.substring(idx+1);
return evaluate(a)*evaluate(b);
}else{
return term(equation);
}
}
```
Once you have the result in nanoseconds, you can hard code the different ranges as constants, or calculate them doing something like the following.
```int[] factors = {1000,1000,1000,60,60,24,365};
String[] units = {
"nanoseconds",
"microseconds",
"milliseconds",
"seconds",
"minutes",
"hours",
"days",
"years"};
for(int i = 0; i < units.length; i++){
if(ops<factors[i]){
return (int)ops + " " + units[i];
}
ops /= factors[i];
}
return (int)ops+" years";
```
By lbackstrom
TopCoder Member