Let's call two patterns that are reachable from each other connected. (Notice that as button presses are reversible, if ~A~ is connected to ~B~, ~B~ is connected to ~A~.)

For the first subtask, we can consider each of the ~2^N~ possible patterns as a node in a graph. There is an edge between two nodes if one is reachable from the other through one button press. Then, we can do a DFS or BFS to determine if ~A~ and ~B~ are connected.

Time Complexity: ~\mathcal O(2^N)~

For the second subtask, we can try directly transforming ~A~ to ~B~. A method of converting lamp ~i~ to colour ~c~ is as follows: If ~i~ is already colour ~c~, then nothing needs to be done. Otherwise, we must convert lamp ~i+1~ to colour ~!c~ and then change the colours of lamps ~i~ and ~i+1~. If we then try converting all the lamps in ~A~ from left to right into their respective colours in ~B~, we will be successful if and only if ~A~ and ~B~ are connected. We can simulate this process in ~\mathcal O(N^2)~.

Time Complexity: ~\mathcal O(N^2)~

For the final subtask, let's call a pattern where the first ~0 \le k \le N~ lamps are alternating F's and A's, and the rest are A's, a base pattern. For example, AAAAAAAA, FAFAAAAA, AFAFAAAA, and AFAFAFAF are base patterns. Notice that any pattern can be transformed into a unique base pattern:

• If an F has at least two A's directly to its left, it can be moved to the left, two spaces at a time, by changing the colours like so: AAF -> FFF -> FAA.
• We can apply this procedure to all F's in the pattern in order from left to right, moving each one as far to the left as possible. If one F ends up beside the previous F, change them both to A. Otherwise, there will be exactly one A between this F and the previous F.
• As no two F's will end up beside each other and the remaining F's will be separated by single A's and pushed as far left as possible, we will end up with a base pattern.

If ~A~ and ~B~ have the same base pattern, they are connected: we can transform ~A~ to its base pattern, then reverse the transformation from the base pattern to ~B~. Additionally, if their base patterns are different, they are not connected: Let the number of F's in even-numbered positions of a pattern be ~nEven~ and the number of F's in odd-numbered positions be ~nOdd~. Since each button press either adds 1 to both ~nEven~ and ~nOdd~ or subtracts 1 from both, ~nOdd - nEven~ must be the same for two patterns in order for them to be connected. Therefore, as each of the ~N+1~ possible base patterns has a different ~nOdd - nEven~, no two of them are connected.

Thus, ~A~ and ~B~ are connected if and only if their base patterns are the same. We can find their base patterns by direct simulation in ~\mathcal O(N^2)~ or by using a stack and counter to keep track of the positions of the F's and the number of A's between the current and previous F's in ~\mathcal O(N)~.

Time Complexity: ~\mathcal O(N)~