Dynamic Programming Optimization-Convex hull Trick

general
, , ,
1

I am trying to learn and understand convex hull trick.

I searched various discussions, and all point to wcipeg, which is down.

I know about cp-algorithms, can someone please provide any resources which explain it for beginners?
And also a few problems to start on with.

2

Sadly cp algorithms have a bad explanation for Convex hull Trick.
I learnt from https://codeforces.com/blog/entry/8219

1 Like
3

I think convex-hull trick is a neat (although very specific) technique, and I have considered writing a tutorial for it. Would that be a good idea?

3 Likes
4

Yes,please.
It would be helpful for everyone.
Thanks!

5

I think this video would be helpful.
For the problems, you can follow @aryanc403’s link.

2 Likes
6

I too recommend that video. I also watched that :slight_smile:

7

The WCIPEG page is well preserved here: http://web.archive.org/web/20181030143808/http://wcipeg.com/wiki/Convex_hull_trick

3 Likes
8

And I’m told that the PEG wiki is down only temporarily. It’s being fixed.

9

Okay, great!