Match Editorial

In Division 1, the three coders who finished all three problems, Eryx, Snapdragon and kalinov, took the top three spots. They finished the coding phase just about a challenge away from each other, and Eryx's 3 challenges secured his lead while SnapDragon's two moved him into second place. In the end, of course, what was important was that their solutions held up in the system tests.

In Division 2, it almost appeared that newcomers would sweep the top 3 spots, but when an obscene number of 500-pointers failed, the top three spots were again occupied by the only three coders to successfully solve all three problems. The leader was newcomer Snail, followed by BeanSweany, who will be returning to Division 1, and third was fvillaf, who will be entering Division 1 for the first time.

The Problems

Value	250
Submission Rate	174 / 189 (92.06%)
Success Rate	142 / 174 (81.61%)
High Score	Wang_Wei for 249.40 points (1 mins 24 secs)
Average Score	207.50 (for 142 correct submissions)

This simple String-manipulation problem got a few people hung up who didn't read the problem statement carefully enough (or who didn't scrutinize the output of their programs on the example cases closely enough). The idea was that you start with a string and you are given a series of instructions on how to manipulate it by adding "decorations" to it.

The available instructions were "append", "prepend" and "surround". The trickiest of these was surround, because it involved prepending the decoration to the string, and then appending it to the string backwards. By far, the most coders that failed this problem forgot to reverse the string before appending it in surround commands.

Value	500
Submission Rate	111 / 189 (58.73%)
Success Rate	23 / 111 (20.72%)
High Score	Shadowstalker for 371.02 points (18 mins 7 secs)
Average Score	280.74 (for 23 correct submissions)

Value	250
Submission Rate	163 / 172 (94.77%)
Success Rate	91 / 163 (55.83%)
High Score	SnapDragon for 237.64 points (6 mins 32 secs)
Average Score	180.36 (for 91 correct submissions)

While there were several submissions faster than Shadowstalker's in Division 2 and SnapDragon's in Division 1, this problem turned out to have a lot more tricky cases to worry about than most. Using what looked like the clever, easy way messed up most coders and using a method that was simple and "safe" was the way to approach this problem.

The safest way to do this problem was to just iterate one character at a time and construct the output. Normally this means copying the string one character at a time until you run into a '$' symbol. Once you find a '$', you check to see if there's a number after it. If the next digit is not a number, or if it is a number that is greater than the number of parameters, you can just append the '$' and continue as if there were no ‘$’. If a valid digit did follow, you also needed to check if the next character after that was a digit and if the two digits after the '$' formed a number less than or equal to the number of available parameters. Then you insert the parameter indicated by the number after the '$' in place of the '$' and number.

The most common problem was doing a substitution that made something that looked like another parameter show up. A few flavors of this problem were in the examples, but there were one or two ways to make this happen that people didn't think about. Another common problem was that peoples' code couldn't handle parameters next to each other with no characters in between.

Value	1000
Submission Rate	21 / 189 (11.11%)
Success Rate	16 / 21 (76.19%)
High Score	Obviously for 707.99 points (20 mins 4 secs)
Average Score	572.39 (for 16 correct submissions)

This problem was inspired by my father, who uses steganography tools in his work. The idea behind steganography is that one can encrypt data into a file that doesn't appear to be anything secret. A bmp image or a wav sound clip can have loads of data encrypted in them and look/sound indistinguishable from their original form.

In this problem, you needed to encrypt each character of the input into three bytes of the output. One easy way to go about this problem was to start by creating an array of numbers from 0 to 3 that is 3 times as long as the message to be encoded. This represents the numbers to be encoded into the image. Then go through the numbers in the original image and insert these numbers (one way to do this is imageNum/4*4+encodeNum).

The final trick was that you had to encode an "end of message" number, which is basically putting a 3 in every spot after the message is done.

