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.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 11:09:41 (k2).
Desktop version, switch to mobile version.
Supported by
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.
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.
How random are your generated random numbers are?