JOIN
 Match Editorial
2004 TopCoder Open
Online Round 1

September 11, 2004

Summary

What is it called when you gather the best coders in the world at a single event? If you didn't already know the answer, it's called the TopCoder Open, and we are already in the thick of it. Online Round 1 further prunes the entry list, funneling 500 competitors into 200 slots. For some, Round 1 is a chance to surprise the crowds, gain a few ratings points, and be inducted into TopCoder's elite. For others, it is purely strategic. Several reds use the round to survey their opponents, and determine which competitors will prove most troublesome in the future. tomek used Round 1 to remind everyone else who won last year. He whisked away the title in the waning seconds of the challenge round... and don't think he didn't plan it that way.

# The Problems

Used as: Division One - Level One:
 Value 250 Submission Rate 417 / 447 (93.29%) Success Rate 265 / 417 (63.55%) High Score SnapDragon for 246.01 points (3 mins 37 secs) Average Score 181.49 (for 265 correct submissions)

Unlike most traversal problems encountered on TC, this one allowed movement along diagonals. That didn't seem to bother most coders. The only added difficulty here was loop detection. Many of the solutions I saw had a large boolean matrix that marked off (row,col,direction) triplets. If such a triplet occurred again, a loop has been detected. An alternate method would be to count steps. If you end up taking more than 50*50*8 steps, you know you are in a loop (basically the pigeonhole principle applied to the previously described matrix).

This step counting method sparked a discussion between radeye and myself, that later spread to Chat Room 1, the round table, and even this write-up. The challenge was: "Build a 50 x 50 maze that requires the largest number of steps to reach the destination." Eryx and ChristopherH have some elegant solutions.

Used as: Division One - Level Two:
 Value 650 Submission Rate 258 / 447 (57.72%) Success Rate 202 / 258 (78.29%) High Score nicka81 for 612.09 points (7 mins 9 secs) Average Score 430.68 (for 202 correct submissions)

In BadParser you are given a binary tree, whose only guarantee is that an inorder traversal will produce the original expression. Unsurprisingly, the first thing done by most solutions was to inorder traverse the given tree. Once the original expression was obtained, parse it correctly to obtain the result. All worries about tree structure, overflow, and division by 0 were eliminated by the constraints. Since there were no parentheses in the expression, my parser greedily looks for the first occurrence of a '/' or a '*'. Otherwise, it settles for the first '+' or '-'. Then it applies the operation to its neighboring operands, thus simplifying the expression. This process is repeated until only a single value remains, namely the result. Java code follows:

```String ops = "*+-/";

String inorder(String[] tree, int node) {
if (ops.indexOf(tree[node].charAt(0))!=-1) {
String[] toks = tree[node].split(" ");
String ret = inorder(tree,Integer.parseInt(toks[1]));
ret += " "+toks[0]+" ";
return ret + inorder(tree,Integer.parseInt(toks[2]));
} else return tree[node];
}

//Executed after the inorder traversal
int eval(String expr) {
if (expr.indexOf(' ')==-1) return Integer.parseInt(expr);
ArrayList al = new ArrayList( Arrays.asList(expr.split(" ")) );
while (true) {
if (al.size() == 1) return Integer.parseInt(al.get(0)+"");
int high = al.indexOf("*");
if (high < 0 || (al.indexOf("/") > -1 && al.indexOf("/") < high))
high = al.indexOf("/");
if (high == -1) high = 1;
String B = al.remove(high+1)+"", OP = al.remove(high)+"", A = al.remove(high-1)+"";
int a = Integer.parseInt(A), b = Integer.parseInt(B), c = 0;
if (OP.equals("*")) c = a*b;
if (OP.equals("+")) c = a+b;
if (OP.equals("-")) c = a-b;
if (OP.equals("/")) c = a/b;
}
}
```

Find3Cheaters
Used as: Division One - Level Three:
 Value 750 Submission Rate 170 / 447 (38.03%) Success Rate 114 / 170 (67.06%) High Score SnapDragon for 735.14 points (4 mins 3 secs) Average Score 569.33 (for 114 correct submissions)

The longest common subsequence (LCS) problem occurs in nearly every undergraduate algorithms text. To depart from the norm, this problem asks for the shortest common supersequence (SCS). Had there only been 2 strings, LCS and SCS have the same solution. In the 3-string case, a new method is required to solve SCS. Given 3 strings, the recursive solution I wrote computes the result by considering what characters can possibly begin a shortest common supersequence. After choosing a character, we are left we a smaller version of the same problem. The algorithm tries all potential characters (the only characters worth trying are at the front of the input strings), and uses memoization for speed. Java code follows:

```int cache[][][];
String a, b, c;

//returns SCS for a.substring(pa),b.substring(pb),c.substring(pc)
int shortRec(int pa, int pb, int pc) {
if (cache[pa][pb][pc] != -1) return cache[pa][pb][pc];
int A = a.length(), B = b.length(), C = c.length();
if ( pa == A && pb == B && pc == C ) return 0;
int best = 1000000;
//here i = 1 means I put the first char from String a in the supersequence
//j and k denote the same things for Strings b and c respectively
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
for (int k = 0; k <=1; k++) {
if (i+j+k == 0) continue;
if (pa + i > A || pb + j > B || pc + k > C) continue;
if (i > 0 && j > 0 && a.charAt(pa) != b.charAt(pb)) continue;
if (i > 0 && k > 0 && a.charAt(pa) != c.charAt(pc)) continue;
if (k > 0 && j > 0 && c.charAt(pc) != b.charAt(pb)) continue;
best = Math.min(best,1+shortRec(pa+i,pb+j,pc+k));
} return cache[pa][pb][pc] = best;
}

public int shortest(String a, String b, String c) {
this.a = a; this.b = b; this.c = c;
cache = new int[a.length()+1][b.length()+1][c.length()+1];
for (int i = 0; i < cache.length; i++)
for (int j = 0; j < cache[i].length; j++)
for (int k = 0; k < cache[i][j].length; k++) cache[i][j][k] = -1;
return shortRec(0,0,0);
}
```

By brett1479
TopCoder Member