Hello!
I am struggling horribly hard with greedy algorithms to the point where I am not able to solve 90% of medium+ greedy problems.
I have watched many videos/lectures but its something very difficult for me.
do you have some resources you can share? How do you come up with greedy strategy and also how in the world do you convince yourself that this strategy will indeed work?
Thank you all
It is perfect if you have formal proof for your greedy strategy. But you don't always have the tools/time to a formal proof. An alternative way is to generate small cases and work out the answers by hand and observe a pattern before deciding to use greedy. Just pray that it will work. If it doesn't, then you might want to try another strategy.
Ah I see.
So basically what you are saying is, for problems involving Greedy the best (without proof and during contest) I can do is guess a strategy using test cases and pray that it works?
How exactly do guess the strategy? Is it just trying to draw patterns from examples? Any concrete techniques for that?
If you are really unsure of your greedy strategy, I have a solution for a special case. Let's say that the problem that you are trying to solve using greedy enables you to generate pretty large test cases for brute force. You could use write a less efficient (but surely correct) brute force to give you more confidence of your greedy algorithm.
this takes a very long time and I would not recommend it
Can you give your recommendation? You seem experienced, any advice is appreciated!
I mostly try to check my greedy several times by hand on small cases and edge cases. Then I submit and hope for luck to be with me.
Thanks! And what is your technique to come up with greedy strategy?
I am working on this: My blog post
For this one for example I can't come up with a greedy strategy.
How do you think of one for arrays like this for example?
Greedy is not my strong suit. My first instinct for that problem is to match the largest A value with the largest solvable B, and proceed like that, then the second largest A value with the second largest solvable B, and so on.
That depends on the problem. Brute force usually isn't hard to write. Especially if you use python.
How long does it take to write a brute force and a test case generator and compare files? 10 minutes? I'm much more comfortable with using that time to recheck the algorithm rather than relying on a randomized brute, which probably misses like 95% of edge cases.
Also, brute won't tell you if your implementation or algorithm is wrong. If you examine cases, you can easily find if it's the algorithm's problem or your code.
I know this might not be too helpful, but what works for me is that when I face most greedy problems I have seen similar ones before. I don't like guessing, but when you have seen lots of proofs and when certain things work and when they don't it's pretty easy to sketch the proof during the contest. If you, as me, doesn't want to go in the "pray it works" direction, I would recommend just doing lots of problems, seeing lots of editorials, and proving out of contest when possible why what you did worked or didn't. Soon almost every problem will be a variation of one you know works, and then you can just code it ;)
Thanks for such a response! I was wondering how many problems should one target for greedy, before most of the variations are covered? I had a look at the number of problems you have solved out of curiosity, but I am not sure if that would be only number of problems you would have solved :p