## 10744 - The Optimal Super-Highway

Moderator: Board moderators

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
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 ?
Why do you say 10203 is too big for counting sort???
The numbers ax + by will always be in the range -40000...40000, so you need an array of 80000 integers, which easily fits into memory.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
david wrote:Why do you say 10203 is too big for counting sort???
The numbers ax + by will always be in the range -40000...40000, so you need an array of 80000 integers, which easily fits into memory.
Hmm, you're right man.
80000 is not so big.
By the way, I tried to use integer arithmetic and sort.
Algo O(NlogN), and I got AC in 8 sec (((

nahidshahin
New poster
Posts: 8
Joined: Mon Nov 10, 2003 10:54 am
Contact:

### Need Help on p10744

shahriar_manzoor wrote:
There are ways to find medians in linear time
But I can't understand How I find medians in linear time ? I use partition method that use quick sort.
But it's worst case complexity is O(nlogn)

Please some one help me to get medians in linear time.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

### Re: Need Help on p10744

nahidshahin wrote:shahriar_manzoor wrote:
There are ways to find medians in linear time
But I can't understand How I find medians in linear time ? I use partition method that use quick sort.
But it's worst case complexity is O(nlogn)

Please some one help me to get medians in linear time.
Use counting sort.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

But I can't understand How I find medians in linear time ? I use partition method that use quick sort.
But it's worst case complexity is O(nlogn)

Please some one help me to get medians in linear time.
Even when counting sort isn't possible, the median can be found in linear time.
The idea is similar to that of quicksort, only that one recursive call, instead of two, is needed, which accounts for the O(N) average (although O(N^2) worst-case) complexity. More specifically, to find the element that would occupy the k-th position of a vector V[0..N) if it were sorted, pick a pivot and partition the array into two subvectors V[0..m) and V[m..N), where all elements in the first subvector are smaller than the pivot, which in turn is no larger than all elements in the second. If k <= m, we know the k-th element will be in the first part; if k > m, it suffices to locate the (k-m)th element in the second part. Either way, we can proceed recursively.
This method can be improved to yield an O(N) time complexity in the worst case, but I don't think implementing it is worth the effort in practice; you would be better off selecting the pivot randomly if you are suspicious of the judge test data..

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
rotoZOOM wrote:
david wrote:Why do you say 10203 is too big for counting sort???
The numbers ax + by will always be in the range -40000...40000, so you need an array of 80000 integers, which easily fits into memory.
Hmm, you're right man.
80000 is not so big.
By the way, I tried to use integer arithmetic and sort.
Algo O(NlogN), and I got AC in 8 sec (((
what are you using? Java?

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
bugzpodder wrote:By the way, I tried to use integer arithmetic and sort. Algo O(NlogN), and I got AC in 8 sec ((

what are you using? Java?
C++ and STL sort
My last submission use counting sort.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
It indeed is possible to determine the k-th smallest value of a set S in O(|S|) time without using counting sort:

Code: Select all

``````select(S, k)
{
if |S| <= LIMIT
{
sort S
return k-th element of S
}

split S into groups of 5 (possibly creating one group with less than 5)

B = medians of these groups (each in constant time)

Pivot = select(B, |B| / 2);

partition S into S1 (< Pivot), S2 (= Pivot), and S3 (> Pivot)

if (k <= |S1|)
return select(S1, k);

if (k > |S1| + |S2|)
return select(S3, k - |S1| - |S2|);

return Pivot;
}
``````
The value of LIMIT depens on the sorting algorithm used, usually it is something around 15. The algorithm itself is very similar to quicksort, but only one partition needs to be sorted in each recursion step. It can easily be transformed into an iterative version.

The special choice of the pivot element ensures the linear time need. The proof is based on how many elements are definitely larger or smaller than the pivot, limiting the size of S1 and S3. Choosing an arbitrary element as pivot would allow |S3| = |S| - 1, resulting in quadratic worst-case behaviour.

I got TLE when trying to implement the algorithm, probably due to the required overhead.

My current solution uses something similar to counting sort, which is a lot faster. Does anyone know how the three sub-second solutions work?

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
Hello Shahriar.

I've got idea of another problem like this. Set free limits (like floats in range -1000 ... +1000 for x/y/A/B), set N to something like 1'000, and Q to something 100'000. Q*N*log(N) obviously won't work here, but there is a beautiful N^2*log(N) + Q*log(Q) solution for such problem

bighilljae
New poster
Posts: 1
Joined: Sun Aug 19, 2007 6:23 am

### I don't Think

Code: Select all

``````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 don't think so that O(N.logn)is AC...

When I use N.log n, it was TLE.
but, if I use O(N), it was WA( this is not AC but, WA means not TLE)

How can you explain it?
Thanks, *^^*

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10744 - The Optimal Super Highway

Does this work for this program?
http://valis.cs.uiuc.edu/~sariel/resear ... /main.html
I am really confused about the solution someone plz help.
try_try_try_try_&&&_try@try.com
This may be the address of success.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10744 - The Optimal Super Highway

Obaida wrote:Does this work for this program?
http://valis.cs.uiuc.edu/~sariel/resear ... /main.html
No.

Read the other posts in this thread. And this problem is basically a variant of http://acm.uva.es/p/v100/10041.html, so you may want to reads something about that problem, too.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10744 - The Optimal Super Highway

Hi i solved 10041 but this one is more hard!!! there we can calculate s1-s2 easily. But here how i can find s1-s2.
My question is if s1 is a given point and s2 would be the point through which the highway will go. Then how i can find s2?
i know one thing it's equdistance to A and B. But i need so many guess to confirm the point. This may cause TLE..
try_try_try_try_&&&_try@try.com
This may be the address of success.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10744 - The Optimal Super Highway

Read the very first post of this thread. All you need to reduce it to the same problem as 10041 is know how to find a (signed) distance between a point and a line.

IF you get TLE, use a more efficient selection algorithm, than sorting. A modification of quicksort does selection in expected O(n) time, and is available in STL under the name std::nth_element.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10744 - The Optimal Super Highway

Thank you i'll give a try 4 it.
try_try_try_try_&&&_try@try.com
This may be the address of success.