Match Editorial

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

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];
}

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;   
}