×

# Editorial for Perfect Equation(BIT_PRAI) from Overnight Coding

 0 Problem Code : BIT_PRAI Problem Link : https://www.codechef.com/ONIG2019/problems/BIT_PRAI Problem Setter : prnjl_rai (Pranjal Rai) Explanation : First of all notice the nature of the given equations. Both of the equations denote a parabola. $(X−a1)^2=b1.Y+c1$ $(X−a1)^2=b1.Y+c1$ and it is clearly mentioned that $b1.b2<0$ which implies that the given parabolas are opposite facing in nature. Now the problem asks for the minimum distance between these 2 parallel to Y axis i.e. the vertical distance. So, first let us check whether these 2 parabolas touch or intersect each other? If yes, the minimum distance between them is 0. To do so, solve the given equations which will result in a quadratic equation $(b1-b2).X^2+2.(a1.b2-a2.b1).X+(b2.c1-b1.c2+b1.a2^2-b2.a1^2)=0$ Check if the roots of obtained quadratic equation are real or imaginary. If the roots are real, given parabolas touch/intersect each other otherwise they don't. Now if the given parabolas don't touch/intersect each other, we can apply ternary search to find the minimum distance between them as the distance function between them is bitonic in nature. According to the given constraints, the X co-ordinates of the vertices of the given parabolas will remain in range $[-10^9,10^9]$. Apply ternary search within the range(You can choose a bigger range to be on safe side). Inside the search operation check the vertical distance between 2 parabolas and shift the range of search accordingly. Link to Setter's Solution : Link asked 16 Feb, 19:30 74●6 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×1,722
×11