Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?   Lessons Learned

Single Round match 95 was a Wednesday night contest. For the cognoscenti, it was the first match with the spiffing new arena, complete with shiny new lobbies and list sorting. In the more mundane, real world, it was the day before Intel announced a profit warning, and their stock tanked.

The problem slate for Div2 was generally easier than in recent contests. Both the level 2 and 3 problems were based on "pointer arithmetic". Perhaps it would be useful for writers to check for variety in a problem slate?

300 (PhoneNum):

This problem took a string of numbers and digits representing a phone number, and required that the number be correctly formatted as either a long distance number eg (800)345-5555 or local number eg 345-5555. The letters Q and Z represented 0, and the other letters were split into groups of 3 to represent 2-9. A decoded number less than 7 digits long was invalid, and greater than 9 digits was long distance. Excess digits were to be discarded.

My solution involved two passes: one to translate the digits, and get rid of meaningless characters, and a second to correctly format the number. On the night, I came up with something like:

StringBuffer sb = new StringBuffer();
for (i=0; i < input.length() ; i++) {   
   c = input.charAt(i);
   if (Character.isLetter(c)) {
      if (c == 'Q' || c == 'Z') {
         sb.append(0);   
      } else {
         if (c > 'Q') c--;
         int digit = c / 3 + 2;
         sb.append(digit);   
      }   
   }
   if (Character.isDigit(c)) sb.append(c);   
}

I wasn't particularly sharp, and the whole solution took 3 or 4 debugging iterations. The code above was changed on the first iteration, and I didn't trust it afterwards, although the bugs were elsewhere.

It preys on my mind that this took me too long. Another solution was to have a heap of "if" statements:

for (i=0; i < input.length() ; i++) {   
   c = input.charAt(c);
   if (c >= 'A' && c <= 'C')
      sb.append(2);      
   if (c ....
}

And the third solution was to initialise an array:

String[] digitClass = { "ABC","DEF","GHI","JKL","MNO"....};
for (i=0; i < input.length() ; i++) {   
   char c = input.charAt(i);
   for (j=0; j < digitClass.length ; j++) {   
      if (digitClass[j].indexOf(c) != -1)
         sb.append(j+2);
   }   
   if ("QZ".indexOf(c) != -1) sb.append(0);
   if (Character.isDigit(c)) sb.append(c);
}   

This strikes me as a classic problem challenge trade-off. What do I want from the solution?

1. Fast coding time.
2. Reliability (ie works first time, and I trust it.)
3. (A very poor third) Elegance.

I'm still not sure what the best solution here is under those criteria, but I lean towards cutting and pasting the Strings. Note that this is probably the worst solution in a real program because of the memory cost.

Anyway, back to the errors.

Problems:

1. Mistyping the characters that were checked (eg "if (c =='Q' || c == 'Q')")
2. In the "formatting phase", making indexing errors taking substrings.
3. In the formatting phase, using ">7" instead of ">=7" when checking for numbers which are too short.
4. Range checking: "if ('A'<=ch && ch<='Z') {"
5. Misreading the problem regarding range checking, so that the solution doesn't deal with anything other than 7 or 10 digits.
6. Indexing from 1 instead of 0 in an sprintf statement.

A pretty good performance on challenge: 50 out of 94 buggy submissions were caught with challenges.

600 (Shellsort):

This problem took an array of ints, an offset and an increment, and required the extraction of a sub-array,

As problems go, this is one of the easier level 2 problems we've seen. The only catch is to get the indexing right.

With hindsight, I'd suggest using an ArrayList or Vector, then converting that to an int[]. This would avoid the risk of indexing errors:

Vector vec = new Vector();
for (i=0; i < input.length ; i++) {   
   if (i % K == segNum) {
      vec.add(new Integer(input[i]));
   }
}   
int ret[] = new int[vec.size];
for (i=0; i < ret.length ; i++) {   
   ret[i] = ((Integer)vec.elementAt(i)).intValue();
}   

Problems:

1. Indexing errors resulting in exceptions.
2. Logic which incremented the index into the returned array, based on code like the following

       lastseg = seg;
            seg = (seq + 1) % K;
            if (seq < lastseq) index++;
    

This fails if K == 1;
3. Although I didn't spot this, allocating too long an array was another possible error.

On challenge phase, 13 of 40 buggy solutions were caught.

1000 (Funnel):

Construct an upside-down triangle by taking 1,3,5...etc characters from the end of a string, padding the last line where necessary. The method is passed 2 parameters which define which line of the triangle, and which character of that line should be returned.

One neat trick to use for this problem is that 1 + 3 + 5 +...+ 2n-1 = n^2. Still, the problem is one of String manipulation and index arithmetic. The same problem was used as the level 2 in div1 also, and almost a third of submissions there failed also, compared 52% in Div2.

Problems:

1. Indexing errors resulting in exceptions.
2. Failing to pad correctly.

On challenge phase, 32 of 91 buggy solutions were caught.