JOIN
 Match Editorial
2005 TopCoder Open
Qualification 5

August 16-17, 2005

Match summary

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

RecipeFraction
Used as: Division One - Level One:
 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;
}
```

CheatABit
Used as: Division One - Level Three:
 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;
}
```

By brett1479
TopCoder Member