| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3892 |
| 2 | jiangly | 3797 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3588 |
| 6 | ecnerwala | 3557 |
| 7 | Ormlis | 3532 |
| 8 | Benq | 3468 |
| 9 | Radewoosh | 3463 |
| 10 | Um_nik | 3450 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 2 | Qingyu | 159 |
| 3 | -is-this-fft- | 158 |
| 3 | atcoder_official | 158 |
| 5 | Dominater069 | 155 |
| 6 | adamant | 154 |
| 7 | djm03178 | 151 |
| 8 | luogu_official | 150 |
| 9 | awoo | 148 |
| 10 | maomao90 | 145 |
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?
UPD: Thank you to all who have responded to this blog, I have read your comments carefully. Hope to be able to quickly solve it the next time I meet 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.
Thank you!
I heard from high rated coders that it is identical to slope trick. You might want to check that to gain more insights.
Slope 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.Hi, I've solved tons of problems by coming up with the dp then optimizing it. Also never solved by just saying "greedy insert into heap lul it works idk why". It's puzzling to me how people solve it by guessing a greedy solution.
Isn’t slope and Alien’s a different trick? I’m not sure if I’m correct but.
Ah, yes, I've remembered it wrong, thanks
I came up with this dp state before but couldn't optimize beyond O(n²). Didn't know about this slope trick before. Where can I find more information on the same?
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
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.
(Not sure why codeforces can't render it, now I put a link to the picture instead) picture
For $$$n = 8, k = 1$$$, the MCF graph would look like the above picture. Consider adding edges going out from source incrementally from rightmost and try to augment using it. The augmenting path would either going down -> going down to sink or going down -> going right (maybe $$$0$$$ step) -> going up to cancel some used edge.
The first case would happen only when $$$n = 7, 5, 3, 1$$$ and the second case would happen when $$$n = 2, 4, 6$$$.
For second case, only canceling the edge with maximum weight won't cause negative cycle in the residue graph thus giving the optimal solution of current flow graph.
Then you could find that, to simulate such augmenting process, we just need to use a priority queue to maintain weight of used edged going out from source.
Oh so regret greedy is an actual topic. I thought people were regretting not identifying the greedy solution that is why they called it that
You can try some practice problem on Regret Greedy, although that's a spoiler :)
https://codeforces.me/blog/entry/127492