In that 3x3 example, pick any of the 3 columns as the starting point and any of the 3 columns as the ending point for a hole you dig in the 2nd row. Out of these the ones where the ending point, except for the ones where it is also the starting point, are not diggable - you have nowhere to stand to dig out the last section. This leaves 5 holes:
... .## ### ... #.# ### ... ##. ### ... ..# (ending in middle) ### ... #.. (ending in middle) ### The end of your hole is the where you will enter, because it's where you end up standing next to after finishing digging. In these cases, the floor of the hole is always one solid piece, so this doesn't matter. Now when you go to dig into the third level, the first three cases have no ways to dig anything. (But they are still valid cases to consider - if they were going to get you into the last level, or into a wider hole in the level below, they would work.) The last two cases each allow you to dig one of two possible 1-space-wide holes in the bottom level. ... ..# .## ... ..# #.# ... #.. #.# ... #.. ##. All of these lead to a solution where you have dug out 3 units. But the dynamic feature here is that you would combine the two middle cases (the #.# ones), because you're in the same hole - the upper layers no longer matter, except with regard to the total number of spaces dug. You would only have to consider this case once in going to the next level, if there was one. If there were ways to reach this state that had different numbers of spaces dug out, you would keep the one with the fewest spaces dug. On Wed, Jul 3, 2013 at 1:55 AM, wonjun <[email protected]> wrote: > Thanks for your reply, but I'm not able to understand it crystal clear. > A few questions:- > 1) In the beginning why is there O(C^2) of them? > I'm unable to understand the phrase "Consider all the open spaces you can > make(if necessary) and get into on the next level". > > 2) Could you explain it with a help of an example? Such as the following > test case: > (just a few steps leading to the solution) > > 3 3 1 > ... > ### > ### > > > > > 2013/7/3 Joseph DeVincentis <[email protected]> > >> 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. >> >> >> > > -- > 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%2BsYsMO2%3D85MPQv7BT-PnfJYGP%3DZWdXHfJnt25EhkzQ4Fiaw%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/CAMAzhzg3i-fBVH5kdy-ZXethbk0%2Bm7FPW37zRFO_J%3DKWLHdMSw%40mail.gmail.com. For more options, visit https://groups.google.com/groups/opt_out.
