JOIN
 Match Editorial
2005 TopCoder Open
Qualification 3

August 16-17, 2005

Match summary

Like some of the other qualification sets, this easy and hard followed the iterative/recursive pattern. The easy, CompanyName, was the most difficult level 1 problem in any of the sets. The hard, Fuses, was also no slouch. Despite the difficulty, 13 coders managed to score over 900 points. This room, which contained many of the best coders on TC, was led by SnapDragon and marek.cygan. Both scored over 950.

# The Problems

CompanyName
Used as: Division One - Level One:
 Value 250 Submission Rate 314 / 354 (88.70%) Success Rate 214 / 314 (68.15%) High Score m00tz for 240.29 points (4 mins 36 secs) Average Score 171.30 (for 214 correct submissions)

Here we must compute a score for each given string, and then take the one with the lowest score. The vowel score is computed by counting the number of contiguous vowel groups. To do this we increment a counter for each vowel not preceded by a vowel. We must also compute a consonant score. Each consonant contributes 2 points to the score, but each consonant group removes 1. The same technique used on the vowels applies here. Java code follows:

```
boolean isVowel(char c) { return "AEIOUaeiou".indexOf(c) != -1; }
public String shortestProposal(String[] proposals) {
int best = 100000, bestpos = 0;
for (int i = 0; i < proposals.length; i++) {
int vs = 0, cs = 0;
for (int j = 0; j < proposals[i].length(); j++) {
char c = proposals[i].charAt(j);
if (isVowel(c)) {
if (j == 0 || !isVowel(proposals[i].charAt(j-1))) vs++;
} else {
cs += 2;
if (j == 0 || isVowel(proposals[i].charAt(j-1))) cs--;
}
}
if (vs + cs < best) {
best = vs + cs;
bestpos = i;
}
} return proposals[bestpos];
}
```

Fuses
Used as: Division One - Level Three:
 Value 750 Submission Rate 264 / 354 (74.58%) Success Rate 136 / 264 (51.52%) High Score SnapDragon for 737.12 points (3 mins 1 secs) Average Score 527.94 (for 136 correct submissions)

Seeing as we aren't sure how many fuses we will need, we try each possible amount. The constraints guarantee we will never require more than 5. When trying a particular number of fuses, we recursively try to assign each device to one of the fuses. If all devices can be assigned we are done. Java code follows:

```boolean solve(int[] amps, int[] fuses, int pos) {
if (pos == amps.length) return true;
boolean ret = false;
for (int i = 0; i < fuses.length; i++) {
if (amps[pos] + fuses[i] > 20) continue;
fuses[i] += amps[pos];
ret |= solve(amps,fuses,pos+1);
fuses[i] -= amps[pos];
}
return ret;
}
public int minFuses(int[] amps) {
for (int f = 1; ;f++)
if (solve(amps,new int[f],0)) return f;
}
```

By brett1479
TopCoder Member