@Algoose Yes, but the algoritm is not correct since we are not covering the condition where element is reused. Ex ia=1 and ib=1 If we increment ia to 2 then there may be a case where A(1)+B(1) is less than A(2)+B(1) but since 1 was denoted by ia which is now 2 hence we will never be able to check this. So algorithm ignores reuse of elements.
On Oct 27, 5:06 pm, Algoose chase <harishp...@gmail.com> wrote: > @Dave, > > I believe in the first "if" clause ib must be incremented > in the "else if" clause ia must be incremented. > > is that right ? > > > > On Sat, Oct 16, 2010 at 6:21 PM, Dave <dave_and_da...@juno.com> 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_selectio... > > . > > > 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> > > > > <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> > > <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. -- 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.
