LaughingTarget's blog

By LaughingTarget, 10 years ago, In English

Hi folks, I'm a newbie to Codeforces and online judges in general, so I'm looking for help in improving. I've seen that lots of problems are solved by greedy approaches, but can you please share your insights on what gives you hints that a problem can be solved by a greedy algorithm? Also how do you satisfy yourself that the greedy algorithm you've used is correct? Thanks in advance!

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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sometimes when I can't think a dp solution (because of time limit or memory limit), I consider greedy.

»
9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

There exists a universal answer to all these "Hi! I am new, please help!" questions: RTFM!

In your case it'll be this book. If you can't afford buying it, you can always download a pirate copy.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    My copy is missing the chapter where it helps me learn from others' experience.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      You mean that you can't learn from authors' experience? I think, in this case Codeforces users' experience won't help you at all.

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        I'll take my chances, thanks.

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

          Please excuse me for rudeness in my previous comments (I mustn't behave in such a way), but it's definitely useless to ask here about the explanation of the idea behind greedy algorithms. Well, I can say something about optimal substructure, but it's explained pretty well in CLRS (in a much more detailed way than anybody will explain it here).

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            This is true but CLRS will tell you to prove your greedy algorithms and will provide a very detailed way to do so. However, in a contest environment, where the time is limited, it can be quite different. Me, for example, I consider greedy when I can't think of a DP solution that will pass the time limit, when I know the problem can be reduced to a well-known greedy one and when I have a strong intuition. That being said, I strongly encourage you to spend some time and try to prove your greedy algorithms in practice where you have plenty of time.

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

I use greedy algorithm when I can determine the optimal choice without looking at the whole input.

For example, problem C from the previous contest, 472C - Design Tutorial: Make It Nondeterministic , is a good example.

In order to determine whether a certain person uses first name or last name, you just need to care about that person's name and previous person. You don't really need to worry about anyone that comes after/before them. The optimal approach is to take "smaller" name that comes after the previous person's name.

Problems that are solved in DP usually cannot be solved like this as you need to care about other inputs. For example knapsack problem. You cannot just see one item and determine whether we should take it.

Obviously this is not the only time you can use greedy, but I find this very useful and thought I'd share.

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

When you are participating in Codeforces Round #270

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

There is no simple answer to this, as you have to solve problems and build the intuition yourself, but I'll share my thoughts.

Let's say the problem is to make n choices. If, when making the i-th choice, we know which choice is the optimal one without considering what will happen in the future (j-th choices with j > i), then the problem can be solved greedily (just taking that optimal choice).

However, in many problems you don't really know the optimal choice that way, as you need to know what choices will be made in the future to know which one is optimal right now. Dynamic programming comes to help here, which takes into account not only how good a choice is right now (for example how many points we will acquire by making this choice), but also what will happen in the future (how many points we will be able to get from the position we will find ourselves after making this choice). In contrast, greedy approaches don't care about what will happen after the current choice (what state we will move to after the choice).

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

This post is old, but I'm still writing in case it helps someone reading this.

There are two broad approaches of proving correctness of greedy.

  1. Greedy stays ahead style proof : read proof example on page 35 : https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/13/Slides13.pdf
  2. Exchange argument style proof : read page 146 of https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/14/Slides14.pdf

If you have an intuitive proof outline, go for greedy!