You are not logged in. Please login at www.codechef.com to post your questions!

×

Dynamic Programming Optimization-Convex hull Trick

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.

asked 04 Dec, 22:46

adzo261's gravatar image

3★adzo261
2898
accept rate: 37%

edited 04 Dec, 22:59

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?

(05 Dec, 01:25) meooow ♦6★

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

(05 Dec, 09:35) adzo2613★

link

answered 05 Dec, 17:24

arjunarul's gravatar image

2★arjunarul
2354
accept rate: 14%

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

(05 Dec, 18:05) arjunarul2★

Okay, great!

(05 Dec, 19:13) adzo2613★

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

link

answered 05 Dec, 16:41

cis_pie's gravatar image

5★cis_pie
1055
accept rate: 9%

edited 05 Dec, 16:44

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

(05 Dec, 16:54) aryanc4035★

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

link

answered 04 Dec, 23:35

aryanc403's gravatar image

5★aryanc403
2.2k515
accept rate: 11%

edited 05 Dec, 16:55

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,030
×46
×37
×10

question asked: 04 Dec, 22:46

question was seen: 270 times

last updated: 05 Dec, 19:13