i got it,thanks a lot
On Thu, Apr 25, 2013 at 7:37 AM, Samuel Jawahar <[email protected]>wrote: > what is that, bridge problem? > > > On Thu, Apr 25, 2013 at 7:08 AM, Joseph DeVincentis <[email protected]>wrote: > >> Samuel, I don't have a book to recommend for that. But where I really >> learned how to do dynamic programming was Project Euler. >> >> >> On Wed, Apr 24, 2013 at 8:59 PM, Samuel Jawahar <[email protected]>wrote: >> >>> Thanks Joseph,can you please tell me the good book for Dynamic >>> programming >>> >>> >>> On Tue, Apr 16, 2013 at 12:46 AM, Joseph DeVincentis >>> <[email protected]>wrote: >>> >>>> To solve Treasure, first make sure that the problem has some solution. >>>> This requires: >>>> >>>> 1. There are enough copies of each key available somewhere. >>>> 2. There is some viable sequence of chest-openings to unlock each >>>> chest. >>>> >>>> (1) can be verified simply by counting all the keys and locks. >>>> (2) can be verified by a quick search in which you assume the keys >>>> don't break upon use. Here there is no branching; just keep track of the >>>> keys you have previously acquired and each time you get a new one, open all >>>> chests that open with that key and add any new keys to your inventory. If >>>> you can't open all the chests this way, then you'll never be able to solve >>>> the real problem. >>>> >>>> Much of the official analysis goes into proving that the above two >>>> conditions guarantee a solution to the real problem. >>>> >>>> Now for the cases not proven impossible, find the "lexicographically >>>> first" solution sequence by repeatedly opening the lowest-numbered locked >>>> chest which you have the key to open. After each step, repeat the analysis >>>> from (2) to ensure the remaining problem is still solvable. If it isn't, >>>> then you need to backtrack; go back to the state before that last move, and >>>> open the 2nd (or 3rd, etc. as necessary) chest instead. >>>> >>>> Because we ensure that the problem is solvable after each move, we know >>>> that at least one of those chests leads to a solution, so we never have to >>>> backtrack multiple steps, and the number of moves we need to attempt is >>>> limited to the square of the number of chests, so we will always find a >>>> solution, and always find it quickly. >>>> >>>> >>>> >>>> >>>> >>>> On Mon, Apr 15, 2013 at 2:55 PM, vivek dhiman >>>> <[email protected]>wrote: >>>> >>>>> Honestly. Content analysis for Treasure is too long. Only some time >>>>> during weekend can be given to understand. >>>>> Can someone explain in short ? >>>>> >>>>> Thanks >>>>> Vivek Dhiman >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Google Code Jam" group. >>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>> an email to [email protected]. >>>>> To post to this group, send email to [email protected]. >>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>> >>>>> >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Google Code Jam" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to [email protected]. >>>> To post to this group, send email to [email protected]. >>>> For more options, visit https://groups.google.com/groups/opt_out. >>>> >>>> >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Google Code Jam" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> To post to this group, send email to [email protected]. >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
