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

Автор ldyllic, история, 2 года назад, По-английски

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!

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

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

    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.

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

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

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

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

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

        Alright, I see the idea, thank you!

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

          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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Try Stress Testing

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

Hope this will help :)

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

    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.

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

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

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

      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