SYCu's blog

How can I identify if a problem can be solved using regret greedy(greedy with heap)?
By SYCu, history, 22 hours ago, In English

In today's competition, I only realized in the last minute that problem D could be solved using regret greedy rather than DS with DP. How should I train to quickly recognize when a problem can be solved using regret greedy?

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

»
22 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

This is the first time I have ever heard "regret greedy". Although a newbie, I have solved about 10 problems of this sort which can be solved with regret greedy. The way I first thought about problem D was like "ok, we have plates with different deliciousness. We want to maximize deliciousness. I am constrained by time n. If I take a plate, it costs me k units of time. But each plate costs me the same amount of time. Plates that cost me the same amount of time with different deliciousness, there must be a greedy idea then. Let's say, I want to take the current plate, but I have already taken a less delicious plate. If the remaining time allows, I will take the current plate, otherwise, why not drop the less delicious plate I have already taken? This allows me to take the current plate, which is more delicious, maximizing the total deliciousness. Okay, if I drop an already-taken plate, what would I do instead of taking it? Well, I either ate a sushi or did nothing instead of taking that plate." At this point, I was distracted from the main idea and I could not solve it. I also thought about the knapsack DP type approach but quickly abandoned the idea. So what convinced me of a greedy approach was the fact that plates cost the amount of time.

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

    Thank you!

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

I heard from high rated coders that it is identical to slope trick. You might want to check that to gain more insights.

→ Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Slope trick (or "alien trick") is usually used to optimize a DP formula with a convex dimension. In many situations slope trick optimized DP and regret greedy would lead to the same solution. However in my opinion, in typical regret greedy problems like 2085D, regret greedy/MCMF is definitely a more natural and intuitional way to come up with the solution.

    For example, 2085D has an alternate DP solution: Denote dp[i][j] as the maximum possible deliciousness from plates $$$[i,n]$$$ if you select $$$j$$$ plates in them. Notice that $$$f(x)=dp[i][x]$$$ is a convex function, so we can optimize it with slope trick. However I doubt someone would come up with this DP without noticing that the problem can be solved with regret greedy.

    → Reply
»
5 hours ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I think it's more natural (and maybe more general) to reduce it to a min cost flow problem then try to simulate it using the property of the flow graph without actually running the MCMF algorithm, which would be too slow.

A few problems that can be solved in this way:

https://www.acmicpc.net/problem/17169

https://www.acmicpc.net/problem/14001

https://atcoder.jp/contests/abc363/tasks/abc363_g

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

    Can you explain how to identify the property in the flow graph that helps to simulate it with greedy approach with heap. Example with 2085D would help.

    → Reply