HighHopes's blog

Generating Test Cases Cleverly
By HighHopes, history, 5 years ago, In English

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.

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

Comments Comments (4)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

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

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.

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

How random are your generated random numbers are?

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