## 10744 - The Optimal Super Highway

All about problems in Volume CVII. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

### 10744 - The Optimal Super Highway

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[i] - 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
Experienced poster

Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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.
Maniac
Experienced poster

Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

### Hmm

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.
shahriar_manzoor
System administrator & Problemsetter

Posts: 400
Joined: Sat Jan 12, 2002 2:00 am

Now

My O(NlogN) ac at 2.1**
My O(N) ac at 0.8**
liulike
Learning poster

Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

### Thanks

Thanks. Your time will help me to calibrate the judge data.
shahriar_manzoor
System administrator & Problemsetter

Posts: 400
Joined: Sat Jan 12, 2002 2:00 am

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....
Maniac
Experienced poster

Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

### Re: Hmm

shahriar_manzoor wrote: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?

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Maniac wrote: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..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

### Re: Hmm

little joey wrote:
shahriar_manzoor wrote: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.
shahriar_manzoor
System administrator & Problemsetter

Posts: 400
Joined: Sat Jan 12, 2002 2:00 am

### Re: Hmm

little joey wrote:
shahriar_manzoor wrote: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.
rotoZOOM
Learning poster

Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk

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
Last edited by bugzpodder on Tue Oct 19, 2004 5:20 pm, edited 1 time in total.
bugzpodder
Experienced poster

Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

bugzpodder wrote: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 ?
rotoZOOM
Learning poster

Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk

ax+by+c is signed distance. and i didnt use counting sort... i used what Larry did
Last edited by bugzpodder on Tue Oct 19, 2004 5:23 pm, edited 1 time in total.
bugzpodder
Experienced poster

Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

bugzpodder wrote: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.

misof
A great helper

Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

misof wrote: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. ))
rotoZOOM
Learning poster

Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk

Next