Match Editorial

With another day of fierce competition in the books, the 2003 TopCoder Open sponsored by Intel® heads into its opening round. 600+ coders battled furiously for the 200 advancing spots. Many competitors, who hadn't qualified on Tuesday, came back to try and change their fate. The new unrated coders, covered in a veil of mystery, sparked much attention. Each could potentially be the next SnapDragon or Tomek. At 10:00 the round began, and submissions started flying in. Minutes into the competition, many were already testing their medium problem. Things changed once the hards were opened. Average submission frequency remained low for a good 20-30 minutes. It wasn't until the last 10 minutes, that most rooms had point totals in the thousands. Unfortunately, many of these scores were inflated. In a rush to claim a seat in the tournament, many coders hastily submitted incorrect solutions. Only 13 level 3 submissions withstood systests. Once the dust had settled, coders who accurately completed the first two in an average amount of time would move on. Others will compete vicariously through the victors.

The Problems

Value	250
Submission Rate	545 / 578 (94.29%)
Success Rate	516 / 545 (94.68%)
High Score	leadhyena_inran for 249.42 points (1 mins 22 secs)
Average Score	222.39 (for 516 correct submissions)

This easy was a classic loop and process problem. Here we are looking for letters, insensitive to case. To solve it, we allocate an array of integers, which will keep track of the letters seen. Java code follows:

public int[] getFreqs(String[] doc) {
   int[] ret = new int[26]; //for tallying
      for (int i = 0; i < doc.length; i++) {
         doc[i] = doc[i].toUpperCase(); //case-insensitive
      for (int j = 0; j < doc[i].length(); j++) {
         if (Character.isLetter(doc[i].charAt(j) ) ) ret[doc[i].charAt(j)-'A']++;
      }
   } return ret;
}

Value	450
Submission Rate	457 / 578 (79.07%)
Success Rate	378 / 457 (82.71%)
High Score	frypan for 437.66 points (4 mins 47 secs)
Average Score	331.28 (for 378 correct submissions)

As directed by the problem, we must check each integer x in [0,max] to determine whether the given complex value is in the Mandlebrot set. The check consists of testing if the magnitude of z(x) is at most 2, for each x. To aid in this matter, the problem has provided a recurrence defining the value of z(x) inductively:

           z(0)   = c
           z(x+1) = z(x)*z(x) + c

public int iterations(int max, double origa, double origb) {
   double a = origa, b = origb;
   for (int i = 0; i <= max; i++) {
      if (Math.sqrta*a+b*b)>2) return i;
      double tempa = (a*a-b*b)+origa;
      b =  2*a*b+origb; 
      a = tempa;
   } return -1;
}

Value	1050
Submission Rate	63 / 578 (10.90%)
Success Rate	13 / 63 (20.63%)
High Score	Jan_Kuipers for 586.28 points (31 mins 1 secs)
Average Score	464.74 (for 13 correct submissions)

The hard clearly stood out from the rest, in terms of required code amount. In this problem, we must turn character input into a graph, and return edge information. The heart of the solution loops over each character of the input, and determines whether it is a node. If so, check all neighboring squares for edges, and traverse all paths to their ends. Traversals were done both recursively and iteratively by competitors, both with varied success. The most significant issue was accounting for loops, so as to not count them twice at a node. Simply removing all traversed edge characters will not work, since multiple edges may share edge characters. To avoid such a problem, I marked all edge characters used while processing a single node. Once done processing the node, I removed all markings. This way, the edges would remain, if needed by another node.

To handle the return value sorting, I used the built in String sorting features. This required some doing, do to varying number lengths. Lets say I was storing each piece of edge data as "dest:len". Simply sorting the strings could produce incorrect results since a string like "10:4" would lexicographically occur before "2:4". To alleviate this issue, I stored all the numbers using a DecimalFormat that forced them to be at least 10 characters in length. This was done with code similar to the following:

   int dest = something, len = somethingelse;
   DecimalFormat df = new DecimalFormat("000000000");
   edgeStorage.add(df.format(dest)+":"+df.format(len));
   /*later*/
   Collections.sort(edgeStorage);