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 C be the current circle of life. Let C_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 (\oplus) operation. As such, C_1[i] = C[i-1] \oplus C[i+1].

Let us expand on this. C_2[i] = (C[(i-1)-1] \oplus C[(i-1)+1]) \oplus (C[(i+1)-1] \oplus C[(i+1)+1]), which simplifies to C_2[i] = (C[i-2] \oplus C[i]) \oplus (C[i] \oplus C[i+2]). To simplify this, we must note a few things about xor.

  • n \oplus n = 0
  • n \oplus 0 = n
  • xor is associative

This means we can simplify the above equation to C_2[i] = C[i-2] \oplus C[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] \oplus C[i+k]

This can be proven recursively: if k satisfies the above equation, then so does 2k.

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: \mathcal O(N \log T)


  • 2
    thomas_li  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 \mathcal{O}(N \log N \log T) with a big constant, but it can be constant optimized to pass. https://dmoj.ca/submission/5812412

  • 10
    Zander  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?

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

      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.

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

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

      A more optimized version would start at i=49.

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

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


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


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

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