LCJLY's blog

Help needed in slope trick technique
By LCJLY, history, 21 month(s) ago, In English

Hi everyone, I'm trying to learn a technique called the slope trick. I have read through several blogs on slope trick e.g https://codeforces.me/blog/entry/77298 and https://codeforces.me/blog/entry/47821. I went on to look at the problem "Sonya and Problem Wihtout A level". However I still couldn't understand how the slope trick work, I know that 2 slop-trickable function can be merged, but I still dunno what is the purpose of knowing that it can be merged and which point are we finding in the graph of the function. 

cin>>n;
rep(x,1,n+1) cin>>arr[x];
rep(x,1,n+1) arr[x]-=x;

multiset<int,greater<int> > B={-(int)1e3};
int ans=0;

rep(x,1,n+1){
    if (*B.begin()<arr[x]){
        B.insert(arr[x]);
    }
    else{
        B.insert(arr[x]);
        B.insert(arr[x]);
        ans+=*B.begin()-arr[x];
        B.erase(B.begin());
    }
}

I have a few questions in mind and wanted to ask regarding the above code. 1) what does the multiset store? 2) why does it have to initialize with a large negative value first 3) why do we insert arr[x] twice in the else statement 4) why do we have two cases either <arr[x] or >arr[x]

Really appreciate if you can answer some of my doubts thanks

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

»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I would recommend you to reread the two blogs and try to understand the concept again. Here are the answers to your question.

  1. The slope changing point. The function is consists of parts of lines with increasing slopes. Therefore, you can store the function just with the multiset of points

  2. You don't have to, whoever wrote this code initialize that value to prevent accessing element from empty set in the first if condition in the loop.

  3. If you know how to do the problem in $$$O(n^2)$$$ dp, you will see that you actually are adding a absolute function $$$|x-a|$$$ to the function. The slope changing point of that function is $$${a,a}$$$ according to the definition of the first blog. Since the slope changing points are addable, you add two values into the multiset.

  4. You should think about the function as a graph, and try adding two functions together, and popping the rightmost slope changing point from the multiset. You will understand the reason after that.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the help. It really answers a lot of my doubt

    → Reply