Approach #1: Reduce Search Space [Accepted]
As the search space is very large ( states of lights, naively operation sequences), let us try to reduce it.
The first 6 lights uniquely determine the rest of the lights. This is because every operation that modifies the -th light also modifies the -th light.
Also, operations commute: doing operation A followed by B is the same as doing operation B followed by A. So we can assume we do all the operations in order.
Finally, doing the same operation twice in a row is the same as doing nothing. So we only need to consider whether each operation was done 0 or 1 times.
Say we do the -th operation times. Let's first figure out what sets of residues are possible: that is, what sets ( ) are possible.
Because and , if , or if , it isn't possible. Otherwise, it is possible by a simple construction: do the operations specified by , then do operation number 1 with the even number of operations you have left.
For each possible set of residues, let's simulate and remember what the first 6 lights will look like, storing it in a Set structure
seen. At the end, we'll return the size of this set.
In Java, we make use of bit manipulations to manage the state of lights, where in Python we simulate it directly.
Time Complexity: . Our checks are bounded by a constant.
Space Complexity: , the size of the data structures used.
Approach #2: Mathematical [Accepted]
Intuition and Algorithm
As before, the first 6 lights uniquely determine the rest of the lights. This is because every operation that modifies the -th light also modifies the -th light, so the -th light is always equal to the -th light.
Actually, the first 3 lights uniquely determine the rest of the sequence, as shown by the table below for performing the operations a, b, c, d:
- Light 1 = 1 + a + c + d
- Light 2 = 1 + a + b
- Light 3 = 1 + a + c
- Light 4 = 1 + a + b + d
- Light 5 = 1 + a + c
- Light 6 = 1 + a + b
So that (modulo 2):
- Light 4 = (Light 1) + (Light 2) + (Light 3)
- Light 5 = Light 3
- Light 6 = Light 2
The above justifies taking without loss of generality. The rest is now casework.
Let's denote the state of lights by the tuple . The transitions are to XOR by or .
When , all the lights are on, and there is only one state . The answer in this case is always 1.
When , we could get states , , , or . The answer in this case is either for respectively.
When , we can manually check that we can get 7 states: all of them except for . The answer in this case is either for respectively.
When , we can get all 8 states. The answer in this case is either for respectively.
- Time and Space Complexity: . The entire program uses constants.
Analysis written by: @awice.