Hi Arunachalam!
Good work! Is there some way you can stop duplicates in the final
answer? i.e; ai+bj can be considered more than once as answer.
Sorry, i am poor at mathematics so can't figure it out how to get its
running time.
But still there is some way that we can get O(n) even in worst case....
think...:)
Arunachalam wrote:
> Here is the improvement to my previous algorithm.
>
> Observation 1.
> ax+by can appear in the solution only if ax+bj has appeared in the
> solution where j > y.
>
> Observation 2.
> ax+bn can be included only if a(x+1)+bn is included in the answer.
>
> 1. Extract an+bn as the maximum
> 2. Form a heap with a(n-1)+b(n) and a(n)+b(n-1).
> 3. Extract the maximum from the heap ( assume max extracted is ai+bj )
> 4. Add ai+b(j-1) to the heap
> 5. Add a(i-1)+bn also to the heap if the extracted max is ai+bn.
>
> So the worst case complexity for this log(n)+log(n-1)+..1.
>
> The best case is O(n) where the heap will have only 2 elements.
>
> PS: can someone prove using amortized analysis this solution has the
> complexity of O(n).
>
>
> On 4/3/06, Mayur <[EMAIL PROTECTED]> wrote:
> >
> > It doesn't matter. It's not correct. :((
> >
> > Here's what the algo does: -
> > It was basically an attempted patch to the problem you indicated: -
> >
> > curMin is the largest number which was not considered for printing at some
> > stage - but might be useful at some
> > other stage...
> >
> > Select an + bn
> > Next select either a(n-1) + bn or an + b(n-1), setting the other one to
> > curMin (or current-minimum).
> > i.e. Follow the sequence (let arbitrarily a(n-1)+b(n) be larger)
> >
> > an + bn
> > a(n-1) + bn
> > a(n-2) + bn
> > ...
> > a(n-k) + bn. <-- at some k, the value of a(n-k) + bn would be smaller
> > than curMin. In this case,
> > print whatever's there in current-min
> > Let the pointer 'j' "surge" ahead
> > Set curMin to be a(n-k) + bn (this number was not
> > printed), and set the surged-ahead flag to B.
> > Reset the pointer "i" to the last-position again ...
> >
> > Something like this: --
> > an + bn, a(n-1)+b(n), a(n-2)+b(n) ... a(n-k)+b(n) ---- a(n) + b(n-1)
> > ------> a(n-1)+b(n-1), a(n-2)+b(n-1), .. a(n-k') + b(n-1)
> >
> > | or
> >
> > |____> a(n) + b(n-2), a(n)+b(n-3), ... , a(n)+b(n-m)
> >
> > | or
> >
> > |____> a(n-k) + b(n), ...
> >
> > The whole point is that we must remember only one position for each array
> > (k for A, and m for B). This is the position where it last-broke off its
> > stride.
> > The algorithm which I wrote doesn't do all this... I mean, my intent was
> > to do this, but the algo's not correct.. I guess I was too eager ...
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > On 4/3/06, Arunachalam <[EMAIL PROTECTED]> wrote:
> >
> > > Hi,
> > It is very hard for me to get the basic flow of this algorithm. Can
> > you explain the basic idea behind the algorithm.
> >
> > regards
> > Arunachalam.
> >
> >
> > On 4/3/06, Mayur < [EMAIL PROTECTED]> wrote:
> >
> > > right... that's correct. Arunachalam's right... Sorry... My second
> > attempt at it...
> >
> > One assumption, though - the output need not be sorted...
> >
> > 1: curMin <- min( a[0], b[0] ) - 1
> >
> > 2: i <- n, j<-n
> > 3: cnt <- 0, whoSurged = NONE;
> > 4: while ( cnt < n )
> > {
> > 5: output a[i] + b[j]
> > 6: cnt <- cnt + 1
> > 7: if a[i] + b[j] < curMin
> > 8: then if whoSurged == A
> > 9: then j <- j - 1
> > 10: i = n
> > 11: else i <- i - 1
> > 12: j = n
> > 12.5: curMin = min(a[0], b[0]) - 1
> > 13: goto step 4
> > 14: if (a[i-1] + b[j]) < (a[i] + b[j-1])
> > 15: then j <- j - 1
> > 16: if curMin == (min(a[0], b[0]) -1 )
> > 17: then whoSurged = B
> > 18: curMin = a[i-1] + b[j+1]
> > 19: else i <- i - 1
> > 20: if curMin == (min(a[0], b[0]) -1 )
> > 21: then whoSurged = A
> > 22: curMin = a[i+1] + b[j-1]
> > }
> >
> >
> >
> > On 4/3/06, iwgmsft < [EMAIL PROTECTED]> wrote:
> >
> > >
> > > assume we have set {ai+bj}.. of size n^2
> > >
> > > we can solve using MERGE-SORT i think.. to divide this problem into
> > > subproblems will take O(2logn) i.e. O(log n)...
> > > now at the time of merge it will take O(2n) i.e . O(n)... so this time
> > > we can find n largest values(by merging values in decending order)..
> > >
> > > correct me if i m wrong..
> > >
> > >
> > >
> > >
> > >
> >
> >
> > http"//ww.livejournal.com/users/arunachalam
> >
> >
> >
> >
> >
> > >
> >
>
>
> --
> ===================================
> want to know more about me
> http"//ww.livejournal.com/users/arunachalam
>
> ------=_Part_4129_9059717.1144061235047
> Content-Type: text/html; charset=ISO-8859-1
> Content-Transfer-Encoding: quoted-printable
> X-Google-AttachSize: 11042
>
> <div>Here is the improvement to my previous algorithm.</div>
> <div> </div>
> <div>
> <div>Observation 1.</div>
> <div> ax+by can appear in the
> solution only if ax+bj has appeared in the solution where j > y.</div>
> <div> </div>
> <div>Observation 2.</div>
> <div> ax+bn can be included
> only if a(x+1)+bn is included in the answer.</div>
> <div> </div>
> <div>1. Extract an+bn as the maximum</div>
> <div>2. Form a heap with a(n-1)+b(n) and a(n)+b(n-1).</div>
> <div>3. Extract the maximum from the heap ( assume max extracted is ai+bj
> )</div>
> <div>4. Add ai+b(j-1) to the heap</div>
> <div>5. Add a(i-1)+bn also to the heap if the extracted max is ai+bn.</div>
> <div> </div>
> <div>So the worst case complexity for this log(n)+log(n-1)+..1. </div>
> <div> </div>
> <div>The best case is O(n) where the heap will have only 2 elements.</div>
> <div> </div>
> <div>PS: can someone prove using amortized analysis this solution has the
> complexity of O(n). </div><br> </div>
> <div><span class="gmail_quote">On 4/3/06, <b
> class="gmail_sendername">Mayur</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">
> <div style="DIRECTION: ltr">It doesn't matter. It's not correct. :((
> <br><br>Here's what the algo does: -<br>It was basically an attempted patch
> to the problem you indicated: -<br><br>curMin is the largest number
> which was not considered for printing at some stage - but might be useful at
> some
> <br>other stage...<br><br>Select an + bn<br>Next select either a(n-1) +
> bn or an + b(n-1), setting the other one to curMin (or
> current-minimum).<br>i.e. Follow the sequence (let arbitrarily
> a(n-1)+b(n) be larger)</div>
>
> <div style="DIRECTION: ltr"><span class="q"><br>an + bn<br>a(n-1) +
> bn<br></span></div>
> <div style="DIRECTION: ltr">a(n-2) + bn<br>...<br>a(n-k) + bn. <--
> at some k, the value of a(n-k) + bn would be smaller than curMin. In this
> case,
> <br>
> print whatever's there in
> current-min<br>
> Let the pointer 'j' "surge" ahead
> <br>
> Set curMin to be a(n-k) + bn (this number was not printed), and set the
> surged-ahead flag to
> B.<br>
> Reset the pointer "i" to the last-position again
> ...<br><br>Something like this: --
> <br>an + bn, a(n-1)+b(n), a(n-2)+b(n) ... a(n-k)+b(n) ---- a(n) +
> b(n-1) ------> a(n-1)+b(n-1), a(n-2)+b(n-1), .. a(n-k') +
> b(n-1)<br>
> | or
> <br>
> |____> a(n) + b(n-2), a(n)+b(n-3), ... ,
> a(n)+b(n-m)<br>
> | or
> <br>
> |____> a(n-k) + b(n), ...<br><br>The whole point is that we must
> remember only one position for each array (k for A, and m for B). This is the
> position where it last-broke off its stride.
> <br>The algorithm which I wrote doesn't do all this... I mean, my intent was
> to do this, but the algo's not correct.. I guess I was too eager ...
> <br><br><br><br><br><br><br><br><br>
> <br><br>
> <div></div>
> <div style="DIRECTION: ltr"><span class="e" id="q_10a5f3eebbe4977a_3"><span
> class="gmail_quote">On 4/3/06, <b class="gmail_sendername">Arunachalam</b>
> <<a onclick="return top.js.OpenExtLink(window,event,this)"
> href="mailto:[EMAIL PROTECTED]" target="_blank">
> [EMAIL PROTECTED]</a>> wrote:</span></span></div>
> <div style="DIRECTION: ltr">
> <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt
> 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid"></blockquote></div>
> <div style="DIRECTION: ltr"><span class="e" id="q_10a5f3eebbe4977a_5">
> <div style="DIRECTION: ltr">
> <div>Hi,</div>
> <div> It is very hard for me to get the basic flow of this
> algorithm. Can you explain the basic idea behind the algorithm.</div>
> <div> </div>
> <div>regards</div></div>
> <div style="DIRECTION: ltr"><span>
> <div>Arunachalam.<br><br> </div></span></div></span></div>
> <div style="DIRECTION: ltr">
> <div style="DIRECTION: ltr"></div>
> <div style="DIRECTION: ltr"><span class="e" id="q_10a5f3eebbe4977a_7">
> <div></div>
> <div style="DIRECTION: ltr"><span><span class="gmail_quote">On 4/3/06, <b
> class="gmail_sendername">Mayur</b> <<a onclick="return
> top.js.OpenExtLink(window,event,this)" href="mailto:[EMAIL PROTECTED]"
> target="_blank">
> [EMAIL PROTECTED]</a>> wrote:</span> </span></div>
> <div style="DIRECTION: ltr">
> <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px
> 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid"></blockquote></div>
> <div style="DIRECTION: ltr"><span>
> <div style="DIRECTION: ltr">right... that's correct. Arunachalam's
> right... Sorry... My second attempt at it... <br><br>One assumption,
> though - the output need not be sorted...<br><br>1: curMin <- min( a[0],
> b[0] ) - 1
> </div>
> <div style="DIRECTION: ltr"><span><br>2: i <- n, j<-n<br></span></div>
> <div style="DIRECTION: ltr">3: cnt <- 0, whoSurged = NONE;<br>4: while (
> cnt < n )<br>{<br>5: output a[i] +
> b[j]<br>6: cnt <- cnt +
> 1<br>7: if a[i] + b[j] < curMin
> <br>8: then if
> whoSurged == A
> <br>9:
> then j <- j -
> 1<br>10:
> i =
> n<br>11:
> else i <- i -
> 1<br>12:
> j =
> n<br>12.5:
> curMin = min(a[0], b[0]) -
> 1<br>13:
> goto step 4
> <br>14: if (a[i-1] + b[j]) < (a[i] +
> b[j-1])<br>15: then j <- j -
> 1<br>16: if curMin ==
> (min(a[0], b[0]) -1 )<br>17:
> then whoSurged =
> B<br>18:
>
> curMin = a[i-1] + b[j+1]
> <br>19: else i <- i -
> 1<br>20: if curMin ==
> (min(a[0], b[0]) -1 )<br>21:
> then whoSurged =
> A<br>22:
>
> curMin = a[i+1] + b[j-1]<br>}<br><br><br><br>
> <div></div>
> <div style="DIRECTION: ltr"><span><span class="gmail_quote">On 4/3/06, <b
> class="gmail_sendername">iwgmsft</b> <<a onclick="return
> top.js.OpenExtLink(window,event,this)" href="mailto:[EMAIL PROTECTED]"
> target="_blank">
> [EMAIL PROTECTED]</a>> wrote:</span></span></div>
> <div style="DIRECTION: ltr"><span>
> <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt
> 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid"><br>assume we have set
> {ai+bj}.. of size n^2<br><br>we can solve using MERGE-SORT i think.. to
> divide this problem into
> <br>subproblems will take O(2logn) i.e. O(log n)...<br>now at the time of
> merge it will take O(2n) i.e . O(n)... so this time<br>we can find n largest
> values(by merging values in decending order)..<br><br>correct me if i m
> wrong..
> <br><br><br><br><br></blockquote></span></div>
> <div style="DIRECTION: ltr"></div></div></span></div></span></div>
> <div style="DIRECTION: ltr">
> <div style="DIRECTION: ltr">
> <div style="DIRECTION: ltr"><span><br><br></span></div></div>
> <div style="DIRECTION: ltr"><span class="q">
> <div style="DIRECTION:
> ltr"><span><br>http"//ww.livejournal.com/users/arunachalam
> <br><br><br></span></div>
> <div style="DIRECTION: ltr"></div></span></div>
> <div style="DIRECTION: ltr"></div></div>
> <blockquote></blockquote></div><br> </div>
> <div style="DIRECTION: ltr"><span class="e"
> id="q_10a5f3eebbe4977a_11"><br><br>http"//ww.livejournal.com/users/arunachalam
>
> ------=_Part_4129_9059717.1144061235047--
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
