Re: [gcj] Discussion about Snapper Chain
Abdelrhman Abotaleb, * * You are solving the problem in the same way by deriving the formula. Even I came to the same conclusion that ( Number of clicks)+1 divided by (2^(number of snappers) should be an integer number. But I'm interested to know what is your method of deriving the formula.. On Mon, May 10, 2010 at 12:56 AM, Abdelrhman Abotaleb profvip.abota...@gmail.com wrote: 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 sooo 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.comwrote: 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.comgoogle-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.comgoogle-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. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Discussion about Snapper Chain
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. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
Re: [gcj] Discussion about Snapper Chain
Here's a simple analysis: Imagine 3 lights plugged into a wall at the right and the state is 1 if it is on, and 0 if it is off. so for each 'click' the states will be: 00 0 0 10 0 1 20 1 0 30 1 1 41 0 0 51 0 1 61 0 1 71 1 1 80 0 0 90 0 1 10 0 1 1 And so on. You can see a pattern here: that for the light to be on, all the switches need to be set to 1. And as a binary number - so: for 1 snappers the number is 1 which is 1 in decimal for 2 snappers the number is 1 1 which is 3 in decimal for 3 snappers the number is 1 1 1 which is 7 in decimal. So can you see the pattern. for N snappers, all the digits in binary are 1 for the number (2^N)-1. As this wraps around we bring in modulus which is where we see that k % 2^N must be (2^N)-1. On 9 May 2010 20:06, Douglas Drumond drumond.doug...@gmail.com wrote: 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. You should check contest analysis: http://code.google.com/codejam/contest/dashboard?c=433101#s=a -- 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.comgoogle-code%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/google-code?hl=en. -- Abizer -- 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.
Re: [gcj] Discussion about Snapper Chain
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 sooo 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.comwrote: 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.comgoogle-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. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
Re: [gcj] Discussion about Snapper Chain
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 sooo 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.comwrote: 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.comgoogle-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.comgoogle-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. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
Re: [gcj] Discussion about Snapper Chain
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...0...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 sooo 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.comwrote:
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.comgoogle-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.comgoogle-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.comgoogle-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.
Re: [gcj] Discussion about Snapper Chain
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...0...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 sooo 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.comwrote:
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.comgoogle-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.comgoogle-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.comgoogle-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
