Match Editorial

In my opinion, this was the second easiest set. The easy, RecipeFraction, required some simple string parsing. The hard, CheatABit, required careful coding as opposed to inspiration. 11 coders were able to score above 900. JongMan and lars, who took first and second respectively, both scored over 950.

The Problems

Value	250
Submission Rate	324 / 346 (93.64%)
Success Rate	307 / 324 (94.75%)
High Score	nicka81 for 246.94 points (2 mins 32 secs)
Average Score	202.70 (for 307 correct submissions)

First, we parse each entry of the recipe to compute the total amount of ingredients used. This will function as the denominator of our returned result. Then, for each supplied ingredient, we check how much of it is used in the recipe, and add this to a second total. This functions as the numerator. Java code follows:

public double getFraction(String[] recipe, String[] ingredients) {
   int tot = 0, num = 0;
   for (int i = 0; i < recipe.length; i++) 
      tot += Integer.parseInt(recipe[i].split(" ")[0]);
   for (int i = 0; i < ingredients.length; i++) 
      for (int j = 0; j < recipe.length; j++)
         if (ingredients[i].equals(recipe[j].split(" ")[1])) 
            num += Integer.parseInt(recipe[j].split(" ")[0]);
   return num*1.0/tot;
}

Value	750
Submission Rate	251 / 346 (72.54%)
Success Rate	208 / 251 (82.87%)
High Score	JongMan for 715.18 points (5 mins 3 secs)
Average Score	468.67 (for 208 correct submissions)

In this problem we have the luxury of trying every possible option. Given the list of participating chess programs we try every possible way of inserting ourself into the list. An easy method is to place ourselves at the beginning, and then repeatedly swapping with the next player. For each position we simulate the tournament, and count how many times we had to "cheat". The simulation is performed by taking the original array, and using it to build a secondary array containing the winners. This is repeated until only we are left. Java code follows:

//Number of cheats given we begin in position pos
int simulate(int[] rats, int pos) {
   int ret = 0;
   while (rats.length > 1) {
      int[] next = new int[rats.length/2];
      for (int i = 0; i < rats.length; i+=2) {
         next[i/2] = Math.max(rats[i],rats[i+1]);
         if (i == pos || i+1 == pos) { //check our match
            if (next[i/2] != rats[pos]) ret++;
            next[i/2] = rats[pos];
            pos = i/2;
         }
      } rats = next;
   } return ret;
}
public int enterCodes(int[] ratings, int yourRating) {
   int[] rat = new int[ratings.length+1];
   rat[0] = yourRating;
   for (int i = 1; i < rat.length; i++) rat[i] = ratings[i-1];
   int best = 1000;
   for (int i = 0; i < rat.length; i++) {
      best = Math.min(best, simulate(rat,i));
      if (i+1 < rat.length){
         int t = rat[i+1]; 
         rat[i+1] = rat[i];
         rat[i] = t;
      }
   } return best;
}