DonnieDarko's blog

guessing greedy solutions
By DonnieDarko, history, 5 years ago, In English

To guess the solution for a greedy problem, brings some benefit? I want to improve my greedy skills, and i'm doing problems, but a lot of the problem that I've solved I only guess the greedy idea, If I get WA, I guess again... It that help? Or are there better ways to improve greedy that only doing problems?

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

»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Yes, you should change the sensitivity of your mouse and your screen resolution.

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

Randomly guessing a greedy strategy and submiting without thinking about it is a very bad strategy — if you get a WA you won't know whether you made a mistake in implementation or the greedy is wrong.

Usually greedy solutions come from observations. Read a problem, write down anything you can deduce about the problem in question, find a way to piece it together. Or something like that.

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

    I'd say that it varies from problem to problem and from contestant to contestant.

    I remember how, back when I was participating in ICPC, common approach on our team was roughly like this: "For this problem we can either think about the solution or implement stress-testing and then just tweak random stupid ideas till we find the right one; since thinking and proving isn't our strong side, let's just write the code".

    And then, obviously, it is usually beneficial to learn after the round why did this particular greedy works... Though simply knowing that "this kind of greedy usually works for this kind of problems" is often enough.

    Upd.: And to clarify what I mean by "it varies from problem to problem" — when you are in situation like "I can either spend 3 minutes coding trivial greedy for this problem — which will give me AC with 95% probability, or spend 30 minutes trying to prove this magic — for which I'm not even sure if the probability to succeed is as high as 95%", it doesn't always sound too bad to give it a try.

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

      Ok, that's fair. But I remember several times when random guessing has bitten me (or my team) in the arse.

      Also to be fair I think there's a big difference between "stress-testing and tweaking" and "just submitting random shit".

      → Reply