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

Автор gautrang2474165, история, 27 часов назад, По-английски

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?

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

»
26 часов назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    26 часов назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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?

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

      I'd say there's a few levels of correctness to a statement:

      1. Proven — oftentimes you can do this in your head
      2. You can intuitively tell it's true or it follows from observations
      3. Seems right but you're not 100% sure
      4. Unsure
      5. False

      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.

      • »
        »
        »
        »
        26 часов назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        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?

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

          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.

          • »
            »
            »
            »
            »
            »
            26 часов назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            Got it, that clears up the speed-vs-certainty tradeoff completely. Really appreciate you taking the time to share all this!