JOIN
 Match Editorial
CRPF Charity Challenge
Round 1

Tuesday, November 11, 2003

Summary

I always love watching, and writing about tournaments, but tonight's competition was better than usual. The first round of the TopCoder Charity Challenge united coders to help a great cause. Everyone was in high spirits, and it seemed to affect their performance. Coders were in top form, with 23 people scoring over 1000. In an unusual twist of events, yellow rated competitors dominated the score board, with only 2 reds winning their rooms. indigo9, a blue rated coder, surpassed 5 higher ranked coders, including 2 reds, to win room 5. It is clear that Monday's final competition for the 4 winning spots will be exciting.

# The Problems

AustrianLotto
Used as: Division One - Level One:
 Value 250 Submission Rate 75 / 75 (100.00%) Success Rate 75 / 75 (100.00%) High Score gladius for 248.13 points (2 mins 28 secs) Average Score 232.03 (for 75 correct submissions)

This is a classic tallying problem: "Given a set of events, count how many of each variety there are." We first allocate an array, which will hold the counts of each type. Then we process each event, and increment the correct counter. Once done, our array is the solution. Java code follows:

```public int[] evaluate(String drawing, String[] picks) {
int[] ret = new int[7];
String[] dtoks = drawing.split(" "); //Split by spaces
for (int i = 0; i < picks.length; i++) {
String[] currToks = picks[i].split(" "); //Split by spaces
int cnt = 0;
for (int x = 0; x < currToks.length; x++) {
for (int y = 0; y < dtoks.length; y++) {
if (Integer.parseInt(dtoks[y])==Integer.parseInt(currToks[x])) cnt++;
}
}
ret[cnt]++; //Increment counter
}
return ret;
}
```

RoomSummary
Used as: Division One - Level Two:
 Value 500 Submission Rate 65 / 75 (86.67%) Success Rate 31 / 65 (47.69%) High Score Maris for 404.29 points (14 mins 33 secs) Average Score 307.75 (for 31 correct submissions)

In this problem, coders were required to simulate a competition round and return the scores of each player. Since the constraints verified the round would proceed normally, no input error checking was required. First build a 2-dimensional array whose rows represent coders, and columns represent each problem. Next loop through each submission, and record the scores in the array. Similarly loop through each challenge, and then each systest, recording score changes in the array. When all is done, final scores can be extracted from the table. Using a hand coded sort or comparator, the coders can be arranged into proper order. The final step is to output in the correct format. To convert from doubles, simply multiply by 100, cast to an int, and then extract the required digits.

CongruenceLock
Used as: Division One - Level Three:
 Value 1000 Submission Rate 44 / 75 (58.67%) Success Rate 25 / 44 (56.82%) High Score abiczo for 953.74 points (6 mins 19 secs) Average Score 839.90 (for 25 correct submissions)

Two different solutions to this problem come to mind, both of which use an array to cache results in a dynamic programming fashion. The first method loops over the different kinds of buttons. Once the ith iteration is complete, the array will store the least possible number of presses required to produce any target, using the first i buttons. Code for this method follows:

```public int minPushes(int current, int target, int[] buttons) {
int[] dp = new int[100000];
Arrays.fill(dp,-1);
dp[current] = 0;
for (int i = 0; i < buttons.length; i++) {
for (int xx = 0; xx < dp.length; xx++) {
int x = xx;
if (dp[x]==-1) continue;
int next = (x+buttons[i])%100000;
while (dp[next] ==-1 || dp[next] > dp[x]+1) { //HERE
dp[next] = dp[x]+1;
x = next;
next = (next+buttons[i])%100000;
}
}
}
return dp[target];
}
```
For a given button, to efficiently account for all reachable targets, we loop over each value. Then, in the loop marked HERE, we continually push the button, as long as it continues to improve the scores for the targets we reach. Another method used by many coders, was to implement a table-aided breadth-first-search. Instead of looping over buttons, we loop over the number of button presses, stopping when we reach the target. Since the table stores the targets already produced earlier in the search, we can avoid reexamining those values.

By brett1479
TopCoder Member