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]<google-code%[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]<google-code%[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]<google-code%[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]<google-code%[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.
