@Coolfrog$:
1. No. It should be O(n + k log k) because finding the kth smallest
element of an array of size n is O(n), using the Median of Medians
algorithm; see
http://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm.
2. Assuming that the entries in A are distinct and so are the entries
in B, we can handle the equality of sums case:
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
output ia, ib, A(ia)+B(ib)
else if A(ia + 1) + B(ib) < A(ia) + B(ib + 1) then
ib = ib + 1
output ia, ib, A(ia)+B(ib)
else // equality case
ia = ia + 1
ib = ib + 1
output ia-1, ib, A(ia-1)+B(ib)
output ia, ib-1, A(ia)+B(ib-1)
end if
end for
Dave
On Oct 16, 6:20 am, "coolfrog$" <dixit.coolfrog.div...@gmail.com>
wrote:
> @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"- 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
