1948C.md (2396B)
1 Source: https://codeforces.com/problemset/problem/1948/C 2 3 C. Arrow Path 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a grid, consisting of $2$ rows and $n$ columns. The rows are numbered from $1$ to $2$ from top to bottom. The columns are numbered from $1$ to $n$ from left to right. Each cell of the grid contains an arrow pointing either to the left or to the right. No arrow points outside the grid. 22 23 There is a robot that starts in a cell $(1, 1)$. Every second, the following two actions happen one after another: 24 25 1. Firstly, the robot moves left, right, down or up (it can't try to go outside the grid, and can't skip a move); 26 2. then it moves along the arrow that is placed in the current cell (the cell it ends up after its move). 27 28 Your task is to determine whether the robot can reach the cell $(2, n)$. 29 30 Input 31 32 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 33 34 The first line of each test case contains a single integer ($2 \le n \le 2 \cdot 10^5$). 35 36 The second line contains a string consisting of exactly $n$ characters < and/or > — the first row of the grid. 37 38 The third line contains a string consisting of exactly $n$ characters < and/or > — the second row of the grid. 39 40 Additional constraints on the input: 41 42 * $n$ is even; 43 * there are no arrows pointing outside the grid; 44 * the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 45 46 Output 47 48 For each test case, print YES if the robot can reach the cell $(2, n)$; otherwise, print NO. 49 50 You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as positive answer. 51 52 Example 53 54 Input 55 56 ``` 57 4 58 59 4 60 61 >><< 62 63 >>>< 64 65 2 66 67 >< 68 69 >< 70 71 4 72 73 >>>< 74 75 >><< 76 77 6 78 79 >><<>< 80 81 ><>>>< 82 ``` 83 84 Output 85 86 ``` 87 YES 88 YES 89 NO 90 YES 91 ``` 92 93 Note 94 95 In the first example, one of the possible paths looks as follows: $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4)$. 96 97 In the second example, one of the possible paths looks as follows: $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$. 98 99 In the third example, there is no way to reach the cell $(2, 4)$. 100 101 In the fourth example, one of the possible paths looks as follows: $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (2, 5) \rightarrow (2, 6)$.