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 ProblemsBadMazeStrategyUsed as: Division One  Level One:
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). Used as: Division One  Level Two:
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 = "*+/"; //inorder traversal modified to add helpful spaces 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(high1)+""; 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 = ab; if (OP.equals("/")) c = a/b; al.add(high1,c+""); } }Find3Cheaters Used as: Division One  Level Three:
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 3string 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); } 
