When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

meooow's blog

By meooow, 5 years ago, In English

The problem

Let us consider the problem where we need to quickly calculate the following over some set S of j for some value x.

Additionally, insertion of new j into S must also be efficient.
This will most likely be encountered with DP problems. For example, the recent problem 1083E - The Fair Nut and Rectangles from Round #526 has the following DP formulation after sorting the rectangles by x.

f(i) = xi·yi - ai + max1 ≤ j < i{ - xj·yi + f(j)}

The problem requires quick calculation of the above define maximum for each index i. How can this be done?

The idea

Notice the special form of mj·x + cj. This is identical to the equation of a straight line with slope mj and Y-intercept cj. So the problem is equivalent to being given a set of lines and asked for the maximum y value any of those lines can give at a particular x. If you draw a bunch of straight lines on a plane, you'll notice that the maximum values are along what appears to be a convex hull.

cht1

Some observations:

  • Every line on the hull provides the maximum value on some contiguous range of x values. Conversely, every line not on the hull is useless and never provides the maximum.
  • All the lines on the hull have different slopes. The order of slopes also determines their position on the hull. A line with lower slope appears on the hull to the left of one with a higher slope.

So, a possible strategy can be to only maintain the convex hull and not keep the useless lines .

A specific problem

Let us further consider the rectangle problem mentioned above.
For clarity, let's substitute x and y of the problem statement with p and q, and allow x and y to only refer to coordinates of the 2D plane where we consider the lines.

f(i) = pi·qi - ai + max1 ≤ j < i{ - pj·qi + f(j)}

In this problem the slope of the lines mj is given by  - pj. Due to the nature of the constraints (no rectangles are nested), after sorting rectangles by increasing p we will find they are also sorted by decreasing q.

The idea:

  1. We'll keep the lines of the hull, in sorted order of slope.
  2. We iterate over the rectangles from i = 1 to n, and pi < pj, qi > qj for i < j.
  3. When we have to get the maximum at some x = qi, all lines that provide the maximum at positions  > qi are now useless, since further maximum queries are guaranteed to occur at  < qi.
  4. When a new line is inserted, the slope of this line  - pi is guaranteed to be lesser than all lines in the hull. Therefore, this line is also guaranteed to provide the maximum in some range ( - ∞, x]. However, adding this line may make it so that some lines previously on the hull are no longer on it. These lines need to be removed to maintain the hull.

For this particular problem:

  • The lines are inserted in sorted order of slope
  • The query positions are also in sorted order

Implementing query and insert:

Query
When querying at x = qi, just compare the value at x of the rightmost line with that of the line next to it. If it is lower, remove it and repeat. When done, get the value at x of the rightmost line as the answer to the query.

cht_query

Insert
When inserting a line, if the intersection point of this line and the leftmost line lies to the right of that of the leftmost line and the line to the right of it, the leftmost line is no longer on the hull. Remove it, and repeat. Parallel lines pose an exception to this since they will never intersect, and must be handled separately if such a situation is possible in the problem.

cht_insert

And that's it... since we add lines at one end and remove at both ends, the data structure for the job is a deque.

Solution for the rectangle problem:

Complexity is if N lines are inserted and Q queries are made.

A few what ifs

What if slopes are sorted in increasing order instead?
You can modify the logic accordingly.... or you can observe that negating the slope has the effect of mirroring lines about the Y-axis, so you can use one implementation for both.

What if slopes are sorted but in reverse order of the query positions?
Both adding and removing will be done at one end, so a stack is required. Of course a deque can also do the job of a stack.

What if minimum is required instead of maximum?
Again, you can modify the logic... or you can observe that negating both slope and Y-intersect has the effect of mirroring about the X-axis. You can use the same implementation.

A more general problem

Let us consider a problem where

  • The lines are inserted in sorted order of slope
  • The query positions are in arbitrary order

To tackle this problem nothing needs to be changed for insertion. However we can no longer remove lines when answering queries. In order to answer queries, notice that each line provides the maximum in some range which is defined by its intersection point with the previous and next line. Given a particular x we can use binary search to find the line where the value will be maximum.

Solution for the rectangle problem using this method:

Complexity is .

The original problem

Coming back to the general version,

  • The lines are inserted in arbitrary order of slope
  • The query positions are in arbitrary order

This is referred to as the "fully dynamic" version of CHT. A convenient way to implement this is using a sorted set, such as std::set in C++ or TreeSet in Java. The idea is to maintain the set sorted by slope. To query, binary search is used as before. To insert, the position at which the line should be inserted is located. If this line does not appear on the hull, it is not inserted. If it does, useless lines are removed from both the left and right of the inserted line. The complexity using this method is .

