10744 - The Optimal Super-Highway

[Maniac]

Unfortunately I get a TLE for this problem. My approach is the following:

read all points, i.e. the cities
then for each query:
- construct a line through the given points (A and B), i.e. the "other" road
- determine distance from each point to this line (negative distances for one side of the line, positive for the other)
- sort the array of distances
- determine the median
- asked distance is sum over all points i: abs(distance - distance[median])

My algo is O(n.log(n)) because of the sorting and hence too slow; an O(n) solution is intended by the problem setters. I don't think there is a faster way to find the median. Any hints about how to solve this problem?

Thanks, Erik

[Maniac]

A small correction: during contest I got TLE. Now I get AC in 7 secs, but there is probably a faster algorithm cause lots of people have runtime under 1 sec.

[shahriar_manzoor]

There are ways to find medians in linear time although that's not what I did. As everything is integer and maximum coordinate is small there is an all integer solution and counting sort works in that case. I will soon update the judge data so that O(nlogn) solutions fail.

[liulike]

Now

My O(NlogN) ac at 2.1**
My O(N) ac at 0.8**

[shahriar_manzoor]

Thanks. Your time will help me to calibrate the judge data.

[Maniac]

Cool, I never used countsort before but now I see the value Got AC in 0.9 sec now.

I still wonder how one might find the median of an arbitrary array in linear time though....

[little joey]

As everything is integer and maximum coordinate is small there is an all integer solution and counting sort works in that case.

Well, the limits for A and B are not explicitly given, so knowing you from past problems, I would expect anything (say values in the billions), in which case an all integer solution with counting sort becomes extremely infeasible.
Are you loosing your sharp edges, or did your past problems make me a little over-cautious?

[Larry]

Cool, I never used countsort before but now I see the value Got AC in 0.9 sec now.

I still wonder how one might find the median of an arbitrary array in linear time though....

They're complicated enough that the overhead might not be worth it anyhow.

The easy expected O(n) one is based on divide and conquer (ala quicksort).. given that hint, it's not too hard to figure out, but you can always google..

[shahriar_manzoor]

As everything is integer and maximum coordinate is small there is an all integer solution and counting sort works in that case.

Well, the limits for A and B are not explicitly given, so knowing you from past problems, I would expect anything (say values in the billions), in which case an all integer solution with counting sort becomes extremely infeasible.
Are you loosing your sharp edges, or did your past problems make me a little over-cautious?

Your last two lines are true.

I just forgot to put ranges on A and B
They also follow the range of other coordinates.

[rotoZOOM]

As everything is integer and maximum coordinate is small there is an all integer solution and counting sort works in that case.

Well, the limits for A and B are not explicitly given, so knowing you from past problems, I would expect anything (say values in the billions), in which case an all integer solution with counting sort becomes extremely infeasible.
Are you loosing your sharp edges, or did your past problems make me a little over-cautious?

You can take line parallel to AB, that include first input point (for example), and you'll get small numbers.
I don't understand about integer solution.
Distance from points to line is not neccessary integer.

[bugzpodder]

I have a O(n) that runs in .293, My O(nlogn) runs in .110 for quick sort built in C++.

and distances to the line with rational slope from integer points are an integer multiple of an integer to the power of -1/2

[rotoZOOM]

I have a O(n) that runs in .293, My O(nlogn) runs in .110 for quick sort built in C++.

and distances to the line with rational slope from integer points are an integer multiple of an integer to the power of -2

For example, A(1,0), B(100,3)
distance from point to line: (ax+by+c)/sqrt(a*a+b*b), where
a=A.y-B.y=-3
b=B.x-A.x=99
c=-a*A.x-b*A.y=3
for point (-100,100) D=10203/99.045
We can ignore 99.045 (since it is constant for all points), but result (10203) is too big for counting sort.
What is my mistake ?

[bugzpodder]

ax+by+c is signed distance. and i didnt use counting sort... i used what Larry did

[misof]

I have a O(n) that runs in .293, My O(nlogn) runs in .110 for quick sort built in C++.

and distances to the line with rational slope from integer points are an integer multiple of an integer to the power of -2

This was exactly my concern when I read Shahriar's post about trying to cut off O(N log N) solutions. My practical experience as a problemsetter shows that this is nearly impossible. If I want all reasonable O(N) solutions to be AC, then fast O(N log N) solutions will make it, too. This is a case where the small differences between programming languages matter. An O(N) solution in one of them may very well be slower than a good O(N log N) solution in other language.

In this case, O(N) solutions with real arithmetics will probably be slower than O(N log N) solutions using integer arithmetics.

But I don't see this as a problem. In my point of view, also the fast O(N log N) solutions are good and should be ACed.

[rotoZOOM]

But I don't see this as a problem. In my point of view, also the fast O(N log N) solutions are good and should be ACed.

I use qsort on distances and got TL.
But I used float pointing arithmetic. ))
I'll try integer one. ))