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.

Authors: AvaLovelace

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}\left(2^N\right)

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}\left(N^2\right).

Time Complexity: \mathcal{O}\left(N^2\right)

For the final subtask, let's call a pattern where the first 0 \leq k \leq 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 at 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\left(N^2\right) 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\left(N\right).

Time Complexity: \mathcal{O}\left(N\right)


Comments

There are no comments at the moment.