FluffyPotato's blog

By FluffyPotato, history, 5 years ago, In English

Hello fellow Coders

I just submitted something it got WA after about 7000 test queries were correct. The test input size is huge, so there is no way for me to debug it in a feasible amount of time. I've checked all my code for common errors: long overflow, small issues, whatever. I'm sure this has happened to many people before.... How do you recommend debugging such a case? Is there anything to look for?

Thank you

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

After you go through your code line by line to check your logic, a common suggestion is to write a brute force correct solution, and a test case generator to try and find a (hopefully small) test case that breaks your incorrect solution.

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Good qn. Here's some of my strategy:

  1. Use test case generator + brute force to find smaller test cases.
  2. Do some lemma proving on each part of the code to find cases where it could break.
  3. Remove some lines from the test case. Sometimes, just a small part of the test is enough to cause wrong answer already. But this only works if you have the test case.
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it
  1. Think about your algorithm one more time
  2. Bash small cases and try to find an edge case/counter test as hard as possible with brain and paper
  3. Check the MAXN
  4. If you couldn't find any small cases it's probably some query issue if you are using a well-known data structure (maybe segtree or lca or flow or something), check your algorithm logic and actual implementation and if it's still not working try pasting a public code or something
  5. Check the gcd/mod
  6. Check the MAXN
  7. Check indexing / off by one error in the dp
  8. int vs long long / casting long longs (actually in one problem I didn't notice that this one multiply operation was not casted to a long long and was remaining int by default and I was stuck for an hour)

The last resort is to write a generator and brute force since that will literally kill your time.

»
5 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Until recently, I would often have a really hard time debugging when I don't know the test case or when it is really large. I didn't try testing with small test cases because I thought it would be inefficient. But now I've realized that manually trying any test case that I can think of or even just small random test cases is actually more effective than I thought, with me often able to quickly find a test case which causes my solution to fail and use it to find the bug. It's definitely better than while (!codeWorks()) stareAtCode();. Of course, it's a good idea to first check for problems specific to large test cases such as overflows and array sizes.