mentalist's blog

Dynamic Programming – Convex Hull Optimisation
By mentalist, 10 years ago, In English

I recently read the article from PEG Wiki about the convex hull trick, which can be applied to speed up dynamic programming algorithms (Link to the website) . This optimisation can only apply when certain conditions are met. Surprisingly, at the end of the article I read that we can achieve a fully dynamic variant of the trick (meaning that there are no conditions of applicability) if we store the lines in a std::set. Although I have understood the approach mentioned, I always fail when I try to implement it. Could someone point me to an implementation of the dynamic convex hull trick, and some problems where I can practice it? Thanks in advance.

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

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

Here: http://codeforces.com/blog/entry/11155#comment-162462

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Thank you very much! This is exactly what i was looking for. By the way, I found a really nice problem for everyone who is interested in practicing this technique: http://www.spoj.com/problems/GOODG/

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I am the author of the dynamic convex hull code dj3500 linked to, so please write me if you find any problems :)

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

      Just as a warning for future readers.

      You don't need the fully dynamic variant to solve this problem. You can solve it easily with a different approach. :)

      → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here are many good convex-hull trick problems (also in the comments): http://codeforces.com/blog/entry/8219

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Here is my alternative implementation. Hope this will help somebody. Note: this class can be used to find both max and min values.

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

    Thanks a lot!

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

    This helped me a lot, thanks for all the work you put in.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    Hey , I wanted to ask questions about your implementation!

    Does your Code needs any specific condition that is decreasing slopes or increasing values of x?

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

    thank you very much

    → Reply