Hello guys,
I'm working hard on my competetive programming skills for a couple of months, but I still find debugging problems as my main weakness. I waste huge chunk of time for looking for a bug (often much more time than for writing a code). Is there any way to improve this skill? Do you use some your techniques?
Thanks.
The easiest and, probably, most useful technique is debug output. Instead of looking for bugs try to print values of your variables in the middle of the program and check if they are correct.
For example, if you try to solve a quadratic equation, you may print the discriminant just after you found it:
So, if you are getting wrong answer on some test and you know this test, you may print out intermediate states of your program and find out the buggy step.
You can also use a debugger (I use gdb, some may prefer any visual one) to see intermediate values of variables, but it is usually slower. However, there are good ACMers who would not agree with me.
I guess we'll see discussion "debugger or debug output" here in a short time... Yes, I also prefer debug output:)
tom, i suggest that you may try some hacking practice at TopCoder or Codeforces. Pick random wrong solution and try to understand — when it fails and why.
Also you may look for some "WA-WA-AC" or "RE-RE-AC" or other symilar things among submissions of other users. When someone receives WA/RE, and after 1-2 minutes his next sumbission for this problem is getting AC — in most cases it means that first try was very close. So you may pick that code and try to fix it.
And you can naturally practice all these things while solving problems and debugging your own solutions:) I think it is just a matter of time and practice.
And if you ask about "best technique of debug" — no one knows which one is best for you. Somebody is using debugger while other prefer debug output, somebody is testing his code on a lot of different cases, while some other guys prefer carefully reading code instead. You should find best combination by yourself:)
Debugging depends on whether you have a wrong test case or not.
If you have a test that your program solves wrong, then debugging is easier than you think. You simply should start outputting most of the values during the calculations (as the example with discriminant above) and see which ones are wrong. If some value is wrong, then either other values used in its computations are wrong or the computation is wrong. If you have everything printed you can easily track the part of the code that produces wrong values and therefore fix it.
Now if you do not have a test that your program solves wrong, but you know it is wrong (from system feedback for example) it's harder. You can either start using the above method, print detailed calculations, and look for error by going through your code and checking each line, but those might turn out to be slow. In those cases I often make a test generator and checker and just run them in infinite loop so I can get a test that my solution fails on, which can often be even slower. However, whatever way you choose, it's considerably slower than having a wrong test case.
Seeing a bug by just looking at the code is extremely difficult as you've written the code, and most likely you will subconsciously feel that it's correct.
Of course there is no universal way of debugging. For example on this year's Balkan Olympiad I had a problem that gave me 0 points. At first I had a wrong test case and I fixed it. Still 0 points, however. I proceeded to look through the code, print debugs and try to find a mistake. I found a few bugs, but still 0 points. Finally I wrote a test generator and checker to find another bug, and got 100 finally. In total I spent around 3 hours and a half on that problem only.
So debugging may always turn out to be more time-consuming than you thought but if you practice a lot and are used to printing debugs to locate the error, you'll be able to remove most bugs pretty fast.
Of course, stuff like heisenbugs are always a pain in the ass! :D