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].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
