Background
While I was learning the "Slope Trick", I could understand the examples in the tutorial but had a hard time solving related problems by myself. Maybe my brain just works differently. Along the way, I come up with a different way to think about this algorithm (and come to almost the same code). Here I would like to share how I think about it, which I call "Worse-to-best option", inspired by the "Buy Low Sell High" problem that I'll explain below.
The Slope Trick is first explained by zscoder in this tutorial, and then further explained by Kuroni in this blog. I learned from Benq's USACO Guide here.
"Worse-to-best option"
Instead of using the exact thinking process as above, this is how I'm thinking about it:
This type of problem always gives you options to take certain actions through a series of steps, and you are supposed to find the optimal solution. My thinking process is:
at each step, choose the worst option first
record the delta between the worse option and an improved option (or options) in a priority queue
when we go through the priority queue, take the top one that reduces the worst option most. Remove it from the priority queue (since you already used it), and (this is important) replace it in the queue with the consequence of such action
The final result is your optimal solution.
At least this is much easier for me to understand. It is kind of greedy algorithm. Let's go through some examples listed on Benq's USACO Guide.
The basic "Buy Low Sell High" problem
For this problem, you are given a price of a stock for the next N days. On each day, you can buy or sell a stock, or do nothing. The question is what's the maximum profit you can make.
When we go through each day, the worse option (lowest profit) is to buy the stock at that day's price
for(int i=0; i<N; i++) {
int price; cin >> price;
profit -= price;
A better option is to do nothing, so the difference from the above worse option is to increase the profit by +price (and keep it in a priority queue pq). This is basically selling the same one share of stock we just purchased.
pq.push(price);
Do we have an even better option than that? If we already some options in the priority queue (some share we can sell) and the previous selling price is lower than today's price. Instead of selling at that price, we should sell at today's price. Bascially, we buy a share ( profit -price), sell it (profit -price + price = profit, which is the same as we have not taken any action yet today), and sell at today's price (profit -price + price + price = profit + price). Let's remove the lowest price option in the queue and replace it with the option of selling it at today's price.
/// pq is the priority queue where the min is at the top of the queue
if(!pq.empty() && pq.top() < price) {
pq.pop();
pq.push(price);
}
After we went through N days, the pq contains the best option we have (N of them). Then we can simply exercise those options and get the max profit.
for(int i = 0; i < N; i++){
profit += pq.top(); pq.pop();
}
FYI, it helps if you read the other explanations on BenQ's USACO Guide site.
Now, if you understand my thinking process above, let's try to solve some more difficult problems listed on Benq's USACO Guide.
Bookface
To read this problem, you actually need to go to the statements. Bascially, this is almost the same as Increase Array problem, except that the difference of 2 adjacent elements can be different no less than d (a constant).
We can easily "translate" this into an increasing array problem. If you think about an array of 0, d, 2d, 3d, ...., that's a basic array satisfying the requirement. So, for the array c[i] in this problem, we sort the array and then do a transformation of x[i] = c[i] — i * d, then we are simply asked to solve an increasing array problem on x[i].
So, use our "Worse-to-best option" approach,
first, we keep x[i] in the priority queue
ll x = c[j] - j * d;
pq.push(x);
what's our options? if x[i] is already the biggest one, it is already an increasing array and we do not need to do anything. If x[i] is not, then we need to move at least the difference between the previous max and x[i] in order to make it an increasing array (think of it as moving x[i] to the previous max level). Now the previous max "option" is used and we pop it from the queue. What's the replacement of this action? Obviously, it is x[i]. So, it looks like this
if(!pq.empty() && x<pq.top()) {
ans += pq.top() - x;
pq.pop();
pq.push(x);
}
One more thing to take care is that the array element can not be lower than 0, so we can always insert the option of 0 into the pq to restrict it.
Here is
The CCDSAP Exam problem is very similar.
Let's look at a little bit difficult problem:
NOI2018 Safety
This problem is almost like the opposite of the above Bookface problem. You basically want to find the min cost to make the value of the adjacent element no more than H (a constant).
Maybe just me, but I was having a hard time thinking about this problem in terms of Slope Trick (the conversion between f and g confuses me <-- read the official solution.) Instead, it is much easier for me to think about this problem in terms of the "Worse-to-best option" approach I'm explaining here.
Let's define dp[i][x] is the min cost for up to stack i and stack i's height is x. Obviously, every time I go from stack i to stack i+1, in the extreme case, the range of x where dp is min can be extended to the left (smaller) by H and to the right (larger) by H.
If I look at the left-hand side of this min range, it is an increasing array from left to right. If I look at the right-hand side of this min range, it is a decreasing array from right to left. So, I can have 2 priority queue, lq and rq, to track the option for each side. When I look at a new stack, I basically consider it is in which region
ll range = (ll)i * (ll)H;
if(a + range < lq.top()) {
/// similar code for increasing array
} else if ( a - range > rq.top()) {
/// for decrease array, basically same approach as increasing array
} else {
/// in the min range, store option for each side
}
The only additional care we need to take is, for example, if it falls in the left region, it could also be an option for the right region. So, it would look like this
lq.push(a + range); /// max coverage
ans += lq.top() - (a + range); /// touch historical set by H
lq.push(a + range); /// compensate
rq.push(lq.top() - range * 2LL); /// also a possible option for right side
lq.pop();
Everything else is very similar to the increasing array problem.
My code
Farm of Monsters
This problem is another example to demonstrate the idea of choosing worse to best options.
Bascially, if I want to kill this monster, I attack and you attack, until to the condition that the remaining life MOD b is <= a, in which case I rest (or kill other places) until it reach the final stage and I do the final kill and win. If not kill this one, then I'm not going to touch this monster.
When we go through each monster, we choose the worst option (best actual in this case, regardless of whether I can do it or not) which is to kill this monster first. If it can be done, good, I killed one more. If not, then we take the previous one that we can kill, switch it to not kill. Since we pick the biggest delta between those, the extraSum is always >= 0, which means we can replace it with kill this monster. The total result is -1 +1 = 0 (i.e. no change).
My code
I'm not going to explain other problems on BenQ's USACO Guide. You can try to solve it by yourself, and I have put my code on BenQ's site.
Conclusion
I hope this helps you to understand Slope Trick in a different way. At least for me, this thinking process is easier for me.
[EOF]
Note: You mentioned Kurino instead of Kuroni
Otherwise, good blog!