@everyone: is there one planning to participate in http://byoc.in/13/tournaments.html Kindly let me know.(This may not a proper thread to post, but please excuse me this time).
On Sun, Jun 20, 2010 at 1:18 AM, Chakravarthi Muppalla <chakri...@gmail.com>wrote: > Hi anand, > could you please enlighten on the running time of the code? > > > On Sun, Jun 20, 2010 at 1:12 AM, Anand <anandut2...@gmail.com> wrote: > >> Here is my approach for solving this problem using DP. >> >> http://codepad.org/Op41weg5 >> >> <http://codepad.org/Op41weg5> >> >> On Thu, Jun 17, 2010 at 6:33 AM, Chakravarthi Muppalla < >> chakri...@gmail.com> wrote: >> >>> I think that we need to go by dynamic programming. >>> Ex: 1,3,7,4,9 T=23 >>> Sort: 1,3,4,7,9 >>> subtract max value from T(23-9=14 ) >>> find Best Solution for (14) --> sub (14-9 = 5), Search for 5.(5-4 = 1) So >>> Answer would be: 9,9,4,1 >>> Search can be binary search as the array is already sorted. >>> At every step best solution for the specified number could be saved in a >>> hash table for any further references. >>> >>> >>> Thanks & Regards, >>> Chakravarthi. >>> >>> >>> >>> >>> >>> On Thu, Jun 17, 2010 at 6:10 PM, Rohit Saraf < >>> rohit.kumar.sa...@gmail.com> wrote: >>> >>>> Yes right, i forgot the "1" >>>> >>>> -------------------------------------------------- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>> >>>> >>>> On Thu, Jun 17, 2010 at 6:05 PM, Dave <dave_and_da...@juno.com> wrote: >>>> >>>>> No. The greedy algorithm also works on the U.S. coinage system, where >>>>> the coins are 1, 5, 10, 25. Again, the rule is that there must be a 1 >>>>> unit coin, and each coin has at least twice the value of the >>>>> preceeding one. >>>>> >>>>> Dave >>>>> >>>>> On Jun 16, 11:34 pm, Rohit Saraf <rohit.kumar.sa...@gmail.com> wrote: >>>>> > @Dave: The greedy will only work if the coins are k,2k,3k,4k,.... nk >>>>> without >>>>> > any of these missing >>>>> > Clear? >>>>> > (Perhaps i did not write it clearly as i was on mobile) >>>>> > -------------------------------------------------- >>>>> > Rohit Saraf >>>>> > Second Year Undergraduate, >>>>> > Dept. of Computer Science and Engineering >>>>> > IIT >>>>> > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>> > >>>>> > >>>>> > >>>>> > On Thu, Jun 17, 2010 at 10:00 AM, Dave <dave_and_da...@juno.com> >>>>> wrote: >>>>> > > The greedy algorithm doesn't work, e.g., when the coins are 1, 5, >>>>> and >>>>> > > 8 units, and you want to make 15 units. In this case, the greedy >>>>> > > algorithm would choose 8, 5, 1, 1, whereas the optimal is 5, 5, 5. >>>>> I >>>>> > > believe the criterion for the greedy algorithm are that the >>>>> smallest >>>>> > > coin be 1 unit and each successive coin be at least twice the value >>>>> of >>>>> > > its predecessor. >>>>> > >>>>> > > Dave >>>>> > >>>>> > > On Jun 16, 9:19 pm, Rohit Saraf <rohit.kumar.sa...@gmail.com> >>>>> wrote: >>>>> > > > If the coins are all multiple of some number k, you can greedily >>>>> give >>>>> > > > as much as possible to the higher domination. Otherwise still, >>>>> there >>>>> > > > is an optimal substructure and u can make a recurrence and use >>>>> > > > memoization(i.e. DP) >>>>> > >>>>> > > > -- >>>>> > > > -------------------------------------------------- >>>>> > > > Rohit Saraf >>>>> > > > Second Year Undergraduate, >>>>> > > > Dept. of Computer Science and Engineering >>>>> > > > IIT >>>>> > > > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>> > >>>>> > > -- >>>>> > > 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.- 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<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Thanks, >>> Chakravarthi. >>> >>> -- >>> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks, > Chakravarthi. > -- Thanks, Chakravarthi. -- 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.
