@Dave
input: k=3
A B
1 6
3 7
6 9
output should be (1,1,7), (1,2,8), (2,1,9)
im getting output form above code
(1,1,7)
(2,1,9)
(3,1,12)
Dave i am still learning algorithms .. so if i am wrong.. don't be annoyed
plz....
thankyou in advance... take care..
On Sat, Oct 16, 2010 at 6:21 PM, Dave <[email protected]> wrote:
> @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$" <[email protected]>
> 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 <[email protected]> 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$" <[email protected]>
> > > 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <
> [email protected]>
> > > > > > > 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 [email protected].
> > > > > To unsubscribe from this group, send email to
> > > > > [email protected]<algogeeks%[email protected]>
> <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 [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<algogeeks%[email protected]>
> <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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [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?hl=en.
