Codeforces Round #336 Marbles

E. Marbles

time limit per test: 

2 seconds

memory limit per test: 

256 megabytes

input: 

standard input

output: 

standard output

In the spirit of the holidays, Saitama has given Genos two grid paths of length n (a weird gift even by Saitama's standards). A grid path is an ordered sequence of neighbouring squares in an infinite grid. Two squares are neighbouring if they share a side.

One example of a grid path is (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 1) → (0, 1) → ( - 1, 1). Note that squares in this sequence might be repeated, i.e. path has self intersections.

Movement within a grid path is restricted to adjacent squares within the sequence. That is, from the i-th square, one can only move to the (i - 1)-th or (i + 1)-th squares of this path. Note that there is only a single valid move from the first and last squares of a grid path. Also note, that even if there is some j-th square of the path that coincides with the i-th square, only moves to (i - 1)-th and (i + 1)-th squares are available. For example, from the second square in the above sequence, one can only move to either the first or third squares.

To ensure that movement is not ambiguous, the two grid paths will not have an alternating sequence of three squares. For example, a contiguous subsequence (0, 0) → (0, 1) → (0, 0) cannot occur in a valid grid path.

One marble is placed on the first square of each grid path. Genos wants to get both marbles to the last square of each grid path. However, there is a catch. Whenever he moves one marble, the other marble will copy its movement if possible. For instance, if one marble moves east, then the other marble will try and move east as well. By try, we mean if moving east is a valid move, then the marble will move east.

Moving north increases the second coordinate by 1, while moving south decreases it by 1. Similarly, moving east increases first coordinate by 1, while moving west decreases it.

Given these two valid grid paths, Genos wants to know if it is possible to move both marbles to the ends of their respective paths. That is, if it is possible to move the marbles such that both marbles rest on the last square of their respective paths.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 1 000 000) — the length of the paths.

The second line of the input contains a string consisting of n - 1 characters (each of which is either 'N', 'E', 'S', or 'W') — the first grid path. The characters can be thought of as the sequence of moves needed to traverse the grid path. For example, the example path in the problem statement can be expressed by the string "NNESWW".

The third line of the input contains a string of n - 1 characters (each of which is either 'N', 'E', 'S', or 'W') — the second grid path.

Output

Print "YES" (without quotes) if it is possible for both marbles to be at the end position at the same time. Print "NO" (without quotes) otherwise. In both cases, the answer is case-insensitive.

Sample test(s)

input

7
NNESWW
SWSWSW

output

YES

input

3
NN
SS

output

NO

Note

In the first sample, the first grid path is the one described in the statement. Moreover, the following sequence of moves will get both marbles to the end: NNESWWSWSW.

In the second sample, no sequence of moves can get both marbles to the end.

这题模拟搜索的方法应该不难想到，复杂度O(n^2logn)，然而太慢。

考虑一种特例，即两个串表示的图形完全相同，只不过起始点和终点相反。在这种情况下可以断定是不能将两个球同时移动到终点的。

否则，假设两球能够被同时移动到终点，那么我们将两张图覆盖在一起，考虑移动过程的逆序，A球在A的终点，B的起点，B球在B的终点，A的起点。

现在试图将A移回A的起点，即B现在的位置，同时试图将B移到A现在的位置，由于共用一张地图，它们一定会在某点相遇，那么它们以后的运动轨迹

必然完全相同，因此当A回到A的起点是，B也到A的起点。

实际上，两个球不能同时抵达终点当且仅当两串存在满足上述条件的后缀子串。

充分性上面已经给出了说明，下面说明必要性。

考虑一种情形，将球a在从起点移动到终点，此时b停留在终点，假设a球向终点靠近了k步，那么b球在最坏情况下后退的步数显然为k。

在这种情形下，必然有两串有后缀子串满足上述条件，因为两球移动轨迹相同，方向相反，若不存在符合要求的后缀子串，b至多退k-1步。

a、b交替如此移动，总的接近终点的距离严格递增，必然能同时到达终点。

可以用hash或kmp在线性时间内判断子串的存在性。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 10;
char s[maxn], t[maxn];
int n;
int f[500];
int fail[maxn];


int solve(){
    f['W'] = 'E', f['E'] = 'W', f['N'] = 'S', f['S'] = 'N';
    int len = n - 1;
    for(int i = 0; i < len; i++) s[i] = f[s[i]];
    int mid = len >> 1;
    for(int i = 0; i < mid; i++) swap(s[i], s[n - 2 - i]);
    fail[0] = fail[1] = 0;
    for(int i = 1; i < len; i++){
        int j = fail[i];
        while(j && s[j] != s[i]) j = fail[j];
        fail[i + 1] = s[j] == s[i] ? j + 1 : 0;
    }
    int p = 0;
    for(int i = 0; i < len; i++){
        while(p && t[i] != s[p]) p = fail[p];
        p = t[i] == s[p] ? 1 + p : 0;
    }
    return !p;
}

int main(){
    //freopen("in.txt", "r", stdin);
    while(~scanf("%d", &n)){
        scanf("%s%s", s, t);
        int ans = solve();
        puts(ans ? "YES" : "NO");
    }
    return 0;
}