Get Time
statistics_w  Match Editorial
2003 TopCoder Open
Qualification Round 2

Thursday, October 9, 2003


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

LetterFreq discuss it
Used as: Division One - Level One:
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;

Mandelbrot discuss it
Used as: Division One - Level Two:
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
Beginning with z(0)=c, we can iteratively compute the values of z(x) for all pertinent x, and test for magnitudes above 2. Java code follows:
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;
Alternatively, we could have computed z(x) recursively, but this could take some extra doing, seeing as a complex value need be passed through the call chain. Many coders accidently computed z(x+1)=z(x)*z(x)+z(x), generating multiple questions about incorrect test cases.

BitmapToGraph discuss it
Used as: Division One - Level Three:
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");
Such a method will correctly format the strings, and produce the necessary sorting method using the native string comparator.

By brett1479
TopCoder Member