Tuesday, January 11, 2011

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.

6 comments:

  1. Here's a very simple problem that you may like because it is easy to make careless bugs when solving it.

    Given a sequence A of floats. Read each element only once and output only those elements that make up maximal possible product. Use O(1) memory.

    Examples:
    A={-10, -0.5, 0.1, 5} output {-10, -0.5, 5}
    A={1,0,2} output either {2} or {1,2}
    A={-1} output {-1}

    ReplyDelete
  2. how did you embedded your syntax highlighted code there in your post?

    ReplyDelete
  3. why do you implements Runnable for the main class ? it is not required to do that ? What's its advantage ?

    ReplyDelete
  4. There's no advantage :) In old versions of Java and/or with old judging systems, I believe the stack for the main thread was too low, so one had to create a new Thread to use lots of stack and avoid stack overflow in recursive solutions.

    ReplyDelete
  5. I don't know if this is a solution for your problem, but I think that the source of the problems is psychological one.
    So one hint is to use the same pattern for all comparisons.
    For example always write aa and a<=b not b>=a.
    Then you can just always put on that your left part is lesser than right.
    Of course another side is that sometimes it probably breaks the beauty of particular expressions.

    ReplyDelete
  6. I don't know if this is a solution for your problem, but I think that the source of the problems is psychological one.
    So one hint is to use the same pattern for all comparisons.
    For example always write aa and a<=b not b>=a.
    Then you can just always put on that your left part is lesser than right.
    Of course another side is that sometimes it probably breaks the beauty of particular expressions.

    ReplyDelete