You can find a neat implementation here (thanks to Chilli for the link). A couple more can be found here and here. I do not want to go into further details about this method, because I personally find using Li Chao tree much simpler if the fully dynamic version is required. Li Chao tree is a specialized segment tree that also deals with the convex hull trick, and there exists a nice tutorial for it on cp-algorithms. This page also contains an alternate interpretation of CHT.

Conclusion

Although this tutorial focuses on the technique of CHT, it is worth mentioning that in contests CHT will almost always be intended as a way to optimize DP. You can refer to link titled "Dynamic Programming Optimizations" below to check out the forms of DP recurrences that can be optimized this way.

Note about precision: You may have noticed that the function intersectX in the code uses long double to find the coordinate. Is this good enough? Since queries are (usually) at integer x, the lines which provide the maximum in a range completely contained in interval between two consecutive integers are useless since they never provide a maximum at any integer coordinate. So we actually do not even need long double, floor/ceil division will do just fine. Thanks to tmwilliamlin168 for pointing this out to me. Note that integer division is not the same as floor division in C++ for negative numbers.

Useful links
Problems

Ordered approximately by difficulty:

That concludes my first tutorial on Codeforces. Thanks for reading and I hope it was useful. Any suggestions or improvements are welcome.
The nice images above were made with Desmos.
If you want other links/problems on CHT to be added, comment below and I will add them.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Great tutorial! Another good resource for those who prefer to learn from videos is Algorithms Live — Convex Hull Optimization.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    I've added the link. One thing that irked me, in the first part the author says that (x - y)2 + prevCost is not really CHT because the functions are parabolic and not straight lines, but the expression can be expanded to y2 - 2xy + x2 + prevCost which needs to be minimized for fixed y over some x, so it actually can be solved in the normal way with a convex hull of lines.

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think PDELIV deserves a mention in the problem list. It requires you to use it in a way I personally hadn't considered before.

»
5 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

I like the implementation created by simonlindholm, found in the KTH notebook. I originally saw ksun48 use it here: https://codeforces.com/contest/1083/submission/46863810.

You can find it in here:https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h

I think it's a lot less magic than the other 2 implementations linked (no mutable member functions/closures), and I believe it's also substantially faster.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    This implementation appears short and neat. Added to the blog. Have you also compared the performance?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      The primary thing that differentiates this implementation is that it stores the intersection point during insertion. This makes the implementation a lot shorter as well as the queries somewhat faster. Overall, compared to the other 2 implementations linked (called HullDynamic and chtDynamic respectively), it's somewhat slower at insertion than the other two, significantly faster at querying than HullDynamic, and slightly faster at querying than chtDynamic. Overall, it's very competitive in performance.

      Insertions (1e7 insertions)

      LineContainer: 0.588702
      HullDynamic:   0.480461
      chtDynamic:    0.513528
      

      Queries (1e5 insertions, 1e7 queries)

      LineContainer: 0.109056
      HullDynamic:   0.385707
      chtDynamic:    0.146591
      

      Overall (1e7 insertions, 1e7 queries)

      LineContainer: 0.784574
      HullDynamic:   0.995786
      chtDynamic:    0.768847
      

      And finally, line count :^)

      LineContainer: 36
      HullDynamic: 44
      chtDynamic: 75
      

      I think the KTH implementation is clearly the winner. Benchmarks can be found here: https://ideone.com/caYDdF

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Starting with C++14, std::less<void> is transparent, so you don't even need the hack with the global bool Q. Instead, you can use different operator< for lines and query points. submission

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, that's nice. Is there any reason you made p mutable?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        p is the x-coordinate of the intersection with the next line and you need to update that when inserting new lines. A line inside the set is const, so you need mutable to make p modifiable. (k and m don't need to be changed, so they're not mutable.)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is it possible to remove lines from the struct?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          yes but no

          You can technically remove lines from the structure, but you cannot bring back the lines you previously discarded for the purpose on maintaining only the hull instead of all lines.

          One or more of those discarded lines may have the second largest value at some $$$x$$$ where the removed line had the max value, which you cannot recover. So you will be having an incomplete hull.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah, that makes sense. So is there any other way which allows remove or update queries on the line parameters while maintaining the complete hull?

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              Not that I know of, assuming you want to keep the same or close enough complexity.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              If queries is offline I think Divide & Conquer O(n * log^2) helps like in Dynamic Connectivity (easy google). Online harder, idk maybe some kind of SQRT decomposition on queries. Smth like keep last B queries and proceed in stupid way, for other queries there is built CHT. So number of stupid asks will be B * q, number of CHT rebuilds will be q / B. To avoid sorting we can merge, so if B = sqrt(n), and for simplicity q = n. Complexity is O(n * sqrt(n) + q * log(n))

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can do it using treap

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why do you need this 'while' in add function?

        while ((y = x) != begin() && (--x)->p >= y->p) {
            intersect(x, erase(y));
        }
        

        I deleted it and got AC. Maybe it's useful for different problems?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I guess it's perhaps unnecessary when the lines you're adding are increasing in some manner? KACTL's stress tests fail without those two lines, though, so in general they are necessary.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    How do I make it query the minimum value instead of the maximum? I'm just starting to learn this, so sorry for the dumb question.

    Edit: I figured it out, you're supposed to insert the negatives.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me what changes must be made to work for the min convex hull?

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      You can do this -

      Code
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Here's another related problem: YATP.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Great Tutorial!!!

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

