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 at http://groups.google.com/group/google-code?hl=en.
