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

When to Use Greedy
Автор Mohsina_Shaikh, история, 17 месяцев назад, По-английски

Hello, Can anyone please help me to understand why Greedy works for the above problem Painting Eggs I have read the editorial and not able to fully understand how greedy is the correct solution for the problem.

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

»
17 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

I am not sure why there are downvotes.Is there anything wrong with the post or I am not allowed to ask doubts.As I have no peers to discuss and resolve doubts I don't know how to resolve it.Im trying hard these days to not leave CP and hang in there.I feel like I'm not improving at all even after 3 years in CP.If you know the answer and feel like answering it please answer else please ignore instead of downvoting.

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    A

    → Ответить
  • »
    »
    17 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    First of all, who cares about all the downvotes.

    Now why greedy works. Think about the worst case scenario. Current difference is exactly A-G = 500. If we were to add 1 to A, then we would reach 501 which is unacceptable.

    Instead we add 999 to G. Which makes the difference G-A = 499.

    This should give you some intuition on why greedy works as after every move we can maintain an absolute difference of at most 500.

    → Ответить
  • »
    »
    17 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I personally haven't voted this blog post but IMHO, one of the reason for downvote could be that you could have posted it in the comment section of the editorial instead of writing your own blog post. There is nothing wrong writing your own blog post. But it would be much easier for others to find out the answer if they are struggling like you.

    → Ответить