CPOINT - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

We can solve this problem by using Ternary Search algorithm:

  • At first, we take a look at a sub-problem: Finding an integer point on the line y=c satisfying its sum of distances to N given points (S’) is mininum. In this sub-problem, every integer point on the line y=c will lead to a respective value of S’, and all of that values together make a parabolic-like curve on the plane. So we can use Ternary Search algorithm to find the respective mininum value of S’.

  • Just imagine that the problem we have to solve is upgraded from the above one, since all the minimum values of S’ will together make a parabolic-like curve from which we can find the minimum value of S. Our task is applying Ternary Search algorithm again!

  • On the other hand, we can also imagine that all values of S (for respective integer points) will together make a parabola in 3D-space, so our work is using Ternary Search in certain layers when we try to cut it by a plane!

See the source code for details and find more information about the Ternary Search algorithm at: http://en.wikipedia.org/wiki/Ternary_search

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2

Bit rusty with maths so need some clarification:

In this sub-problem, every integer
point on the line y=c will lead to a
respective value of S’, and all of
that values together make a
parabolic-like curve on the plane.

I want to understand how it is a parabolic curve?

So we can use Ternary Search algorithm
to find the respective mininum value
of S’.

How is it that a parabolic curve implies we can use a Ternary Search algorithm to find the minimum?

3

http://www.codechef.com/viewsolution/5547419 can you please help me what i am missing in the code … i tested with the inputs provided in the question it worked fine for me … please i am a new beginner for the site … am i missing any guidelines.