IHateDynamicProgramming's blog

By IHateDynamicProgramming, history, 6 weeks ago,

Hello,

I'm trying to solve a nice and hard problem: Given n functions yi(x) = a0 + a1x + a2x^2 + a3x^3 and q queries. For each query, you are given an integer t and you are required to find out yi (i ≤ i ≤ n) that minimizes the value of yi(t).

I found a solution for this problem, using Li Chao tree: https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

But, I don't understand in a property: After sqrt(a0), two functions can intersect at most one time.

Special thanks!

• +3

 » 6 weeks ago, # |   0 This can be solved using dynamic programming :D
•  » » 6 weeks ago, # ^ |   0 But I want to prove that: After sqrt(a0), two functions can intersect at most one time!
 » 6 weeks ago, # |   0 Well, I can tell you a way of solving that problem. We have polynomials of degree $\le 3$. Their graphs can be split in a few pieces in a way that every piece intersect each other in at most one point (split every time that monotonicity or convexity changes). You can then use each piece in the relevant range of $x$s for it, and use LiChao Tree.