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 <dhruva.sa...@gmail.com>
> 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 <
> gustavo.paciano...@gmail.com> 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. <b4r...@gmail.com>
>>
>> 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 <profvip.abota...@gmail.com>
>>>
>>> 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
>>>> <diehard.co...@gmail.com>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 google-c...@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com>
>>>>> .
>>>>> 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 google-c...@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com>
>>>> .
>>>> 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 google-c...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com>
>>> .
>>> 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
>> gustavo.gouv...@poli.usp.br
>> gl_lg...@hotmail.com
>> gustavo.paciano...@gmail.com
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "google-codejam" group.
>> To post to this group, send email to google-c...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com>
>> .
>> 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 google-c...@googlegroups.com.
> To unsubscribe from this group, send email to
> google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegroups.com>
> .
> 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
gustavo.gouv...@poli.usp.br
gl_lg...@hotmail.com
gustavo.paciano...@gmail.com
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to google-c...@googlegroups.com.
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
