gautrang2474165's blog

By gautrang2474165, history, 29 minutes ago, In English

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?

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
11 minutes ago, hide # |
 
Vote: I like it +1 Vote: I do not like 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.

  • »
    »
    4 minutes ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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?