## 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: Riolku

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: • commented on Sept. 29, 2023, 5:11 p.m.

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

• commented on Jan. 28, 2020, 1:34 p.m.

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

• commented on Feb. 24, 2016, 4:57 a.m.

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

• commented on Aug. 2, 2020, 9:09 p.m.

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.

• commented on Feb. 24, 2016, 3:25 p.m. edit 2

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?

• commented on Feb. 24, 2016, 3:44 p.m.

fataleagle

• commented on Feb. 25, 2016, 3:57 a.m.

*fetalbagle

• commented on Feb. 25, 2016, 6:17 p.m.

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