Editorial for CCC '16 S5 - Circle of Life
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be the current circle of life. Let denote the th generation of the circle, and be the th cell of the th generation of the circle. Note that the condition that exactly one neighbour is alive is the bitwise xor () operation. As such, .
Let us expand on this. , which simplifies to . To simplify this, we must note a few things about xor.
- xor is associative
This means we can simplify the above equation to . If we continue to expand, we note that for every which is a power of two, this holds:
Furthermore, since , for every set bit in , we advance it by that bit. For example, when , we advance by and then by to get our answer.