How To Debug

This module is based on both of these resources. I've included the content that is most relevant to USACO.

Pre-Submit

• Don't repeat yourself!

• Your code should be consistent and readable (to yourself at the very least).

  • See style tips.
• Give variables meaningful names.
• Use plenty of print statements.

Wrong Answer

• Read the full problem statement again.

• Read your code again.

• Have you understood the problem correctly?

• Is your output format correct?

  • Did you remove debug output before submitting?

• Add some assertions, resubmit.

• Are you sure your algorithm works?

  • Go through the algorithm for a simple case / write some testcases to run your algorithm on.

• Do you handle all corner cases (such as $N=1$) / special cases?

• Any undefined behavior?

  • can result in different outputs locally vs online

  • uninitialized variables

  • not returning anything from non-void functions

  • array out of bounds

    • C++ - Can use array::at or vector::at instead of [] to throw an exception when the index is out of bounds.

  • signed integer overflow

    • USACO problems usually contain a note of the following form if the output format requires 64-bit rather than 32-bit integers, but it's easy to miss:

    Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a long long in C/C++)."

  • C++ - Compiling with additional options can help catch these.

• Confusing $N$ and $M$, $i$ and $j$, etc.?
• Shadowed or unused variables?

  • C++ - Compile with warning options (-Wall -Wshadow).
• Are you clearing all data structures between test cases?
• Any NaNs (ex. taking the square root of a negative number)?
• Write a test case generator and a (simpler) slow solution and compare the outputs

  • See stress testing.
  • You can compare against a model solution (if available).
• Use a debugger (if you're using an IDE).

  • Set breakpoints to stop your program at certain lines.
  • Step through lines one by one and watch how the values of your variables change.
  • Probably slower than well-placed print statements ...
• Rewrite your solution from the start.

  • Make a new file rather than overwriting your previous program! It's always possible that you might introduce more bugs.

Of course, many of these are also relevant for RE / TLE.

Runtime Error

• Have you tested all corner cases locally?
• Any undefined behavior? (see above)
• Any assertions that might fail?
• Any possible division by 0? (mod 0 for example)
• Any possible infinite recursion?
• Invalidated pointers or iterators?
• Are you using too much memory?

Time Limit Exceeded

• Do you have any possible infinite loops?
• What is the complexity of your algorithm?
• Avoid vector, map. (use array / unordered_map)
• Did you remove debug output before submitting (ex. are you printing a lot of information to stderr)?

Before Posting on the Forum

• Try everything above first.

  • If you've found a small counter-test, you should be able to figure out why your code isn't working on your own via print statements.
• Provide a link to the problem (and the relevant module, if applicable).
• Include what you've attempted so far.
• If you have code, post it (formatted as described here).

  • Add comments.
  • If you know which part doesn't work, mention it.