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

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

During a contest, wasting 40 minutes on a broken idea hurts way more than skipping a problem. These are the 3 red flags that usually tell me to drop an approach: (-) Endless casework: Every edge case you find needs a new patch instead of fitting one clean rule. (-) Forcing a data structure: You picked Segment Tree / Binary Search early, and now you're inventing ugly hacks just to make transitions work. (-) Can't explain why in one sentence: If your greedy/DP idea sounds like "maybe sort by X and hope it works" without a clear invariant, you're guessing.

When any of these happen, I test n <= 5 by hand or flip the problem (work backwards from the final state).

What's your biggest red flag that an approach won't work?

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

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

If I find myself writing more than 100 lines for a Div2 C, I stop immediately

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

When I have to prove my greedy by saying 'trust me bro' to myself

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

if you cannot reduce your shi to a mathematical formula or two 90% of the time; your shi failing

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

    a refined version of the ^ comment:

    /* If you cannot express what your approach is doing mathematically, you probably don't understand the approach well enough to know whether it will work.
    
    Suppose you have a greedy approach:
    
    You should be able to establish an exchange argument explaining why choosing the locally optimal option preserves global optimality
    
    For DP:
    
    You should understand what every state means, why the transition is valid and why it covers all possibilities
    
    For Binary search:
    
    You should be able to define a predicate or the reverse monotonicity
    
    For graph algorithms:
    
    You should be able to articulate the invariant that makes the algorithm correct.
    
    ==============================================
    The underlying principle is that you should be able to explain the algorithm independently of its implementation.
    
  • »
    »
    3 часа назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    The remaining 10% is Div2 C constructive problems where the intended solution is 150 lines of pure pain