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_1[(i - 1) - 1] \oplus C_1[(i - 1) + 1]) \oplus (C_1[(i + 1) - 1] \oplus C_1[(i + 1) + 1]), which simplifies to C_2[i] = (C_1[i - 2] \oplus C_1[i]) \oplus (C_1[i] \oplus C_1[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_1[i - 2] \oplus 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] \oplus 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: \mathcal O(N\log T)


Code by FatalEagle, refactored into D by Kirito.

import std.stdio;

int N;
long T;
char[100001] S;
int[100001] A, B;

void step(int k) {
    int pos=(cast(long)1<<k)%N;
    int pos2=(N-pos)%N;
    foreach(i;0..N)
        B[i]=A[(i+pos)%N]^A[(i+pos2)%N];
    foreach(i;0..N)
        A[i] = B[i];
}

void main() {
    scanf("%d%ld", &N, &T);
    scanf("%s", &S);
    foreach(i;0..N)
        A[i]=S[i]-'0';
    for(int i=60; i>=0; i--)
        if((T>>i)&1)
            step(i);
    foreach(i;0..N)
        printf("%d", A[i]);
    printf("\n");
}

Comments


  • 5
    leonzalion  commented on Jan. 28, 2020, 8:34 a.m.

    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])

    If I'm not mistaken, I think it should be C: C_2[i] = (C[(i-1)-1]⊕C[(i-1)+1])⊕(C[(i+1)-1]⊕C[(i+1)+1]) (the initial generation) instead of C_1.


  • 9
    Zander  commented on Feb. 23, 2016, 11:57 p.m.

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


    • 4
      marethyu  commented on Aug. 2, 2020, 5: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.


    • 10
      d  commented on Feb. 24, 2016, 10:25 a.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?


      • 14
        awaykened  commented on Feb. 24, 2016, 10:44 a.m.

        fataleagle


        • 16
          jeffreyxiao  commented on Feb. 24, 2016, 10:57 p.m.

          *fetalbagle


          • -11
            bobhob314  commented on Feb. 25, 2016, 1:17 p.m.

            This comment is hidden due to too much negative feedback. Click here to view it.