## Editorial for CCC '16 S5 - Circle of Life

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

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.

Time Complexity:

## Comments

You can also solve this problem with FFT :P the problem essentially reduces to calculating the dot product of all the cyclic shifts of an array with another array, which is a classic FFT problem. The final complexity is with a big constant, but it can be constant optimized to pass. https://dmoj.ca/submission/5812412

If I'm not mistaken, I think it should be : (the initial generation) instead of .

Could someone help me understand how you know that after 60 steps you have the answer?

To clarify d's explanation, we know that the upper bound for T is 10^15 according to the problem statement. The binary representation for the maximum T (10^15) is 11100011010111111010100100110001101000000000000000. We can see that the last bit is set at position 49. Thus the optimized version would start at i=49.

The algorithm is concerned about the 's in the binary representation of . Only the last bits of have the choice to not be .

A more optimized version would start at .

By the way, who posted this code and gave the answer away?

fataleagle

*fetalbagle

This comment is hidden due to too much negative feedback. Show it anyway.