[algogeeks] Re: Nice question!!

Tue, 27 Jun 2006 19:56:38 -0700

Googmeister is right!
 
A simple and wonderful solution in O(n log n)....
The strange thing I notcied is... we are getting algorithms simiar to sorting algorithms like mergesort and quicksort....  for this problem
Looks like there is a strange connection between sorting and this problem...

 
On 6/28/06, Googmeister <[EMAIL PROTECTED]> wrote:


Gene wrote:
> Googmeister wrote:
> > Pradeep Muthukrishnan wrote:
> > > I have been trying this problem for quite some time now...but havent
> > > found anything concrete...can anyone solve this?
> > > http://acm.zju.edu.cn/show_problem.php?pid=2642
> >
> > Here's a O(n log n) mergesort style solution:
> >
> >   * Divide the elements in the middle: a[l..m-1], a[m], a[m+1..r]
> >   * Recursively compute the optimal interval entirely in the left half
> >   * Recursively compute the optimal interval entirely in the right half
> >   * Compute the optimal interval containing a[m]
> >   * Return the best of the three intervals
> >
> > The key step for efficiency is computing the optimal
> > interval containing a[m] in linear time. Here's a greedy solution.
>
> Hi Gm,
>
> If finding this interval requires linear time, then the run time is
> proprtional to n^2

No. It's the standard n log n recurrence.

> because there is no bound on the size of the
> interval you're searching for

Yes there is. At each recursive call the size of the interval
shrinks by a factor of 2. Once you've divide the interval,
you no longer need to worry about intervals crossing
the border.

>  and each of n elements must eventually
> become a[m]

That's true. But the size of the interval left to examine
will be 1 or 2 for most of them.



--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to