During contests or upsolving, I keep running into the same issue: as soon as I spot a greedy or DP transition that looks somewhat plausible, I immediately start implementing it without properly verifying the logic. Most of the time, I either get stuck mid-way because the states become too messy, or I submit and get hit with WA on some basic edge cases I completely overlooked. Even worse, sometimes I misjudge the constraints and only realize after writing 100 lines that my complexity won't pass the time limit. Lately, I've been trying to break this habit by writing a quick brute force to stress-test small cases or double-checking the invariants on paper before touching my IDE.
What are some clear signs or "red flags" that tell you an approach is a dead end before you spend too much time implementing it?









Biggest red flag is that your approach relies on a guess or assumption that isn't intuitively correct and you have not proven. Maybe you can cut a few corners for classic problems such as top-to-bottom greedy instead of knapsack DP or ternary searching if it intuitively checks out. Try a few cases on paper before implementing.
Got it. So the trap is confusing 'looks right' with 'actually proven.' When you're under time pressure in a contest, how do you decide when an intuitive shortcut like greedy is safe enough to trust versus when you have to stop and prove it?
I'd say there's a few levels of correctness to a statement:
If you struggle with getting WAs I would only go with 1 and 2. As you get better you can probably expand to 3 in some cases. If you have a 3 that solves the problem, and you can't prove it, then try a bunch of cases. Maybe the cases can even help you prove it.
That 5 levels framework makes total sense. Speaking of testing case, during contests, do you regularly write stress tests (brute force + random generator) to verify your solutions, or only for level 3 ideas? I find it super effective but time — consuming, so if you do, how do you set it up quickly?
I would only write a brute force for certain types of constructive problems or if you get WA and can’t figure out why for quite a while. But if it’s super simple to write a brute force then go for it, and there are a few stress testing websites that you can use in open internet contests like CF or you can write your own.
Got it, that clears up the speed-vs-certainty tradeoff completely. Really appreciate you taking the time to share all this!