ldyllic's blog

How to figure out failing test cases?
By ldyllic, history, 3 years ago, In English

Hey, CodeForces!

I am seeking for your advice: how to improve my skills of figuring out test cases where my program fails? I have been facing quite a few WA on 100+, 300+ test cases and each of the times I wasn't able to get what was that edge case by myself. Hence, I am asking you guys for an advice :)

And in particular — what is the edge case here?

This is my submission: https://mirror.codeforces.com/contest/264/submission/159610034

This is the problem: https://mirror.codeforces.com/contest/264/problem/B

Thank you all for your help!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you don't know what's wrong, try to generate some random tests. This usually helps, because on a big amount of data it's easy to find what's wrong.

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

    Yeah, but for example if you take a look at 14th and 15th test cases they are almost identical, so I am not sure what is failing there.

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

    Would you mind to spend some of your time and show me a thinking process on my example? Will be very appreciated..

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

      Ok, you set $$$dp[i]=dp[i+1]$$$ for default. Ok, but that means that a sequance starting from $$$dp[i]$$$ may not have first element as $$$v[i]$$$. And when you try to create a sequence with first two elements set to $$$v[i]$$$ and $$$v[j]$$$, you check if $$$gcd(v[i],v[j]) > 1$$$ but v[j] may not be present in the sequence under $$$dp[j]$$$

      Let's count $$$dp[i]$$$. You search for a $$$j$$$ that $$$gcd(v[i],v[j]) > 1$$$, and if you find it, you stop the search. So, you are trying to create only one sequence which starts with $$$v[i]$$$ and has the second element $$$v[j]$$$. But you lose all the sequences which start with $$$v[i]$$$ and have second element $$$v[k]$$$ where $$$j<k$$$ and $$$gcd(v[i],v[k]) > 1$$$.

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

        Alright, I see the idea, thank you!

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

          Great. Btw, if you can't figure out what's wrong, you can try to simulate the tests. Generate them with random values, run your program on them, and write a checker, and you have a big chance to find what's wrong.

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

Try Stress Testing

generate random test cases and check your code with Accepted Submission or with brute force

Hope this will help :)

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

    What does it mean "check my code with accepted submission"?

    I've also heard of some stress testing site, but I guess I have to pay to use it.

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

      I have found a video explaining your words, swarup_312, thanks

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

      In simple programming language , just create two method In one method put accepted code or brute force and In second method put your code and generate random test cases and run your program and then stop your code when two methods give different ans

      → Reply