In my solution (alas far too late to qualify) states were represented by three numbers, but could have been just two. state(col, stdig, enddig) where col is the current position stdig and endig are -1 for a virgin unaltered row, otherwise they are the start and end colums that have been dug out. There is a further restriction that, if stdig and enddig are non-positive, col must be equal to one or both of them. The theory being that after digging the block of rock out from the row above, the digger can only jump into the most recently dug block, any other dug blocks will be out of reach. And jumping the other way, into a normally vacant space would be pointless as the the dug out section would unreachable and therefor useless.
The actual implementation is an array of structures indexed by col and containing stdig and enddig. For virgin rows, the same object can be stored at all columns the digger can reach. For altered rows, the object is stored at either the stdig and enddig column. I added a third variable representing the distance to the floor in the cell below. That allowed me to only consider two rows at a time. Falling from one open cell to another just increments that distance to drop variable, and when it reaches the max drop limit that transition is no longer possible. It worked astonishly quickly, solving the large data problem in 3 seconds on a very slow computer. But there are a lot of specials cases and tricky code that needs to be written governing the transition from row to row and I'm guessing it took about 8 hours to finish. This was after spending uncounted hours completing a previous failed attempt that solved the small data sample but failed miserably on the large one and spending the rest of a very restless night working out details on how the darn thing could be solved. That there are people who can work out the details and get this coded and turned in in less than two hours is mind boggling. Has anyone considered the possibility that we are competing with automatons developed by some advanced civilization :) On Wednesday 30 September 2009 01:54:56 Bharath Raghavendran wrote: > For round 2 problem B, the code analysis suggests states as (i, j, start, > end). Can we have the states as just (i, start, end)? Is the value of j > important? we can just move without adding to the value of d. > > In case, there are pits in between, the states would be broken down .. for > example when we have the following > ...... > .##.#. > in the first row, the states would be (1, 1, 4) and (1, 4, 6) > > Would it work ? > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
