I have solved nearly 51 greedy problems. But I felt helpless
in solving greedy problem though. Likewise in today's Educational round, there were B, C, D problems which were greedy type.
What should be your tips if I want to increase my greedy problem-solving skill?
I know these questions may be sound weird to some of you and this post will be downvoted. Yet I am eagerly want to know the way of doing better in greedy and constructive algorithm problems or how you guys recovered this weakness from strength.
Anyway I am new at CP and I am learning, I will take any instruction positively.
B, C, D are greedy? We must have very different definitions of greedy then. I'd say B is DP (idk about any other solution) and C is brute force. I didn't solve D this contest.
Nevertheless, I think the best way to improve greedy is to solve some problems and develop intuition. The more problems you solve, the more types of problems you'll know and the higher the probability of identifying the solution to a problem during a contest. Good luck and keep on practicing :)
Yea true I think he has confused Ad-Hoc with greedy as B,C and D were Ad-Hoc problems.
So you recommend solving more and more problems of greedy tag from codeforces? But the problem I am facing, I can understand the problem but can't get an efficient way to reach the solution, I spend about 5-6 hours on a problem which I can't solve and it helps me a lot but for greedy it seems to me that every problem approach is of different type. I am confused here.Give me suggestion.
A greedy problem is one where locally optimal decisions lead to globally optimal decisions. Basically, you want to be as "greedy" as possible. An example problem would be the following:
You are given n boxes and you need to carry k of them. Carrying one box takes $$$E_i$$$ energy. What is the minimal amount of energy needed to carry k of them?
Obviously, we can just do an 1D sort and take the k boxes that cost the least. This is a greedy problem
An Ad Hoc problem is basically one where you have to make some clever observations which will then lead to an easier problem. This causes it to have many different shapes and forms. Usually, if you can't classify a problem into a standard Data Structure/Algorithm, it'll probably be an Ad Hoc one. Ad hoc problems are hard to make up right off the bat but since this is probably the one problem CodeForces isn't lacking of, I'll leave it to you to give an example.
And now practicing. To be fair, CodeForces tags aren't the best. Most problems tagged with greedy but aren't classical greedy. They usually only use it in part of the solution or there's a greedy solution that's rather obscure. Rather than solving by CodeForces tags, I'd recommend you to find another problems list if you simply want to improve you greedy skill.
And as to not being able to even get a mere idea to the solution for any problem, I think you're solving problems too hard for you. You can also add a rating range when finding problems in the problemset (1000-1300 may be a good range for you), this will give you easier problems and you'll get comfortable solving them.
Finally, about the different types of problems. Obviously, there are going to be a lot of different Ad Hoc problems. Don't expect all the problems to be similar and have similar solutions. The huge variety in the problems is also why you should to practice and solve more, the more you solve, the better you get and the more problem types you know.
This site has approx 2000 problems on greedy do you think doing 51 greedy problems will make you master in greedy algorithms.
I never said I will become master by solving 51 greedy problems.It seems that you haven't take part in any contest or you are faired with your real identity. Anyway What I intend to say is How to build Intuition ability on solving greedy problems.
Following your logic, if there is a site with $$$10^6$$$ greedy problems, solving $$$25500$$$ greedy problems won't make you master greedy.