SA01Fan's blog

What to do when one gets wrong answer for a hard problem for a long period of time?
By SA01Fan, history, 4 years ago, In English

Guys, recently when I was trying to solve some problems that were slightly difficult for me , I was getting wrong answers on test (20 and above) and those test cases are so large that codeforces system does not reveal them completely. Even though the editorial was also similar to my idea. In this case what should I do to understand my mistake? Please suggest some efficient way to debug. How to generate small test cases that are able to break my code?

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

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

Ummm okkay, so basically you want to know why your solution is incorrect. Two three things :

  • Find someone else's solution that's similar to your solution and find the differences
  • Create a testing program and generate test cases. Run them on both your program and some correct one. Wherever they fail to be the same, you got the test case where your program fails.

If you find out some other method do let me know, would be useful to me too.

Edit : This video on testing your solution by Errichto might be useful.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I also made some edge test cases and tried all my best to make my code failed....But somehow it does not. Suppose your entire solution is correct except in a line you wrote cnt = cnt + 1. But cnt can be increased if some conditions are met. Somehow you missed some of them.Then when you generate test cases you can also calculate wrong answer for them manually and they can match with your code's output..I know other can say make a bruteforce code to check whether its correct or not. But this is also time worthy and sometimes is not possible too...

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Agreed. Has happened with me too, when there's some case which is too big to decipher the issue.

      Being a lazy person, I just understood and implemented someone else's code and moved forward.

      So yes, I agree that this is a problem. I think we should collect some tutorials on debugging and test case generation, put it on a blog, so that people like us can benefit from those.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey — I've written a blog after facing the same problem again. Might be useful to you.

      → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

stress testing ?

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Any stress testing 101? I've faced the same issue as the op (I've had >50 submissions for a single problem before). I've considered stress-testing, but after googling, most of the sources were too dense for me--btw, I'm using CLion + JHelper.

For what it's worth, I think(?), getting better at finding test-cases that break code is an acquired skill. I remember when I started CP, I didn't really recognize any edge cases, but since then, it's been easier. Also worst case scenario, just do a bunch of random small test-cases to see where code fails. On Codeforces Round 712, my code didn't work, and I had no clue why, so I just did a bunch of random tiny test cases and found my error.

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Write a script to randomly generate tests and test if your output is correct (using a checker, or just compare to an Accepted submission which can be copied from Codeforces) in a loop.

Try different combinations of input sizes, don't always use the maximum value: small test cases are sometimes more likely to trigger strange bugs in the program.

If you are not convinced of the correctness of your C++, enable runtime checkings during the test. See https://mirror.codeforces.com/blog/entry/15547.

→ Reply