Editing Convex hull trick
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 106: | Line 106: | ||
# <math>m = -2a\sigma(k)</math> | # <math>m = -2a\sigma(k)</math> | ||
# <math>p = \operatorname{dp}(k) + a\sigma(k)^2 - b\sigma(k)</math> | # <math>p = \operatorname{dp}(k) + a\sigma(k)^2 - b\sigma(k)</math> | ||
− | Then, we see that <math>mz + p</math> is the quantity we aim to | + | Then, we see that <math>mz + p</math> is the quantity we aim to minimize by our choice of <math>k</math>. Adding <math>a\sigma(n)^2 + b\sigma(n) + c</math> (which is independent of <math>k</math>) to the maximum gives the correct value of <math>\operatorname{dp}(n)</math>. Also, <math>z</math> is independent of <math>k</math>, whereas <math>m</math> and <math>p</math> are independent of <math>n</math>, as required. |
Unlike in task "acquire", we are interested in building the "upper envelope". We notice that the slope of the "maximal" line increases as <math>x</math> increases. Since the problem statement indicates <math>a < 0</math>, the slope of each line is positive. | Unlike in task "acquire", we are interested in building the "upper envelope". We notice that the slope of the "maximal" line increases as <math>x</math> increases. Since the problem statement indicates <math>a < 0</math>, the slope of each line is positive. | ||
− | Suppose <math>k_2 > k_1</math>. For <math>k_1</math> we have slope <math>m_1 = -2a \sigma(k_1)</math>. For <math>k_2</math> we have slope <math> | + | Suppose <math>k_2 > k_1</math>. For <math>k_1</math> we have slope <math>m_1 = -2a \sigma(k_1)</math>. For <math>k_2</math> we have slope <math>m_1 = -2a \sigma(k_1)</math>. But <math>\sigma(k_2) > \sigma(k_1)</math>, so |
− | + | But <math>\sigma(k_2) > \sigma(k_1)</math> since the given sequence is positive, so <math>m_2 > m_1</math>. We conclude that lines are added to our data structure in increasing order of slope. | |
Since <math>\sigma(n) > \sigma(n-1)</math>, query values are given in increasing order and a [[pointer walk]] suffices (it is not necessary to use binary search.) | Since <math>\sigma(n) > \sigma(n-1)</math>, query values are given in increasing order and a [[pointer walk]] suffices (it is not necessary to use binary search.) |