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

Автор Not_Hadid_007, история, 2 недели назад, По-английски

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!

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

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

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

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

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.

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

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.