Online Round 4 March 22, 2006 Match summary Round 4 always features some of the hardest problems TopCoder has to offer, and tonight was no exception. While the easy stumped no one (literally), only 37 coders solved the medium, and only 4 solved the hard. Chief amongst them was andrewzta with a 30 point lead over Ruberik, who opted to do the hard first, though it ended up not mattering for him. Eryx and krijgertie got 3rd and 4th with failed medium submissions. The ProblemsDrawTreeUsed as: Division One  Level One:
The easy problem had nothing tricky in it, but it did require a reasonable amount of code. There are a lot of different ways to do this problem, but most of them involve a recursive function that adds strings to a global variable. The calls to the recursive function should tell how much to indent. Adding the pipes is a little bit tricky, but we can just add a loop to find the last child, and add pipes after every child but the last one. MonotoneSEMinUsed as: Division One  Level Two:
The medium problem turned out to be rather difficult. The first step
to solving it correctly is to realize the shape of the function.
Since it is only evaluated at discrete steps, those are the only
points where its value matters, and so the function ends up being
piecewise flat. That is, it looks like a staircase (albeit an uneven
one). Once we have this figured out, we can work on optimizing the
squared error. Lets think about the simple case where we have the
string "10". In this case, we'd really like to make the function go
from 1 to 0, but that wouldn't be monotically increasing. So, we have
to make the function lower for the first bit, or higher for the
second bit, or both. It turns out that the lowest squared error
occurs when we make the function 0.5 for both of them. In fact, we
can derive a more general formula: if an interval has A ones and B
zeros, and we have to assign everything in the interval the same
value, then the best value is A/(A+B). bits[1..N] for(i = 1..N) create interval [i..i] while(not monotone) find intervals [i..j], [j+1..k] that violate monotonicity merged [i..j], [j+1..k] into [i..k] return squared error of functionWhile the greedy solution above works (in O(N) when done properly), most coders opted to use some form of dynamic programming instead. They computed the best squared error for the first j bits, as well as the value of the function at the j^{th} bit. Then, using dynamic programming, then tried adding each sized interval after the first j bits, with the same value all along it, as described. See SnapDragon's solution for an example of this algorithm. TreeReconstruct Used as: Division One  Level Three:
Lets start by thinking of the simple cases of 2 or 3 nodes.
Obviously, if the subset contains 2 nodes the original tree may have
only had 2 nodes also, with the same distance between them. However,
this is not the case when there are 3 nodes. Lets call the three
nodes A, B and C, and call AB, AC, and BC the distances between them.
Now, imagine that there was some other node D in the original tree,
and that A, B, and C were all connected to it. In this case, it is
not hard to see that AB + AC = BC + 2*AD. Thus, working
backwards, we can figure out AD. If AD is 0, then there wasn't an
extra node in the original graph  A was simply between B and C.
Otherwise, AD lets us figure out BD and CD, and thus we can insert D.
In some cases, it will turn out that BD or CD is 0, in which case we
clearly don't insert a new node, since D is equal to B or C. Those
are all the possible cases. The impossible cases come from AD being
negative, or implying that BD or CD are negative. Also, since the
original weights have to be integral, if any of the weigts are
fractional, the case is invalid. public class TreeReconstruct { public int reconstruct(String[] g1, String[] g2) { HashSet r = new HashSet() ; int n = g1.length ; int[][] d = new int[n][n] ; StringBuffer sb = new StringBuffer() ; for (int i=0; i<n; i++) { sb.setLength(0) ; for (int j=0; j<n; j++) { d[i][j] = Integer.parseInt("" + g1[i].charAt(j) + g2[i].charAt(j), 16) ; sb.append(d[i][j]).append(",") ; } r.add(sb.toString()) ; } for (int a=0; a<n; a++) for (int b=a+1; b<n; b++) for (int c=b+1; c<n; c++) { int da = d[a][b] + d[a][c]  d[b][c] ; int db = d[a][b] + d[b][c]  d[a][c] ; int dc = d[a][c] + d[b][c]  d[a][b] ; if (((da  db  dc) & 0x1000001) != 0) return 1 ; sb.setLength(0) ; for (int e=0; e<n; e++) { int de = Math.max(Math.max(d[a][e]da/2, d[b][e]db/2), d[c][e]dc/2) ; int cs = 0 ; if (da/2 + de == d[a][e]) cs++ ; if (db/2 + de == d[b][e]) cs++ ; if (dc/2 + de == d[c][e]) cs++ ; if (de < 0  cs < 2) return 1 ; sb.append(de).append(",") ; } r.add(sb.toString()) ; } return r.size() ; } } 
