Editorial for CCC '16 S5 - Circle of Life - DMOJ: Modern Online Judge

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$ ~C~ be the current circle of life. Let $C_n$ ~C_n~ denote the $n$ ~n~th generation of the circle, and $C_n[i]$ ~C_n[i]~ be the $i$ ~i~th cell of the $n$ ~n~th generation of the circle. Note that the condition that exactly one neighbour is alive is the bitwise xor ( $\oplus$ ~\oplus~) operation. As such, $C_1[i] = C[i-1] \oplus C[i+1]$ ~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 n = 0~
$n \oplus 0 = n$ ~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]$ ~C_2[i] = C[i-2] \oplus C[i+2]~. If we continue to expand, we note that for every $k$ ~k~ which is a power of two, this holds:

$C_k[i] = C[i-k] \oplus C[i+k]$ ~C_k[i] = C[i-k] \oplus C[i+k]~

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

Furthermore, since $(C_a)_b = C_{a+b}$ ~(C_a)_b = C_{a+b}~, for every set bit in $T$ ~T~, we advance it by that bit. For example, when $T = 3$ ~T = 3~, we advance by $1$ ~1~ and then by $2$ ~2~ to get our answer.

Time Complexity: $\mathcal O(N \log T)$ ~\mathcal O(N \log T)~

Comments

3

thomas_li commented on Sept. 29, 2023, 5:11 p.m. ← edited →

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)$ ~\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$ ~T~ is $10^{15}$ ~10^{15}~ according to the problem statement. The binary representation for the maximum $T$ ~T~ ( $10^{15}$ ~10^{15}~) is 11100011010111111010100100110001101000000000000000. We can see that the last bit is set at position $49$ ~49~. Thus the optimized version would start at $i = 49$ ~i = 49~.

11

d commented on Feb. 24, 2016, 3:25 p.m. ← edit 2 →

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

A more optimized version would start at $i=49$ ~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.

fataleagle

21

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

*fetalbagle

-22

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

*fatimligle

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