codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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)$.