DMOPC '18 Contest 5 P4 - An Art Gallery Problem

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Bob is admiring a beautiful postmodern exhibit at the local art gallery. The exhibit consists of N colourful neon lamps in a line, labelled 1 to N, and each lamp can be one of two colours: a vibrant fuchsia or a soothing aquamarine.

The exhibit also happens to be interactive. There are N - 1 buttons that the visitors can press, labelled 1 to N - 1. Pressing button i will simultaneously change the colours of lamps i and i + 1 (from fuchsia to aquamarine or aquamarine to fuchsia), but only if those lamps are the same colour. Obviously, this represents the profound fragility and changeable nature of the human condition.

Bob notices that the colours of the lamps currently form pattern A. He thinks they would look good in pattern B, so he wants to know if it is possible to get to B from A by a sequence of zero or more button presses.

Constraints

Subtask 1 [20%]

1 \le N \le 20

Subtask 2 [20%]

1 \le N \le 2\,000

Subtask 3 [60%]

1 \le N \le 200\,000

Input Specification

The first line will contain one integer, N.
The second line will contain a string of N characters, either F (fuchsia) or A (aquamarine), pattern A.
The third and final line will contain a string of N characters, either F or A, pattern B.

Output Specification

Output YES if it is possible to get to B from A and NO otherwise.

Sample Input 1

6
FAAFFF
FFAAFF

Sample Output 1

YES

Sample Input 2

6
FAFAFA
AFAFAF

Sample Output 2

NO

Comments

There are no comments at the moment.