Match Editorial

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

Srm 97 was a wednesday night match. "En Topcoder", it was the night that Reid blew through the 3000 point barrier. In the rest of the world, it was the day that Argentina were knocked out of the Soccer World Cup.

As matches go, the problem set for Division-II is probably one of my favourites. The problems seem to me to give freshness to existing themes. There appear to have been a little over 330 coders in Div-II. Each of the first two problems had a success rate of above 66%, and the third problem was real challenge. This was done without resorting to obscurity or mindless complexity. In my view, that made for a good, tough match.

250 (MountainP):

Take a string, sort the characters, then add the minimum necessary to make a palindrome.

Not a great deal to be said, except that this isn't the sort of problem which most of us have had to think about previously.

One approach (indexing physically):

char[] data = input.toCharArray();
Arrays.sort(data);
StringBuffer sb = new StringBuffer(new String(data));
char c = data[data.length-1];
for (int i = data.length-1; i >= 0; i++) {
   if (c != data[i]) {
      sb.append(data[i]);
   }
}
return sb.toString();

Problems:

1. A number of coders included a palidrome test (probably because palidromes featured in the previous match.) The test-case "racecar" in particular exacted a toll when code-paths weren't worked out right.
2. Some coders failed when there were duplicate instances of the last letter.
3. One way to reverse a String is to use StringBuffer.reverse(). However, unlike String, StringBuffer is not immutable, and the original StringBuffer is changed. So code like

StringBuffer sb1 = new StringBuffer();
StringBuffer sb2 = new StringBuffer();
sb1.append(input):
sb2 = sb1.reverse();

Less than a third of failing solutions were caught by challenges. I'd argue that close attention to this problem was the easiest way to find a successful challenge. The grey coders did beet here: they successfully challenged 39% of failing submission vs only 18.5% in the green rooms. Neatly, that's twice as good.

This problem's input was a target and an array to represent moves in a hypothetical game. The values (i, input[i]) represented a directed edge. The goal was to return an array of all values of i whose successor sequence contains the target.

where 0<=i<input.length where the sequence { i, input[i], input[input[i]], ... } contained a particular value.

The solution is obvious to me now: simply trace the path starting at each possible index of the array, and check whether the target was in the sequence. A little care was needed to check for loops, but otherwise, the solution isn't taxing. I give a complete solution:

import java.util.*;
public class JumpGame {
    public int[] whichOnes(int[] boardSpec, int target) {
   // We will cache each 
   ArrayList al = new ArrayList();      
        for (int i = 0; i < boardSpec.length;i++) {
            if (check(boardSpec, target, i, 0)) {
      al.add(new Integer(i));
            }
        }
        int[] ret = new int[al.size()];
        for (i = 0; i < al.size();i++) {
            ret[i] = ((Integer)al.get(i)).intValue();
        }
        return ret;
    }
    boolean check(int[] arr, int target, int val, int count) {
        if (count == arr.length) return false;
        if (arr[val] == target) return true;
   return check(arr, target, arr[val], count+1);
    }
}

This clearly shows two Java design decisions interacting to make C++ a better choice for this problem. These are the fact that {int, char, boolean, etc} are not objects, and that extensible arrays like ArrayList and Vector only hold objects.

In contrast, the same solution in C++ (my first ever C++ program...):

#include <string>
#include <vector>
class JumpGame {
public:
    vector<int> whichOnes(vector<int> boardSpec, int target) {
        vector<int> ret;
        for (int i = 0; i < boardSpec.size();i++) {
            if (check(boardSpec, target, i, 0)) {
                ret.push_back(i);   
            }
        }
        return ret;
    }
    int check(vector<int> arr, int target, int val, int count) {
        if (count == arr.size()) return 0;
        if (val == target) return 1;
        return check(arr, target, arr[val], count+1);
    }
};

I guess Java gives stack traces and StringTokenizer, C++ is bound to have some advantages.

While this is clear, clean and elegant, in competition, I went and used a breadth-first search, and took a week longer than everyone else.

Problems:

1. Daft algorithm choice :)
2. When checking for loops, looping a maximum of val times.
3. Not checking for loops at all.
4. Not considering that a sequence starting at target obviously contains target. (This was catchable from the examples)

1000 (LineDraw):

Given the data on a series of up to 25 points, calculate the least number of points which are not on two straight lines.

To me, this seems to cry out for a brute force solution. In particular, the fact that the problem size is 25 rather than the traditional 50 is a dead give-away. (For the newer coders, the number 50 has some poorly-understood mystical significance to the initiates of the Topcoder problem-writers' guild.)

So simple loops are your friend:

    for (int i = 0; i < xs.length; i++)
      for (int j = i+1; j < xs.length; j++)
        for (int k = 0; k < xs.length; k++)
          for (int l = k+1; l < xs.length; l++) {
              // Check lines in here...
          }

The more difficult element of a solution is the reliable check whether a point is on a line. My solution (not debugged in time) used a Line class with isHorizontal and isVertical fields to avoid divide by zero. Beyond that, the slope in maintained as delta_y and delta_x.

Then

   slope1 == slope2  
=> delta_y1 / delta_x1 == delta_y2 / delta_x2
=> delta_y1 * delta_x2 == delta_y2 * delta_x1

As Zorba points out, a range of -20,000 < x, y < 20,000 means that there isn't even a need to take a gcd.

Problems:

1. I saw an O(n^8) problem which fell to a challenge.
2. Looping using the following code:

       for (int i = 0; i < xs.length; i++)
         for (int j = 1; j < xs.length; j++)
           for (int k = 2; k < xs.length; k++)
             for (int l = 3; l < xs.length; l++) {
                 // ...
             }
        return min;
      }
   

   This actually has a couple of problems. It revisits the same points repeatedly once all counter are greater than 3. If the input size is 6, It fails when points { 1, 2 } are colinear, and (say) {0, 3, 4, 5} are colinear.
3. Floating point math caught a few. Remember, AVOID!