10744 - The Optimal Super-Highway

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

Moderator: Board moderators

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

Post by david » Wed Oct 20, 2004 10:47 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:

Post by rotoZOOM » Thu Oct 21, 2004 3:39 am

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
Location: Bangladesh
Contact:

Need Help on p10744

Post by nahidshahin » Fri Oct 22, 2004 7:03 am

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

Post by rotoZOOM » Fri Oct 22, 2004 7:19 am

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

Post by david » Fri Oct 22, 2004 6:11 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

Post by bugzpodder » Sat Oct 23, 2004 5:05 am

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:

Post by rotoZOOM » Sat Oct 23, 2004 8:44 am

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.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Mon Dec 20, 2004 4:12 pm

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

Post by Destination Goa » Mon Feb 14, 2005 1:14 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

Post by bighilljae » Sun Aug 19, 2007 6:36 am

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 10744 - The Optimal Super Highway

Post by Obaida » Mon Feb 09, 2009 8:22 am

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. :oops:
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

Post by mf » Mon Feb 09, 2009 9:14 am

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 10744 - The Optimal Super Highway

Post by Obaida » Mon Feb 09, 2009 10:25 am

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

Post by mf » Mon Feb 09, 2009 10:38 am

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 10744 - The Optimal Super Highway

Post by Obaida » Mon Feb 09, 2009 10:47 am

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

Post Reply

Return to “Volume 107 (10700-10799)”