You can take a look at my solution for problem D, which runs in ~1:30 (in python) for both small and large sets. (my username is caethan, btw).
A (relatively) short description: Generate an array of size 2*D + 1. The center is where you are, you need to check line of sight on all the other squares to see if there's an image of you there. Set the elements of the array to 1 to mark that you need to check them. Superimpose a distance cutoff to get rid of the corner squares that are past your visual range (set them to 0). The line of sight algorithm works like this: first, you need to figure out which squares your line of sight is going to pass through on the way to your destination square. This is just a matter of arithmetic, and it generates a list of squares. So for line of sight to, say, (4, 4), it'll give you a list of (1, 1), (2, 2), (3, 3), and (4, 4). This algorithm is relatively expensive, so it caches its results as it goes to save execution speed. Then, you walk through the list of squares in the hall of mirrors. Start a probe in your starting square and try to move to the next square in your list. If your destination square is empty or has you in it, then just move your probe there. If there's a mirror, but you're only moving in one direction (i.e. from (1,1) to (1,2)), then keep the probe in the same square but flip direction. If there's a mirror and you're moving in two directions (i.e., from (1,1) to (2,2)), there's a corner and you need to handle the corner cases as described in the problem state. Once you're done moving, check your final square to see if it's the same as your starting square. If so, you can see an image of you there, so mark it in your visual array. A naive version of this algorithm (which was the first one I built, and had to sleep on to figure out how to fix) runs as O(N^2), is too slow, since it checks all of ((D*2)+1)**2 squares. What you can do, though, is walk out from your starting destination one distance step at a time, and check, say, (1,1), and then keep the line of sight going until you hit something, and clear all squares along that diagonal, which will contain at most one image. That decreases the number of distinct squares you have to check and lowers the run speed to (I believe, though I haven't checked explicitly) O(N logN). Hope this helps! ~Brett On Sunday, April 15, 2012 3:55:21 PM UTC-5, Balaji Krishna wrote: > > Hey guys, for this problem, I came up with a program for the small > input, and it was relatively fast, certainly less than a minute. I > used the smae algorithm for the large input but then it took about 20 > mins, so was wondering what algorithms you found to work quickest. > > Also, I was wondering if anybody could explain a possible algorithm > for problem d in the same round. > > If you could answer either of these questions, that'll be really > great. Thanks -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/Zdf2zy19U-0J. 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.
