Here's a simple analysis: Imagine 3 lights plugged into a wall at the right and the state is 1 if it is on, and 0 if it is off.
so for each 'click' the states will be: 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 0 1 7 1 1 1 8 0 0 0 9 0 0 1 10 0 1 1 And so on. You can see a pattern here: that for the light to be on, all the switches need to be set to 1. And as a binary number -> so: for 1 snappers the number is 1 which is 1 in decimal for 2 snappers the number is 1 1 which is 3 in decimal for 3 snappers the number is 1 1 1 which is 7 in decimal. So can you see the pattern. for N snappers, all the digits in binary are 1 for the number (2^N)-1. As this wraps around we bring in modulus which is where we see that k % 2^N must be (2^N)-1. On 9 May 2010 20:06, Douglas Drumond <[email protected]> wrote: > > Is anyone interested in discussing the algorithm for Snapper Chain. > > What was the right approach to it? > > > > PS: I have seen some solved source code. But, would like to know about > the > > approach. > > > You should check contest analysis: > http://code.google.com/codejam/contest/dashboard?c=433101#s=a > > -- > 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]<google-code%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- Abizer -- 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.
