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

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

Yesterday, I was stress testing the solution of problem E of some random participants from recent Div 3, with my solution but i couldn't hack them. After a few hours, two solutions which i stress tested got hacked but my stress testing couldn't catch where their solution was failing.
So, how do people find such a test cases to hack other's solution? Any suggestions are appreciated. Thank you.

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

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

Well. It depends on how you stressed tested those solutions of course.

Finding a counterexample depends on what you want to pinpoint (i.e. a WA or TLE or maybe a RTE).

If you want to cause TLE, perhaps you would like to analyze the time complexity of their code or even target the data structures that they are using (like unordered map).

If you want to cause WA, you would want to find flaws in their logic rather than simply throwing random cases. For example, off by one bugs, special cases, etc.

TLDR: The number of conditions that can be exercised in a typical program code on Codeforces is at least exponential. You won't get far if all you rely on is blind fuzzing.

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

I think they try proving the correctness of the target solution. Proving correctness != running it on random tests. If the proof fails somewhere, they can then proceed to hack the solution. After 1-3 hacks, they find some cases that majority of low ranked coders are overlooking.

Stress Testing might help with TLE, but if you carefully read the target solution, you can estimate its time complexity and try to generate a case that will lead the solution towards its worst case time complexity.

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

How random are your generated random numbers are?

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