Блог пользователя SA01Fan

What to do when one gets wrong answer for a hard problem for a long period of time?
Автор SA01Fan, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

stress testing ?

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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://codeforces.com/blog/entry/15547.

→ Ответить