PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
First solution: If we choose an arbitrary assignment for any two adjacent cells of the original state, then the entire rest of the state can be determined from the current state. For example, if we choose values for original[0] and original1, then current1 is defined as original[0]^original1^original2 (where ‘^’ is exclusive or), thus original2=original[0]^original1^current1. Repeating the process allows us to determine all cells of the original state. Depending on the initial assignment, this may or may not yield a valid solution. There are only 4 initial assignments to try, and we simply count the number that yield valid solutions.
Second solution: Consider the state of the game as the binary representation of an N-bit integer. Let A represent the original state of the game, and B the current state. Then the simulation step simply implies that B=F(A), where F(A)=(A<<<1)^A^(A>>>1), ‘<<<’ is left rotation (not left shift), and ‘>>>’ is right rotation. Now consider these cases:
-
If N is divisible by 3, then F(011011…011011)=000…000, hence the solution cannot be unique (becase F(X^Y)=F(X)^F(Y), there will either be 0 solutions, or 4 solutions). Denote G(B)=(B<<<1)^(B<<<2)=A^(A<<<3). Now G(B)^(G(B)<<<3)^(G(B)<<<6)^…^(G(B)<<<(N-3)) should equal 0. If this is the case, then there are multiple solutions. Otherwise there is no solution.
-
If N has a remainder of 1 when divided by 3, then F(110110…1101101)=1000…000, hence there is always a unique solution, given by B^(B<<<1)^(B<<<3)^(B<<<4)^(B<<<5)^…^(B<<<(N-3))^(B<<<(N-1)).
-
If N has a remainder of 2 when divided by 3, then F(101101…10110110)=1000…000, again implying a unique solution, given by B^(B<<<2)^(B<<<3)^(B<<<5)^(B<<<6)^…^(B<<<(N-2))^(B<<<(N-1)).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.