Hi Anil , Have completed the topcoder Marathon match problem? jawahar On Thu, Sep 10, 2009 at 8:07 PM, Anil Kishore <[email protected]> wrote:
> You may wanna try the Problem in Todays TopCoder SRM , > http://www.topcoder.com/stat?c=problem_statement&pm=10620 > > <http://www.topcoder.com/stat?c=problem_statement&pm=10620>Its a good > problem. Give it a try :) ,, Don't worry, we are there to explain in case. > > - Anil Kishore, > IIIT-Hyderabad. > > > On Thu, Sep 10, 2009 at 6:52 PM, samuel jawahar > <[email protected]>wrote: > >> Dynamic programing gives the effective way of recursion, with table that >> contains the previous results >> Regards >> Jawahar >> >> >> On Thu, Sep 10, 2009 at 5:55 PM, amit jain <[email protected]> wrote: >> >>> thanx buddy.... >>> >>> On Thu, Sep 10, 2009 at 2:11 PM, Mayank Jaiswal <[email protected]>wrote: >>> >>>> Hi amit, >>>> >>>> I'll try to help you. >>>> Recall the definition of dynamic programming. >>>> *Dynamic programming is a method of solving complex problems by >>>> breaking them down into simpler steps. >>>> * >>>> So, when solving a problem, think that whether you are solving same >>>> subproblem again and again or not. If yes, just find out a way in which you >>>> can store the result of smaller problems and use it further in the >>>> algorithm >>>> . >>>> >>>> By the term *optimal substructure*, we just mean that when you realise >>>> your bigger problem to be consisted of similar smaller subproblems, the >>>> solution to this subproblem will contribute to optimal solution of parent >>>> bigger problem...... it sounds confusing and complex ...i know. Just forget >>>> this. Practice a few problems .... Cormen (Introduction to algorithms) is a >>>> good book to learn. >>>> >>>> >>>> Solving some problems will automatically give you a feel of what to do >>>> .... its not a big deal as it sounds to be. Best of luck! >>>> >>>> Cheers, >>>> Mayank >>>> >>>> >>>> >>>> >>>> >>>> On Thu, Sep 10, 2009 at 1:55 PM, Anil Kishore <[email protected]>wrote: >>>> >>>>> >>>>> If you think of it as some standard step-by-step thinking, then it may >>>>> not work most of the time. By more practice, you will develop the art >>>>> of DPing ;) . . . Its all about, 'remember your past to your memory >>>>> capacity' >>>>> >>>>> May be its something like this. , >>>>> -> Hmm the Problem looks good , lemme imagine as a big picture >>>>> -> I see, we need to solve this way (think as if you are explaining the >>>>> answer to your friend) >>>>> -> Oh, I am doing the same kind of things and need to solve similar >>>>> sub-problems >>>>> -> Aha!, its recursion . . I knew it ! , lemme write the function >>>>> corresponding to the recurrence relation >>>>> -> oh .. wait, am I calling the function more than once, with same >>>>> parameters.. yaya, lemme memoize >>>>> -> Aaah!, i figured out the order in which the subproblems are solved . >>>>> . >>>>> -> Aha !, its DP . . I knew it ! :p >>>>> >>>>> If you are in doubt, you can simply memoize (even if its not needed). >>>>> May be someone who can solve advanced DP in less time, can explain >>>>> better. >>>>> >>>>> - Anil Kishore >>>>> >>>>> >>>>> On Thu, Sep 10, 2009 at 1:41 PM, amit jain <[email protected]> wrote: >>>>> >>>>>> okk >>>>>> how do you think optimal substructure step ? >>>>>> On Thu, Sep 10, 2009 at 1:34 PM, Hawston LLH <[email protected]>wrote: >>>>>> >>>>>>> i guess only practice more and get more familiar with it is the only >>>>>>> useful trick if there is any. :) >>>>>>> >>>>>>> On Thu, Sep 10, 2009 at 3:57 PM, amit jain <[email protected]>wrote: >>>>>>> >>>>>>>> u know we have not enough time during competition and sol of dp >>>>>>>> looks like they will take 1 complete day.. >>>>>>>> now a days i m spending my whole day to solve a single dp problem >>>>>>>> like we had in qualification round. >>>>>>>> and i read out both clrs and as well as topcoder link >>>>>>>> so plz suggest me useful trick to solve them... >>>>>>>> thanks in advance.. >>>>>>>> On Wed, Sep 9, 2009 at 11:10 PM, Kaushalya Madhawa < >>>>>>>> [email protected]> wrote: >>>>>>>> >>>>>>>>> This is good! >>>>>>>>> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProgAnd >>>>>>>>> refering CLRS will be helpful >>>>>>>>> Regards, >>>>>>>>> Kaushalya Madhawa >>>>>>>>> http://kaumad.wordpress.com >>>>>>>>> http://most-wanted-stuff.blogspot.com >>>>>>>>> >>>>>>>>> twitter: http://twitter.com/kau_mad >>>>>>>>> skype: kau.mad >>>>>>>>> gtalk: kau.mad >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> On Wed, Sep 9, 2009 at 3:27 PM, Sagar Shah <[email protected] >>>>>>>>> > wrote: >>>>>>>>> >>>>>>>>>> Can anyone please suggest me some good tutorial/book to learn >>>>>>>>>> Dynamic Programming? >>>>>>>>>> >>>>>>>>>> Thanks >>>>>>>>>> Sagar Shah >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> -- >>>> Mayank Jaiswal >>>> B.Tech >>>> Final Year Student >>>> Computer Science and Engineering >>>> Indian Institute of Technology, Kharagpur >>>> >>>> D-220, Nehru Hall of Residence >>>> +91 97344 28874 >>>> http://www.linkedin.com/in/msjaiswal >>>> >>>> >>>> >>>> >>> >>> >>> >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" 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/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
