I used Java's regular expression feature to solve A. I did feel guilty about taking unfair advantage of those poor suckers using a language without regular expression support. But it really wouldn't have been a very hard problem in any case.
For B, I did a raster scan of the map. For each cell I called a recursive function that followed the downhill path until it found a cell that had already been assigned to a basin or a sink. If it found a sink it assigned it a new basin identifier, then on the return path it assigned the identifier to the cell being processed. On Friday 04 September 2009 02:41:38 Miguel Oliveira wrote: > For problem A, I converted both the dictionary and the patterns to a > list of L bitmasks (one for each letter/position in the pattern). Each > bitmask has the bit i with 1 if the letter 'a'+i belongs to the word > or to the pattern in that position. Then, you just have to do at most > L bitwise "AND" operations per comparison. This solutions runs in ~0 > secs. > > For B, I did a kind of Flood Fill (http://en.wikipedia.org/wiki/ > Flood_fill), running from top to bottom, left to right. > > For C, I did the easiest Dynamic Programming (http://en.wikipedia.org/ > wiki/Dynamic_programming) approach. But it's easy to optimize it (it > still runs in about 0.1 secs). > > You may check my code. My username is mogers. > > > I think that the problems were easier than last year's qualification > round. Too bad because I could solve problems like these in the online > round 1 x) > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
