I was thinking the same way as Jacob to treat it as a N-bit binary number, then thing will be much easier.
So N is number of snappers and K0 is a mount of time the finger snaps to turn on the lights So N:K 1:2 2:4 3:8 4:16 This way I can check if the snaps actually make the lights on or not. I though it would work fine as a super bonehead solution at first, but I would get stuck when the amount of snaps went beyond the amount it takes to turn the light on start from initial condition (all 0s). On May 9, 10:06 pm, Jacob Lyles <[email protected]> wrote: > I think it is simplist to pretend the snaps are not snaps, but bits in > an N-bit binary number. When you get to all 1s, it is on. > > On Sun, May 9, 2010 at 6:17 PM, Gustavo Pacianotto Gouveia > > > > <[email protected]> wrote: > > Yeah... the way to conclude the solution for me was a little diferrent to, > > but it is always the study of the cycles.. > > I deduced from the same thinking of tower of hanoi: > > Let be F(n) the number of snaps to turn the light on: > > when you add a snapper, to turn the light on, we need: > > 1:to energise this snapper --> F(n-1) snaps > > 2:to turn this on -->1 snap > > 3:to reenergise again --> F(n-1) snaps > > so F(n) = 2F(n-1)+1 > > 2F(n-1) = 4F(n-2)+2 > > .... > > 2^(n-1)F(1) = 2^n*0+2^(n-1) // F(0) = 0 > > -------------------------------------- > > F(n) = 2^n-1 => so, after 2^n-1 snaps the light will be on. one more snap > > and we have the inicial case. => we have a cycle of 2^N snaps and the ON > > state is the 2^N-1 state of every cycle... > > > 2010/5/9 Dhruva Sagar <[email protected]> > > >> Ok, it seems that the logic I happened to deduce was a little (subtle) > >> different than everyone elses. > >> For 2 snappers this is how the state changes > >> 0 0 > >> snap > >> 1 0 > >> snap > >> 0 1 > >> snap > >> 1 1 > >> So the above shows that for 2 snappers the light turns on in 3 snaps = > >> 2^N-1 snaps. But then when you look at the sample input output given in the > >> problem statement I saw that there was this test case : 4 47, which implies > >> that K can also be greater than 2^N-1. So lets see what happens of that is > >> the case > >> 0 0 > >> snap > >> 1 0 > >> snap > >> 0 1 > >> snap > >> 1 1 > >> snap > >> 0 0 > >> snap > >> 1 0 > >> snap > >> 0 1 > >> snap > >> 1 1 > >> So now in the above pattern you will see that although the pattern > >> repeats, this time it actually takes 4 = 2^N more snaps to bring it back to > >> the ON state. > >> So the first time it takes 2^N-1, and from then onwards every 2^N snaps it > >> will turn on again. > >> hence I deduced this simple formula, for the light to be on : > >> k = 2^N-1 + (Some number) * 2^N > >> From this then I simply deduced that > >> When (k - 2^N - 1) % (2^N) == 0, the snapper is ON :). Although this is > >> pretty much the same as others, I think this way is slightly easier to > >> understand, at least it is for me. > >> On Mon, May 10, 2010 at 06:14, Gustavo Pacianotto Gouveia > >> <[email protected]> wrote: > > >>> both are exactly the same solution.. think.. how to calculate this? > >>> " > >>> ... The solution to the problem is then very simple. The answer is "ON" > >>> if and only if the rightmost N bits of K are 1. ... > >>> " > >>> the rightmost N bits are represented as: 2^{N}-1 = 000...000001111...11 > >>> (N ones) > >>> (2^N-1) & (K) == 2^N-1 <--- it doesn't matter in what cycle it is.. > >>> just the relative position into the cycle (the last one) > >>> <=> (2^N-1)&(K+1) == 0 <=> (K+1)%(2^N) == 0 > >>> and verifying the statement: > >>> " > >>> ... The formula is ( Number of clicks)+1 divided by (2^(number of > >>> snappers) should be an integer number. > >>> If anyone really interested i may include how to deduce the formula ... > >>> " > >>> is equal to: (K+1)%(2^{N}) == 0 <--- if it is on the right place of the > >>> cycle (the last one), and we add 1, then, we have a integer number of > >>> cycles.... > >>> both verify if the K is in the right place on the cycle.... and both are > >>> O(1) ... so, I don't think one is more elegant than the other. > > >>> 2010/5/9 David M. <[email protected]> > > >>>> I used that same formula to solve the problem too (I was looking the > >>>> interval of clicks the lamp switched on) and it worked perfect. But > >>>> reading > >>>> the contest analisys... i think analisys' solution is more elegant and > >>>> simply than mine... :) > > >>>> Well, the problem was solved and that's the important :D > > >>>> 2010/5/9 Abdelrhman Abotaleb <[email protected]> > > >>>>> Ok I'm want really to discuss it > >>>>> because I solve it using a very simple way. > >>>>> only single operation!!! :D :D > >>>>> I deduced a formula relates the number of snappers by the number of > >>>>> clicks > >>>>> if it satisfy the formula so the lamp is ON ;otherwise the lamp is off > > >>>>> Indeed this method is sooooooooooooooo efficient for the large data set > >>>>> input . > > >>>>> Really in the first I solve it straightforward using recursion > >>>>> algorithms and so on > > >>>>> The formula is ( Number of clicks)+1 divided by (2^(number of snappers) > >>>>> should be an integer number. > >>>>> If anyone really interested i may include how to deduce the formula > > >>>>> Good Luck > > >>>>> On Sun, May 9, 2010 at 9:26 AM, Varun Nischal <[email protected]> > >>>>> wrote: > > >>>>>> Hello all, > > >>>>>> 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. > > >>>>>> Thanks, > >>>>>> Varun > > >>>>>> -- > >>>>>> 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. > > >>>>> -- > >>>>> 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. > > >>>> -- > >>>> 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. > > >>> -- > >>> grato, > > >>> Gustavo Pacianotto Gouveia > > >>> LTI - Laboratório de Técnicas Inteligentes > >>> Escola Politécnica da Universidade de São Paulo > >>> [email protected] > >>> [email protected] > >>> [email protected] > > >>> -- > >>> 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. > > >> -- > > >> Thanks & Regards, > >> Dhruva Sagar. > > >> -- > >> 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. > > > -- > > grato, > > > Gustavo Pacianotto Gouveia > > > LTI - Laboratório de Técnicas Inteligentes > > Escola Politécnica da Universidade de São Paulo > > [email protected] > > [email protected] > > [email protected] > > > -- > > 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. > > -- > 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 > athttp://groups.google.com/group/google-code?hl=en. -- 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.
