@Harish Your understanding is correct. By reuse I meant that A(1) after being used in A(1)+ B(1) combination can be reused in A(1)+B(2) if it fulfills the criteria. Dave gave an algorithm that used A(1) once and did not include the case where where A(1) can be used in any other combination.
On Oct 29, 12:17 pm, Harish U <[email protected]> wrote: > @amod > > I am not sure I understand what you are saying. > It is assumed that the K smallest Items(from both list A & B) are identified > and arranged in increasing order as the first step. > > Now A(1) and B(1) constitute "the least fare" round trip(since the list is > sorted) and we include that combination into our list of selected round > trips with minimal fare. Then we proceed by either including A(1)-B(2) or > A(2)-B(1) or both (if they add up to an equal value) > I am not clear about what you mean by reuse of elements. > Am I missing anything here ? If so a more clear example would help ! > > > > > > > > On Thu, Oct 28, 2010 at 10:26 AM, Amod <[email protected]> wrote: > > @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 <[email protected]> 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 <[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_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$" <[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%2bunsubscr...@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 [email protected]. > > > > > > To unsubscribe from this group, send email to > > > > > > [email protected]<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 [email protected]. > > > > To unsubscribe from this group, send email to > > > > [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. > > > -- > > 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%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 [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.
