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)) { |
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); |
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.
Here's a very simple problem that you may like because it is easy to make careless bugs when solving it.
ReplyDeleteGiven 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}
how did you embedded your syntax highlighted code there in your post?
ReplyDeletewhy do you implements Runnable for the main class ? it is not required to do that ? What's its advantage ?
ReplyDeleteThere'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.
ReplyDeleteI don't know if this is a solution for your problem, but I think that the source of the problems is psychological one.
ReplyDeleteSo 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.
I don't know if this is a solution for your problem, but I think that the source of the problems is psychological one.
ReplyDeleteSo 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.