Editorial for DMOPC '18 Contest 5 P4 - An Art Gallery Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
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
A's, and the rest are
A's, a base pattern. For example,
AFAFAFAF are base patterns. Notice that any pattern can be transformed into a unique base pattern:
- If an
Fhas 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
Fends up beside the previous
F, change them both to
A. Otherwise, there will be exactly one
Fand the previous
- 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)~