## 10744 - The Optimal Super-Highway

Moderator: Board moderators

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

### 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 - 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.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### 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.

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am
Now

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

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Thanks

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

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 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?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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..

shahriar_manzoor
Posts: 399
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?
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
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

### 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.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
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.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
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 ?

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
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.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 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.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
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. ))