ACM ICPC 2011 World Finals - prizes for first solution for each problem

Did you know that they gave $1500 to the team with the first accepted solution, and $1050 for every other team that solved one of the problems before others in the ACM ICPC 2011 World Finals? You can find all teams that got these prizes at the bottom of the Official Results.

People who went to the World Finals awards ceremony obviously do, but I think this hasn't been mentioned online. What do you think - does this make sense?

Binary search and eps in comparisons

The usual wisdom about floating-point comparisons inside binary search is to make comparisons exact, to avoid losing precision (as opposed to comparison using some error tolerance denoted as eps). For example this:

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > 0) right = middle; else left = middle;
}

is preferable to

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > eps) right = middle; else left = middle;
}

when f is a monotonically increasing function, because even with small eps, there's a danger that the corresponding error in the binary search parameter will be much bigger. On the other hand, even if our comparison is incorrect for equal values due to rounding errors, the binary search will still converge correctly since equal values may only appear in one point and everything will be correct in points very close to it.

But all above is true only if f is monotonically increasing! If it is just non-decreasing, and has a plateau, going without eps gets you hugely incorrect results. This bit me today in the hard problem of SRM 508: my failed solution that passes after adding error tolerance to the last comparison in enough() (TopCoder login required).

I guess the lesson is that when trying to be too clever (instead if adding eps to all comparisons), one needs to be extra careful :-)