@Dave
1. should it not be O(k + klogk) ??
2. but u are not considering all the possible values... let k =3
like i. a1+b1
ii. min( a1+b2, a2+b1) upto these fine one of them will be
chosen ...either ia or ib will increase.
iii. but know we have to take remaining of step ii in to
consideration along with
a1+b3,a3+b1,a2+b3,a3+b2 ...
On Fri, Oct 15, 2010 at 8:20 PM, Dave <dave_and_da...@juno.com> wrote:
> @Coolfrog$: You don't have to sort the arrays. You only have to find
> the k smallest elements in each and sort those k entries. This can be
> done in O(n + k log k).
>
> Algorithm:
> find the smallest k elements of A and sort them into ascending order.
> find the smallest k elements of B and sort them into ascending order.
> ia = 1
> ib = 1
> output ia, ib, A(ia)+B(ib)
> for n = 1 to k do
> if A(ia + 1) + B(ib) > A(ia) + B(ib + 1) then
> ia = ia + 1
> else
> ib = ib + 1
> end if
> output ia, ib, A(ia)+B(ib)
> end for
>
> Complexity O(n + k log k).
>
> Dave
>
>
> On Oct 15, 4:00 am, "coolfrog$" <dixit.coolfrog.div...@gmail.com>
> wrote:
> > @amod
> > as given A->B and B->A are in sorted form...if not sort them
> in
> > O(n log n).
> > then
> > first suggestion A1+B1
> > second suggestion MIN( A1+B2 , B1+A2) ===> let it be B1+A2
> > third suggestion MIN( A1+B2 , A1+B3, A3+B1,A2+B3, A3+B2)====> let it
> be
> > A2+B3
> > and so on...
> >
> > @Dave what will be complexity of above solution...?
> > i think O(n log n) for sorting and second part (suggestions) O(n)..
> >
> > Guys do correct me plz...
> >
> >
> >
> >
> >
> > On Thu, Oct 14, 2010 at 11:10 AM, Amod <gam...@gmail.com> wrote:
> > > @Dave You are partly correct.
> >
> > > If i ask for four minimum fares for the round trip then
> > > first suggestion is what u said : sum the sum of the minimum cost from
> > > A to B and the minimum cost from B to A
> > > after that we have to see which combination from both costs, sums up
> > > least
> >
> > > On Oct 14, 9:55 am, Dave <dave_and_da...@juno.com> wrote:
> > > > @Amod. Isn't the minimum sum the sum of the minimum cost from A to B
> > > > and the minimum cost from B to A? What am I missing?
> >
> > > > Dave
> >
> > > > On Oct 13, 11:06 pm, Amod <gam...@gmail.com> wrote:
> >
> > > > > Hi
> >
> > > > > I think I forgot to mention that the SUM of the ROUND trip i.e.
> A->B->A
> > > (sum = going + returning) should be least.
> >
> > > > > Please don't take into account any other thing like time and
> > > > > availability.
> > > > > So solution is not that straightforward.
> >
> > > > > Its like we have two arrays and we have to return least k sum from
> the
> > > > > given arrays where we take one element from the first and one from
> > > > > second in the sum.
> >
> > > > > Cheers
> > > > > Amod
> >
> > > > > On Oct 13, 2:26 pm, Shiyam code_for_life <mailshyamh...@gmail.com>
> > > > > wrote:
> >
> > > > > > When a user wants to choose to fly from A to B, suggest the
> flight
> > > > > > with lowest fare that's available, here its A1, if A1 is busy
> then A2
> > > > > > and so on
> > > > > > Repeat the same for B to A.
> >
> > > > > > Am I missing something here?
> >
> > > > > > Complexity is O( (number of flights from A to B) + number of
> flights
> > > > > > from B to A) )
> >
> > > > > > Cheers
> >
> > > > > > 'Coding is an art'- Hide quoted text -
> >
> > > > > - Show quoted text -
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > *Divesh*
> > (¨`·.·´¨) Always
> > `·.¸(¨`·.·´¨ ) Keep
> > (¨`·.·´¨)¸.·´Smiling!
> > `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life
> 1000's
> > of reasons 2Smile"- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
