Match Editorial

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

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

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.

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