I avoided special-casing anything in my solution, which is hardly minimal:

   public String[] encode(String[] image, String message)
   {
      String[] ret = new String[image.length];
      int[] encoded = new int[801];
      for (int i=0; i<encoded.length/3; i++)
      {
         int letter = 63;
         if (i < message.length())
         {
            if (message.charAt(i) == ' ')
               letter = 0;
            else if (message.charAt(i) >= 'A' && message.charAt(i) <= 'Z')
               letter = 1+message.charAt(i)-'A';
            else if (message.charAt(i) >= 'a' && message.charAt(i) <= 'z')
               letter = 27+message.charAt(i)-'a';
            else if (message.charAt(i) >= '0' && message.charAt(i) <= '9')
               letter = 53+message.charAt(i)-'0';
         }
         encoded[i*3] = 3&letter;
         encoded[i*3+1] = 3&(letter>>2);
         encoded[i*3+2] = 3&(letter>>4);
      }
      int index = 0;
      DecimalFormat fmt = new DecimalFormat("000");
      for (int i=0; i<ret.length; i++)
      {
         ret[i] = "";
         for (int j=0; j<image[i].length(); j+= 3)
         {
            int current = Integer.parseInt(image[i].substring(j, j+3));
            current = current/4 * 4 + encoded[index++];
            ret[i] += fmt.format(current);
         }
      }
      //System.out.println(decode(ret));
      return ret;
   }

An interesting exercise I did while writing this problem is writing a decoder for the image.

Value	500
Submission Rate	127 / 172 (73.84%)
Success Rate	87 / 127 (68.50%)
High Score	SnapDragon for 481.67 points (5 mins 35 secs)
Average Score	343.50 (for 87 correct submissions)

The best part about this problem is how many possible ways there are to look at it. One way, for instance, is to model the problem as an unweighted directed graph, and make edges from each element to the next element to start with each letter. Then it becomes a very typical shortest-path algorithm. Another method is to start from each element and make an array of best distances. The starting element always requires 0 keystrokes, then for each element, the next element starting with each letter of the alphabet requires no more than one more keystroke than the current element. My implementation looks like this:

   public int minimumKeystrokes(String[] elements)
   {
      String e = "";
      for (int i=0; i<elements.length; i++)
         e += elements[i].toLowerCase().charAt(0);
      int max = 0;
      for (int i=0; i<e.length(); i++)
      {
         int[] dists = new int[e.length()];
         Arrays.fill(dists, 1000000000);
         dists[0] = 0;
         String e2 = e.substring(i) + e.substring(0, i);
         for (int j=0; j<e.length(); j++)
         {
            for (char c = 'a'; c <= 'z'; c++)
            {
               int ind = e2.indexOf(c, j+1);
               if (ind >= 0)
                  dists[ind] = Math.min(dists[ind], dists[j] + 1);
            }
            max = Math.max(max, dists[j]);
         }
      }
      return max;
   }

One of the things that makes this implementation simple is that I am always starting from the first element of the combo box, and I manipulate the combo box to start on each element in sequence.

Value	1000
Submission Rate	9 / 172 (5.23%)
Success Rate	3 / 9 (33.33%)
High Score	Eryx for 453.78 points (44 mins 42 secs)
Average Score	411.52 (for 3 correct submissions)

This problem is a very common thing to do in the area of computer graphics, because writing code for triangles can often be more efficient than writing it for general polygons. Doing this can be tricky, however, with non-convex polygons (and could potentially be trickier if self-intersecting polygons are allowed).

This problem required the coder to find a set of N-3 lines that could be drawn to correctly triangulate the polygon. Since almost any polygon has more than one correct triangulation, the set of lines should be the lexicographically smallest possible. This didn't make the problem more complicated as much as it told you what order to look at lines.

The basic algorithm required to do this involved starting from the first point, and trying to insert a line from that point to every non-adjacent point after that. For each of these lines, if the line doesn't intersect any previous lines or any of the edges of the polygon, and if it's inside the polygon, you can add it to your output.

At this point, the problem becomes two simpler problems now - how do you check if two lines intersect, and how do you determine if a line is inside a polygon (if the line doesn't intersect any of the edges of the polygon, it will either be all inside or all outside the polygon). To answer these questions, I recommend reading the recent TopCoder editorials on geometry: This one explains how to find out where two lines intersect (you then must decide if that point is on both line segments). This one explains how to decide if a point is inside a polygon (just try it with the midpoint of the new line).