revivedDevil's blog

Help with Greedy
By revivedDevil, history, 6 years ago, In English

I'm unable to solve even the easiest of Greedy problems... Maybe, because I don't feel convinced until I prove my solution, but that's hard sometimes even for easy greedy problems.

Anyone who faced this problem earlier, and found a way out?

Any suggestions regarding how should I practice greedy problems, or what problems should I practice will be of much help :-)

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

»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I don't think that solving greedy problems would help much, because behind every greedy problem stays different idea and observation. I had the same problem and I also tried solving more greedy problems, but that didn't help me. The solution to this problem (for me) was to focus more on math and solve more combinatorics problems. This way you get used with the basic math techniques, which helps you develop your thinking and also helps you being able to prove the greedy observation. This is my opinion and I don't say it would help you, but for me it worked. (you can still downvote if you find it unhelpful)

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

    Ok thanks... I'm already focusing on maths, still I have a question in my head..

    Should I stick to this strategy of first prove then code, or should I try some different approach, like get some intuition, check it on some cases and code it?

    Also, are there coders with good rating, who always prove their solution? Because whoever I've met with good ratings, they just solve problems without proving their intuition (which is somehow correct most of the times)? How do they get such precise intuition then?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Depends on the contest. If you have full feedback, then it's not necessary to prove it — just submit it and see if it's correct. However if there's partial or no feedback at all, then I find the prove important, because otherwise I can't be 100% sure that my observation is correct. My personal strategy is: Firstly I observe something that possibly solves the task. I trust my intuition, so I write the code. Then I start doubting about my idea and solution. I am proving it. Then I start doubting again. So I am trying to find a hole in my prove. I can't find any mistake. Now I repeat doing the last 5 things, until the contest is over or I get tired of this shitty greedy task and continue solving the others.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm too noob to answer you, but what I think is:

Just let it go, code the very first things that comes into your mind, most of the time they will get AC and if sometimes they didn't you just learn and the accuracy will be increased. Just don't worry too much :)))

But there may be better solutions and safer ones( for your rating actually ), and I'm neither good at greedy nor any other things, I've got this advice from my expert ( I mean the exact word, not rating ) friends...

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what if nothing comes in your mind even after trting so hard

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If you are stuck (getting no new idea) for 20-30 minutes, give up on that problem for now. Try to solve it later. If fail to solve it in 2-3 tries, read the editorial.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is there any way of getting the intuition of greedy problems?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Check if it has greedy property, e.g. check if taking the max / min is surely best, Sometimes we need to try different approaches by guessing and checking if it works.

          → Reply