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.
  • Or 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

• If you have a small test case on which your program fails as well as the correct output for that test case (and you understand why that output is correct), you are expected to figure out why your program isn't working on your own.
• If you haven't found a small test case on which your program fails, try generating one (as described above).