This problem POLY can also be added here.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Tutorial! I tried solving the problem 1083E - The Fair Nut and Rectangles but for some reason my code is giving WA on test 5. Can someone please help me. 57194241

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You're forcibly including the first rectangle always. The optimal solution might leave it out.
    Fix is that when in ll m = get_max(lines, v[i].q); you find m < 0 you should not add it to dp[i].

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How do I modify the data structure so it gets the minimum at a point instead of the maximum?

Edit: I figured it out, you should insert the negatives of the slopes and constants.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

which order of the slopes or queries are relevant? decreasing or increasing. Or both? I'll be appreciated if you answer this comment :3

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The only difference between my AC code 69191641 and my WA on test 6 code for problem E — The Fair Nut and Rectangles was the "long double" used for comparing in fuction check(), which i put there because I saw that in many other's code. However, I didn't used any division, and the problem statement clearly said that xi, yi, ai are all int, so I'm very confused. Can someone please explain ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$b$$$ can be up to $$$10^{18}$$$ and $$$m$$$ can be up to $$$10^6$$$, so this multiplication overflows 64bit integers.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can some please tell me how to solve this problem https://codeforces.com/contest/319/problem/C using li chao tree....

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the implementation of "A More General Problem", how are you using lower bound for deque. You are doing lower bound for vector but in comparator using deque. I am not getting it. Can you explain it or share some links from where I can read about it? meooow.

Thank You

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The vector has integers $$$0, 1, 2, 3, 4, ...$$$ so this is just a clever way to not code his own binary search to find the index of the optimum line for a particular $$$x$$$.

    It would be a bit tricky to use lower_bound over the deque because we have to find the intersection with the next line. To do it you can keep the intersection with the next line in the struct and update it on insert.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for answering it.

      I got it for deque.

      How will we write lower bound for a set (In Full Dynamic Version) for query part? Nson

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Here is the kactl version

        The $$$p$$$ in the line struct represents the $$$x$$$ coordinate of the intersection with the next line. You can see it is modified upon insertion. This way you can do the same lower_bound without knowing the next line.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Nson is correct, it is just to avoid writing binary search code.
    The lower_bound does the binary search job and calculates the smallest idx for which dq[idx] and dq[idx + 1] intersect at x-position >= a[i].q.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, was looking at the Li Chao tree method and it seems a lot simpler. Would just like to know, does Li Chao tree have any limitations? Is it possible to use it even in a non-dynamic version (lines are sorted by slope, query not arbitrary)?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes, if it works as fully dynamic, that means you can insert and query in any order. That includes sorted order.
    Limitations of Li Chao tree that I can think of are (1) it only supports integer queries, and
    (2) operations take logarithmic time with respect to the query domain size rather than the current size of the hull.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi. Can anyone help my with problem Avoiding airports?

My main idea: For every outgoing edge u->v (s,e) find the min cost that we can reach v at time e:

From all incoming edges into u, earlier than s, find the min:

F(v,e) = min{e_i < s}(F(u, e_i) + (s — e_i) ^ 2) = s^2 + min(F(u,e_i) + e_i ^ 2 — 2 * e_i * s)

This is standard CHT. For every vertex I keep CHT and process time points:

1) if at time T I have outgoing edge from u to v (T, T2) — I say add to CHT[v] at time T2 line (-2*T2, Query(CHT[u], T) + T2^2)

2) if at time T I have incoming edge (e.g. the promise from step 1): I just added that line to CHT of a given vertex.

See my code: https://pastebin.com/RPnrHGJ0

It fails on test 5, where 50 < n < 100, m ~200000, and there is at least one pair (u,v) with the same departure and landing time (s = e)

Any ideas?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found the solution with LiChao tree that is very similar to mine. Can anyone explain why LiChao is needed?