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

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

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**between this`A`

`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:**

## Comments