TTMMM's blog

Should we Practice Greedy?
By TTMMM, history, 4 years ago, In English

Many a times i have heard people saying there's no point in practicing Greedy questions. If you have a good day, you'll solve the question based on greedy else not. So we shall save the time and rather spend on practicing DP. Please express your viewpoint.

In contests, I am generally not able to solve 1800-rated Greedy questions. My Rating: 1630

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

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

I've seen some questions based on greedy approach, which look easy at first, but they generally use a key observation that we tend to overlook at times. So practicing them can't really hurt in my opinion.

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

"Don't practice greedy problems" must be one of the worst advice I've seen. But just saying "practice greedy problems" doesn't feel right.

Simplifying, you have 2 ways to approach greedy problems: think of something that "makes sense" and pray it gets AC or prove your greedy. What people fail is knowing how to prove greedy solutions but that's in my opinion the most important thing you should keep in mind when PRACTICING greedy problems. Note that practice is practice, competition is competition, so even if you correctly guess your greedy don't forget about that and try reading the editorial/comments talking about how to prove it after the contest. Learning proofs also helps you having that "intuition" needed to correctly guess a problem and for most easy problems (read: until around div2D) you can find the proof for the solution anyway in <= 2 minutes of thinking IF you're used to thinking about it.

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

    I feel you have written exactly what happens. Proving that our intuition is right is somewhere i lag. I'll definitely keep this in mind to read editorials in order to learn how to prove! Thanks a lot tfg

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    What people fail is knowing how to prove greedy solutions but that's in my opinion the most important thing

    tfg Where can we learn about ways to prove whether greedy works or not ?

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

      By trying to prove solutions during/after the contest, looking at editorials and talking to other participants after contest.

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

So we shall save the time and rather spend on practicing DP

I find that to be quite a stupid way to think about it. You should practice everything. If you're preparing for some specific competition and you have a deadline, then you might want to practice only questions which are more likely to come up for that competition. If you're practice to be good, there's no rush. You'll want to practice both greedy and DP just as any other technique/algorithm.

When I was starting out I used to absolutely hate greedy because I wouldn't be able to solve any of them. Even when I got to IOI level I still thought there's not much I can do about my inability to see the greedy solutions. Nowadays I know that to be false — you can improve your abilities to see greedy approaches a lot by practice.

The distinction is not clear in certain problems, but a greedy approach is not a completely ad-hoc approach. The latter you can't practice by definition.

In my opinion the reason people think that one can't improve at greedy question is that what you are training is your intuition. In competitive programming, and in any mind sport in general, intuition plays a huge role and no amount of knowledge beats it. With greedy approaches you need to more or less rely on your intuition at every step of the way. Even after coming up with the right solution you probably won't have enough time to rigorously prove it, either. Improving your intuition instead of core knowledge is more annoying because the progress is not that obvious, but it's nonetheless very important.

Summary/TL;DR: Practice everything, there's no rush. You can improve on greedy problems a lot, even if it seems like people magically come up with them (personal experience).

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

    Exactly! I just pray that i get AC in greedy problems and generally fail to Prove that why my solution was right! Thanks a lot Enchom

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

    You don't have time to rigorously prove it in a contest, but you usually have plenty of time to informally prove it (if your intuition is good enough). And taking the time to do that makes a world of difference compared to the "pray it gets AC" approach.

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

      That was exactly my point. Perhaps I didn't get it across well. Intuition is key since you will usually do only a somewhat handwavy proof.

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

You should definitely practice them. A lot of weird adhoc problems end up being based on some sort of greedy approach, so experience with various greedies will help.

→ Reply