I think that solving B-small was tricky, but not that hard in the competition. B-large was more difficult.
Through experience you manage to write the code as simple and short as possible, which helps you to solve the problems faster. TopCoder helps a lot in this matter. I see that you already joined ;) On Sep 30, 4:01 pm, Ken Corbin <[email protected]> wrote: > 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 ?- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
