"Worse-to-best option", a different way to think about Slope Trick

Revision en3, by gmyu.michael, 2021-06-12 22:19:44

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 thinking process is just different. 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 Kurino 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:

  1. at each step, choose the worst option first

  2. record the delta between the worse option and an improved option (or options) in a priority queue

  3. 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 replace it with the consequence of such action

The final result is your optimal solution.

At least this is much easier for me to understand. Let's go through some examples listed in 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 shares of stock in the priority queue that 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 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();
}
Tags slope trick

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English gmyu.michael 2021-06-13 06:29:44 4 Tiny change: ' [user:Kurino,2021-06-1' -> ' [user:Kuroni,2021-06-1'
en12 English gmyu.michael 2021-06-13 03:08:38 6 (published)
en11 English gmyu.michael 2021-06-13 03:06:27 447
en10 English gmyu.michael 2021-06-13 02:51:52 293
en9 English gmyu.michael 2021-06-13 02:48:33 3404
en8 English gmyu.michael 2021-06-13 02:40:32 2414
en7 English gmyu.michael 2021-06-13 02:38:30 2172
en6 English gmyu.michael 2021-06-12 22:43:08 20
en5 English gmyu.michael 2021-06-12 22:41:08 2736
en4 English gmyu.michael 2021-06-12 22:33:22 1077
en3 English gmyu.michael 2021-06-12 22:19:44 118
en2 English gmyu.michael 2021-06-12 22:14:36 2673 Tiny change: 'queue pq\n`pq.push(price);`\n' -> 'queue pq\n~~~~\n pq.push(price);\n~~~~\n'
en1 English gmyu.michael 2021-06-12 21:26:57 898 Initial revision (saved to drafts)