
Match Editorial 
CRPF Charity Challenge
Round 1Tuesday, 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 2dimensional 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 tableaided breadthfirstsearch. 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