10744 - The Optimal Super-Highway

[david]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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.

[mf]

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]

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

[mf]

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]

Thank you i'll give a try 4 it.