Google Codejam 2010 Solutions - Qualification - Zero Wind :: Jamie Wong
Problem 1: Snapper Chain
This is the one I screwed up, because I somehow overlooked the fact that each snap was simply equivalent to an binary increment of the snappers states. Instead, I did a foolish simulation, which did actually pass me the small test case. But anyway, the real solution is O(1).
For interest, here's what the snapper chain looks like in the first 30 iterations. The left side, labeled "P:" shows which of the snappers are powered, and the right side, labeled "S:" shows the current state of the snappers, with "#" being ON and "." being OFF in both cases. I did this so it would be easier to see the pattern. The first row is the initial set up, before any snaps.
Read full article from Google Codejam 2010 Solutions - Qualification - Zero Wind :: Jamie Wong
No comments:
Post a Comment