Tuesday, December 28, 2004 Match summary 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 500pointers 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 ProblemsSignatureDecoratorUsed as: Division Two  Level One:
This simple Stringmanipulation 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. ParameterSubstitutionUsed as: Division Two  Level Two: Used as: Division One  Level One:
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. ImageSteganographyUsed as: Division Two  Level Three:
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 specialcasing 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. ComboBoxKeystrokesUsed as: Division One  Level Two:
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 shortestpath 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. TriangulationUsed as: Division One  Level Three:
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 nonconvex polygons (and could potentially be trickier if selfintersecting polygons are allowed). This problem required the coder to find a set of N3 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 nonadjacent 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). 
