# Editorial for CCC '16 S5: Circle of Life

Before reading the editorial, please make sure you've read the problem thoroughly multiple times and tried your best to solve it. Thanks!

Proceed to Editorial

Proceed to Editorial

_{n}denote the nth generation of the circle, and C

_{n}[i] be the ith cell of the nth generation of the circle. Note that the condition that exactly one neighbour is alive is the bitwise xor (^) operation. As such, `C

_{1}[i] = C[i - 1] ^ C[i + 1]`. Let us expand on this. `C

_{2}[i] = (C

_{1}[(i - 1) - 1] ^ C

_{1}[(i - 1) + 1]) ^ (C

_{1}[(i + 1) - 1] ^ C

_{1}[(i + 1) + 1])`, which simplifies to `C

_{2}[i] = (C

_{1}[i - 2] ^ C

_{1}[i]) ^ (C

_{1}[i] ^ C

_{1}[i + 2])`. To simplify this, we must note a few things about xor. - n ^ n = 0 - n ^ 0 = n - xor is associative This means we can simplify the above equation to `C

_{2}[i] = C

_{1}[i - 2] ^ C

_{1}[i + 2]`. If we continue to expand, we note that for every k which is a power of two, this holds: `C

_{k}[i] = C[i - k] ^ C[i + k]` Furthermore, since (C

_{a})

_{b}= C

_{a + b}, for every set bit in T, we advance it by that bit. For example, when T = 3, we advance by 1 and then by 2 to get our answer. Time Complexity: O(N log T)