June 12, 2002 Lessons Learned the Hard Way June 14, 2002 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 DivisionII 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 DivII. 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.length1]; for (int i = data.length1; i >= 0; i++) { if (c != data[i]) { sb.append(data[i]); } } return sb.toString(); Problems:
StringBuffer sb1 = new StringBuffer(); StringBuffer sb2 = new StringBuffer(); sb1.append(input): sb2 = sb1.reverse();is likely to cause problems. (Of course, this should have been caught by testing.) 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. 500 (JumpGame):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 breadthfirst search, and took a week longer than everyone else. Problems:
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 giveaway. (For the newer coders, the number 50 has some poorlyunderstood mystical significance to the initiates of the Topcoder problemwriters' 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_x1So all the nasty floating point maths related to slope can be avoided, provided there is no overflow. 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:

