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

×

POLY - Editorial

2
3

PROBLEM LINK:

Practice
Contest

Author: Trung Nguyen
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

DIFFICULTY:

HARD

PREREQUISITES:

Li Chao segment tree OR good sense of lower hull trick

PROBLEM:

You have $n$ polynomials $y_i(x)=a_0+a_1x+a_2x^2+a_3x^3$ and $q$ queries in which you are asked to find $y_i$ which minimizes $y_i(t)$.

QUICK EXPLANATION:

Solve problem via brute force for small $t$ and for large use Li Chao segment tree.

EXPLANATION:

Consider polynomial $y_i-y_j$ for some $i$ and $j$. Its degree is at most three.

Lemma: Polynomial $y=x^3+ax^2+bx+c$ has at most one root greater than $k=\sqrt{\max(|b|,|c|)}+2$.

Proof: Let $u\geq v >k\geq w$ to be the roots of $y$. Then $y=(x-u)(x-v)(x-w)$ so $b=uv+uw+vw$, $c=-uvw$. Since $u,v>\sqrt {|c|}$ it holds that $|w|<1$. Thus $b=uv+w(u+v)> uv-(u+v)=(u-1)(v-1)-1$. But since $u,v>\sqrt {|b|} + 2$ we have $b> (\sqrt {|b|} + 1)^2-1=|b|+2\sqrt {|b|}>b$ which is contradiction. $$\tag*{$\Box$}$$

Given this and the fact that for $x^2+bx+c$ at most one root greater than $\sqrt{|c|}$ (due to their product being equal to $c$) we can just manually check first $350>\sqrt{10^5}$ integer points and consider functions only on set of points after $350$ when any two functions will have at most one intersection points due to their difference being at most third degree polynomial.

Now to handle queries on $[350,+\infty)$ we will use Li Chao segment tree. Assume you're given set of functions such that each two can intersect at most once. Let's keep in each vertex of segment tree some function in such way that if we go from root to the leaf, it will be guaranteed that among functions we meet on the path will be the one giving minimum value in that leaf. Let's see how to construct it.

Assume we're in some vertex corresponding to half-segment $[l;r)$ and function $f_{old}$ is kept there and we adding to the set function $f_{new}$. Then intersection point will be either in $[l;m)$ or in $[m;r)$ where $m=\left\lfloor\dfrac{l+r}{2}\right\rfloor$. We can efficiently learn that comparing values of functions in points $l$ and $m$. If dominating function changes then it's in $[l;m)$ otherwise it's in $[m;r)$. Now for the half of segment where there no intersection we pick lower function and write it in current vertex. After that we recursively go to the other half of segment with the function which was upper one. As you can see this will keep correctness on the first half of segment and in the other one correctness will be maintained during the recursive call. Thus we can add functions and check the minimum value in the point in $O(\log C)$.

Here is the illustration of what's going on in the vertex when we consider adding in it new function:

alt text

In this particular case we will keep new in the vertex and recursively call in the left segment with old function.

ALTERNATIVE SOLUTION

One can construct hull of functions in offline instead of using LiChao tree. If function $f_a$ less than function $f_b$ on $x\to+\infty$ and they have at most one point of intersection then $f_a$ coefficients $(a_3,a_2,a_1,a_0)$ lexicographically smaller than coefficients of $f_b$. Thus we can firstly sort functions in descending order of their coefficients and then add functions one by one to maintain the lower envelope.

We will keep them in stack. Assume this stack to be $(f_1,f_2,\dots,f_k)$ and points $350< x_2< \dots< x_k$ are the intersections of the functions. Then function $f_i$ have least value among all functions on $(x_i,x_{i+1})$ with $x_1=350,x_{k+1}=+\infty$. If we consider new function $f_{k+1}$ with all coefficients lexicographically smaller than ones of functions we have then there will be such point $x_0$ that it will have smaller values than all functions on $(x_0,+\infty)$ and it will still have larger values than functions from envelope on $(350,x_0)$. So we can repeatedly remove functions $f_k$ till they have larger values than both $f_{k+1}$ and $f_{k-1}$ at the point where functions $f_{k-1}$ and $f_{k+1}$ intersect and add function $f_{k+1}$ in the stack afterwards. This will be sufficient to build lower envelope of functions and if you also keep their intersection points then you can use binary search to find function with lowest value in given point $x$.

This approach strongly generalizes well-known convex hull trick for the case in which we have set of non-necessarily convex functions with the property that they have at most one intersection and we can calculate beforehand which order will they have if we consider them for $x\to+\infty$.

Finally, to illustrate the solution, I'll provide some pictures. Assume you had functions $f_1$, $f_2$, $f_3$ in the stack. alt text

And now you want to add $f_4$. alt text

As we see function $f_3$ is no use at all since it is above point of intersection of functions $f_2$ and $f_4$. So we remove it and place $f_4$ in its place in the stack.

alt text

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 12 Nov '17, 00:22

melfice's gravatar image

2★melfice
71825
accept rate: 0%

edited 21 Nov '17, 21:49

admin's gravatar image

0★admin ♦♦
19.0k348495533


Any resource on Lichao_SegmentTree ? I read the CF comment already, but was not enough for me to come up with this magic Data Structure, i will be glad if anyone can help :)

link

answered 20 Nov '17, 21:57

trath's gravatar image

4★trath
111
accept rate: 0%

For the lower convex hull trick, why is assuming that each pair of functions intersect in at most one point correct?

link

answered 19 Nov '17, 13:52

amr_keleg's gravatar image

2★amr_keleg
1
accept rate: 0%

Read the Lemma and 1st paragraph. there would be at most 1 intersection point past 350.

(19 Nov '17, 19:26) nilesh31055★

Ok , I see. Yet I have another two questions. 1) Is there a formula to find the largest real root of a cubic equation? Should I use binary Search (bisection method) or other numerical methods? 2) Does this lemma somehow generalise to higher order polynomials?

(19 Nov '17, 23:04) amr_keleg2★

@amr_keleg Because they are increasing functions,so two lines will intersect atmost 1 time(provided both are not the same function)

Edit: Not necessary unless linear as nilesh specified,however beyond a particular x it intersects atmost 1.

link

answered 19 Nov '17, 16:02

vivek_1998299's gravatar image

6★vivek_1998299
1.3k29
accept rate: 22%

edited 20 Nov '17, 00:53

1

You are wrong. This would only be true when rate of increase is constant i.e. the functions are linear.

(19 Nov '17, 19:28) nilesh31055★

@nilesh3105 Yeah i got it!!. Thanx for correcting me.

link

answered 20 Nov '17, 00:46

vivek_1998299's gravatar image

6★vivek_1998299
1.3k29
accept rate: 22%

edited 20 Nov '17, 00:49

Here is my, less complicated solution:

I created a comparator function for polinomials, which compares them by a3, then a2 and so on.

For first I precompute answer up to 320 (the constant is because 320^2 > 10^5) by brute-force.

After that I sort the queries by ascending. If for some t query (t > 320), we find a p and a q polinom, where the p polinom compares less than q polinom, and p(t) < q(t) stands, then we can remove q polinom from the set, because for every x > t, p(x) < q(x) will hold also. It can be proved indirectly, using the fact t > 320.

I'm unsure about the number of runs for a given polinomial, but it isn't too much, as I got AC in 0.26.

link

answered 21 Nov '17, 00:44

bazsi700's gravatar image

6★bazsi700
3758
accept rate: 7%

edited 21 Nov '17, 21:52

What is the time complexity of author solution?

link

answered 11 Jul, 11:57

sauravchandra1's gravatar image

4★sauravchandra1
1
accept rate: 0%

wikified 11 Jul, 11:58

I also wanna know it xD...

(11 Jul, 20:05) l_returns4★
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:

×14,441
×1,213
×300
×23
×6

question asked: 12 Nov '17, 00:22

question was seen: 1,223 times

last updated: 11 Jul, 20:05