It's not really a recurrence-based DP, but a state-based one. The DP works as follows:
Consider all the open spaces you can make (if necessary) and get into on the next level. There are O(C^2) of them - pick any two spaces, possibly both the same one, as the ends of the open space. Some of these are invalid - either they are adjacent to existing holes (and so you should use the longer space including the holes instead), and some of them cannot be dug out according to the rules. But you can evaluate each one as to its validity, as well as the number of holes you have to dig to open it up (which is simply the number of initially filled spaces within the space you select). In some cases, you might be able to dig the same holes in left-to-right or right-to-left order, which makes a difference where you enter the hole - which in turn matters if the next layer below that one has holes within the region you are entering. In any case, you'll end up with a set of cases for spaces you can end up in on the next level, along with which part of the "floor" of that space you ended up in, if it is divided into more than one piece, and the number of spaces dug out so far. If your entry point was directly above a hole in the next layer, then you will instead fall more than one layer. For these cases, determine where you end up, and whether the fall is safe. If it is, determine the limits of the space on the layer you land in; because of your fall, you didn't have any opportunity to extend this hole, and then set this case aside to be considered later, once you have found other ways to reach this level. Now, for each of the cases on level 2, repeat the same algorithm. However, now you might have multiple ways to reach the same state starting from different level 2 cases. Compare all results that end up in the same space and the same floor section of level 3, and just keep the one with the fewest spaces dug out so far. Each state consists of your current row, the ends of the hole within that row that you occupy, and where within the hole that you are, and the state has an accompanying score, the minimum number of spaces you need to dig to reach the state. Process all the ones in one row, then all the ones in the next row and so on. On Tue, Jul 2, 2013 at 4:10 PM, wonjun <[email protected]> wrote: > I have tried to solve Digging > Problem<https://code.google.com/codejam/contest/204113/dashboard#s=p1&a=1> and > have gotten quite stuck. > When I read the problem, I thought Dijkstra's Algorithm would beat it, and > have tried to do so. But it seems my implementation has many flaws, and is > not giving the required output. > > > Now, when I read the contest analysis - and I haven't understood the > recurrence behind the DP solution; given the states (as in the analysis) > > So in short: > 1) Is there a way to solve this using Dijkstra? > 2) What's the recurrence behind the DP solution? > > Kindly help me. > Thanks. > -- > 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]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CAA0%2BsYu2_iGzKjbxsTcwRLefRNAfMzoE3LrX0f-7YsUZMtoU%2BA%40mail.gmail.com > . > 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]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMAzhzhDttzrG4pYLAnDPi8798ikPfM5_6OvTVZ6h9V3ux%3Dnuw%40mail.gmail.com. For more options, visit https://groups.google.com/groups/opt_out.
