10744 - The Optimal Super-Highway
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 - 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
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
-
- System administrator & Problemsetter
- 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.
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
Thanks
Thanks. Your time will help me to calibrate the judge data.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Re: Hmm
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.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.
Are you loosing your sharp edges, or did your past problems make me a little over-cautious?
![:lol:](./images/smilies/icon_lol.gif)
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
They're complicated enough that the overhead might not be worth it anyhow.Maniac wrote:Cool, I never used countsort before but now I see the valueGot AC in 0.9 sec now.
I still wonder how one might find the median of an arbitrary array in linear time though....
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..
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
Re: Hmm
Your last two lines are true.little joey wrote: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.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.
Are you loosing your sharp edges, or did your past problems make me a little over-cautious?
I just forgot to put ranges on A and B
![:wink:](./images/smilies/icon_wink.gif)
They also follow the range of other coordinates.
-
- Learning poster
- Posts: 63
- Joined: Mon Dec 22, 2003 5:05 am
- Location: Russia, Chelyabinsk
- Contact:
Re: Hmm
You can take line parallel to AB, that include first input point (for example), and you'll get small numbers.little joey wrote: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.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.
Are you loosing your sharp edges, or did your past problems make me a little over-cautious?
I don't understand about integer solution.
Distance from points to line is not neccessary integer.
-
- 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![:)](./images/smilies/icon_smile.gif)
and distances to the line with rational slope from integer points are an integer multiple of an integer to the power of -1/2
![:)](./images/smilies/icon_smile.gif)
Last edited by bugzpodder on Tue Oct 19, 2004 5:20 pm, edited 1 time in total.
-
- Learning poster
- Posts: 63
- Joined: Mon Dec 22, 2003 5:05 am
- Location: Russia, Chelyabinsk
- Contact:
For example, A(1,0), B(100,3)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
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 ?
-
- 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.
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.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
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.