Codeforces Beta Round 50: how to avoid stupid bugs?

Today I've solved another Codeforces round, with very disappointing results. That was even more disappointing given the fact that the problems were very nice (and they are always both in Russian and English there - no excuse for you not to participate in the next round on Friday :)), and I was able to see the solutions quickly.

Two of my five solutions failed. The first one, for problem B, had this bug (here's a link to full solution):

036	if (bx < 0 || bx * by > hblock * wblock || (bx * by == hblock * wblock && bx < hblock)) {

037	bx = hblock;

038	by = wblock;

039

}

Line 36 must have "bx > hblock" instead of "bx < hblock": this is an implementation of the tie-breaker which asks us for minimal value, not maximal value.

The second one, for problem E, had this bug (here's a link to full solution):

067	double rc = Math.min(ra + Math.PI / 2, rb);

...

...

070	if (rc > rb + EPS) {

071

++b;

072

} else {

073

++a;

074

}

The condition in line 70 must be "rc > rb - EPS" or "ra + Math.PI / 2 > rb + EPS" instead of "rc > rb + EPS". This code iterates over two sets of segments, and needs to advance one of the pointers based on which segment ends first. I've even had the correct condition with "- EPS" in the beginning, but has found that this would shift pointer b in case of a tie. For some reason, I've decided that it's better to shift a instead to be on the safe side (now I realize it doesn't matter) - but changed the code in such a way that it will always shift pointer a!

What do you think is the best way to find such bugs during the contest or to not make them in the first place? I used to do the latter automatically, it looks like I need to improve in this area.

SnarkNews winter series - 2011

I'd like to share another screencast: round 1 of SnarkNews winter series - 2011. Here's Torrent (preferable), Direct AVI. The rules of this contest are quite different from TopCoder and one needs to submit ACM-style programs through a web interface instead of using the TopCoder arena.

What is this series? You can find the rules at the "rules of the series" link above. Overall, this is (at least) 13th series of 5-6 contests, each presenting 5-6 problems for 1 hour 20 minutes (usually), with the timeframe to start each contest about a week. The problems are usually not new but are chosen to be unknown to most Russian competitors. The problem statements are often in Russian, so participation is usually limited to Russian speakers. However, if you want to practice your Russian skills, feel free to register and participate as described on the rules page. You've missed Round 1, but the remaining four rounds are still up for grabs.

The problems were on the difficult side of what usually happens in such contests this time, so the remaining four rounds should be easier on average :)

Screencasts: 2010

As requested, here's an attempt at a richer screencast for SRM 491 - this one also has a side-cam view at myself and my table. I'm afraid it doesn't make the screencast much more interesting, but probably it becomes a bit more funny, and the psychological experiment of working while knowingly being recorded was definitely interesting. Feels a bit like creating the big event atmosphere at home :) Since the file turned out to be 3.2G, the only feasible way to distribute it seems to be via: Torrent.

The highlight of that SRM was the failing min-cost-max-flow solution for the hard problem, which was even one of the intended solutions by the judges. Luckily, there was another greedy solution that worked much more quickly. I went this road, but in the opposite direction: my first solution was greedy, then I wrote a stress test against a stupid solution and found it didn't work, couldn't figure out how to fix it and then came up with the min-cost-max-flow solution which I've resubmitted and which failed systest due to timeout. After the match, the logical question was: why did I choose writing min-cost-max-flow instead of fixing the greedy solution? I think that the answer is that programming contests teach us to look for a 'beautifully fitting' solution. When I saw the reduction to min-cost-max-flow, it looked like something the author of the problem had in mind, and I gave it no second thought.

Here are other screencasts of 2010, just for the record.
SRM 461: Torrent
SRM 476: Torrent
SRM 480: Torrent
SRM 485: Torrent
SRM 486: Torrent

TCO 2010 Finals Hard

With no better idea of spending some time on the Las Vegas - New York plane, I've decided to try coding the hard problem from the TCO 2010 finals (statement linked). This took me 26 minutes and I got 618 points in the practice room — knowing the solution in advance and using IDEA instead of a simple text editor (rng_58's time in the finals was 48 minutes, for 463 points).

I hope the code with the below explanations can serve as a semi-editorial while we're waiting for the official editorial.