Not_Hadid_007's blog

How Do You Recognize a Greedy Problem During a Contest?
By Not_Hadid_007, history, 38 hours ago, In English

What clues do you usually look for when identifying a Greedy problem during a contest? Are there any common patterns, constraints, or characteristics that help you recognize one? I'd love to hear your approaches and experiences!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
38 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Look for problems where the best local choice leads to the global optimum. Always verify that the greedy choice is valid.

→ Reply
  • »
    »
    38 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    But what techniques do you personally use to verify that a local optimal choice will actually lead to a global optimum? Do you rely on mathematical proofs, testing, or both?"

    → Reply
    • »
      »
      »
      38 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I usually combine two approaches: First, I try to prove that swapping any optimal solution with my greedy choice won’t worsen it. Second, in contests, I code a brute-force DP/backtracking for small n and compare outputs against my greedy solution on random tests. Last, If I can’t find a counterexample, I will submit the code. Actually, it’s enough to practice more greedy algorithm problems to get the hang of it; that’s what I did.

      I am a middle school student from China; my English is not very good, please understand.

      → Reply
      • »
        »
        »
        »
        37 hours ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        That's a solid approach! Comparing greedy with brute force is a great way to catch mistakes. And I agree, consistent practice makes a huge difference. Thanks for sharing!

        → Reply
      • »
        »
        »
        »
        37 hours ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        Your English is probably better than mine and im a hs student from America

        → Reply
    • »
      »
      »
      37 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I try to prove that choosing differently cannot produce a better result, rather than relying only on testing.

      → Reply
»
36 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Maybe it's intuition. In fact, a lot of beginner problems are greedy. The more you practice, the more intuition you get when facing harder problems, and you can often tell they're greedy just by checking, without needing to use DP.

→ Reply
»
36 hours ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

If the problem requires a linear time solution (you can know that from the constraints) I think of the most stupid way to solve the problem and then try to improve it using some observations, if those observation lead to a greedy solution I try to disprove it with some counter example rather than proving it.

→ Reply
  • »
    »
    35 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Interesting approach! I like the idea of actively trying to disprove a greedy solution with counterexamples rather than blindly trusting it.

    → Reply