Mathemagicians
Time limit1sMemory limit512 MB
Given two red/blue colorings of a circle of n people, decide whether repeated moves, where one person copies a neighbor's color, can turn the first coloring into the second.
- Level
Medium7 of 10
- Topics
- String, Greedy, Implementation, Math
- Solved
- No attempts yet
Problem
There are n mathemagicians standing in a circle. Each mathemagician wears either a blue hat or a red hat. A mathemagician can cast a color change charm which changes the color of their hat to the same color as the hat of the mathemagician directly to the left or to the right of them (the caster of the spell may choose which one of them). Note that mathemagicians are polite people and do not like interrupting each other, so only one mathemagician at a time may perform mathemagic.
The mathemagicians are not happy with their current hat configuration, so they would like to use the color change charm repeatedly to enter another hat configuration. Time isn't an issue because they can conjure cookies to eat.
Input
The first line contains an integer n (3 ≤ n ≤ 105), the number of mathemagicians. The next contains a string of length n. If the ith mathemagician wears a blue hat in the beginning, the ith character of the string is 'B', otherwise the ith character is 'R'. Finally, the third line contains a string of length n. If the ith mathemagician would like to wear a blue hat in the end, the ith character of the string is 'B', otherwise the ith character is 'R'.
It is guaranteed that not every mathemagician is happy with their hat color in the beginning.
Output
Output "yes" if it is possible for the mathemagicians to achieve the desired hat configuration after a finite number of color change charms, otherwise output "no".