IHateDynamicProgramming's blog

By IHateDynamicProgramming, history, 6 weeks ago, In English

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).

Link: https://www.codechef.com/NOV17/problems/POLY

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.

I need your help, please!

Special thanks!

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This can be solved using dynamic programming :D

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.