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
Let C be the current circle of life. Let Cn denote the nth generation of the circle, and Cn[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, `C1[i] = C[i - 1] ^ C[i + 1]`.
Let us expand on this. `C2[i] = (C1[(i - 1) - 1] ^ C1[(i - 1) + 1]) ^ (C1[(i + 1) - 1] ^ C1[(i + 1) + 1])`, which simplifies to `C2[i] = (C1[i - 2] ^ C1[i]) ^ (C1[i] ^ C1[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 `C2[i] = C1[i - 2] ^ C1[i + 2]`. If we continue to expand, we note that for every k which is a power of two, this holds:
`Ck[i] = C[i - k] ^ C[i + k]`
Furthermore, since (Ca)b = Ca + 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)