Arunachalam wrote: > Sorry, > I did not read the Gene's solution properly. Great work Gene. I > doubt the solution given above. > > > On 6/27/06, Googmeister <[EMAIL PROTECTED]> 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 > > > > How will this solution work in which the optimal subset in > a[m-x]......a[m+y]. That is the solution extends over the two splitted half > of the arrays. I am not getting any points commented as *. Can you please > explain?
I don't follow your question. If the optimal interval is a[m-x]..a[m+y], where x and y are positive, then the optimal interval contains a[m]. This will be discovered in the third part of the recursive scheme (finding the optimal interval containing a[m]). > * 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. > > > > * If the optimal internal containing a[m] contains one > > element, it is simply a[m] > > * If it contains more than one element, it must > > contain the larger of a[m-1] and a[m+1], so add > > this to the interval. (If it contains the smaller > > of the two, you can only improve the solution > > by also including the larger of the two.) > > * Let's assume the element in the previous step > > was a[m-1]. Now, if the optimal interval contains > > more than two elements, it must contain the > > larger of a[m-2] and a[m+1]. > > * Etc. > > * Return the best interval of any size constructed > > by this process. > > > > > > > > > > > > -- > =================================== > want to know more about me > http"//ww.livejournal.com/users/arunachalam > > ------=_Part_8357_31231953.1151425970707 > Content-Type: text/html; charset=ISO-8859-1 > X-Google-AttachSize: 2488 > > <div>Sorry, </div> > <div> I did not read the > Gene's solution properly. Great work Gene. I doubt the solution given > above.<br><br> </div> > <div><span class="gmail_quote">On 6/27/06, <b > class="gmail_sendername">Googmeister</b> <<a href="mailto:[EMAIL > PROTECTED]">[EMAIL PROTECTED]</a>> wrote:</span> > <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px > 0.8ex; BORDER-LEFT: #ccc 1px solid"><br><br>Pradeep Muthukrishnan > wrote:<br>> I have been trying this problem for quite some time now...but > havent > <br>> found anything concrete...can anyone solve this?<br>> <a > href="http://acm.zju.edu.cn/show_problem.php?pid=2642";>http://acm.zju.edu.cn/show_problem.php?pid=2642</a><br><br>Here's > a O(n log n) mergesort style solution: > <br><br>>>>* Divide the elements in the middle: a[l..m-1], a[m], > a[m+1..r]<br>>>>* Recursively compute the optimal interval entirely > in the left half<br>>>>* Recursively compute the optimal interval > entirely in the right half > </blockquote> > <div> </div> > <div> </div> > <div>How will this solution work in which the optimal subset in > a[m-x]......a[m+y]. That is the solution extends over the two splitted half > of the arrays. I am not getting any points commented as *. Can you please > explain? > </div><br> > <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px > 0.8ex; BORDER-LEFT: #ccc 1px solid">* Compute the optimal interval containing > a[m]<br>* Return the best of the three intervals<br><br>The key step for > efficiency is computing the optimal > <br>interval containing a[m] in linear time. Here's a greedy > solution.<br><br>* If the optimal internal containing a[m] contains > one<br> element, it is simply a[m]<br>* If it contains more than > one element, it must<br> contain the larger of a[m-1] and a[m+1], > so add > <br> this to the interval. (If it contains the > smaller<br> of the two, you can only improve the > solution<br> by also including the larger of the two.)<br>* Let's > assume the element in the previous step<br> was a[m-1]. Now, if > the optimal interval contains > <br> more than two elements, it must contain > the<br> larger of a[m-2] and a[m+1].<br>* Etc.<br>* Return the > best interval of any size constructed<br> by this > process.<br><br><br><br>http"//ww.livejournal.com/users/arunachalam > > ------=_Part_8357_31231953.1151425970707-- --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
