## Editorial for DMOPC '18 Contest 5 P4 - An Art Gallery Problem

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: AvaLovelace

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

For the first subtask, we can consider each of the 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 and are connected.

Time Complexity:

For the second subtask, we can try directly transforming to . A method of converting lamp to colour is as follows: If is already colour , then nothing needs to be done. Otherwise, we must convert lamp to colour and then change the colours of lamps and . If we then try converting all the lamps in from left to right into their respective colours in , we will be successful if and only if and are connected. We can simulate this process in .

Time Complexity:

For the final subtask, let's call a pattern where the first 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 and have the same base pattern, they are connected: we can transform to its base pattern, then reverse the transformation from the base pattern to . 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 and the number of F's in odd-numbered positions be . Since each button press either adds 1 to both and or subtracts 1 from both, must be the same for two patterns in order for them to be connected. Therefore, as each of the possible base patterns has a different , no two of them are connected.

Thus, and are connected if and only if their base patterns are the same. We can find their base patterns by direct simulation in 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 .

Time Complexity: