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

×

Editorial for Perfect Equation(BIT_PRAI) from Overnight Coding

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

prnjl_rai's gravatar image

5★prnjl_rai
746
accept rate: 0%

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:

×1,722
×11

question asked: 16 Feb, 19:30

question was seen: 67 times

last updated: 16 Feb, 19:30