Mohsina_Shaikh's blog

When to Use Greedy
By Mohsina_Shaikh, history, 16 months ago, In English

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.

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

Comments Comments (4)
| Write comment?
»
16 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    A

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply