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.
