codeforces-scrape

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

1234C.md (3112B)


      1 Source: https://codeforces.com/problemset/problem/1234/C
      2 
      3 C. Pipes
      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 You are given a system of pipes. It consists of two rows, each row consists of $n$ pipes. The top left pipe has the coordinates $(1, 1)$ and the bottom right — $(2, n)$.
     22 
     23 There are six types of pipes: two types of straight pipes and four types of curved pipes. Here are the examples of all six types:
     24 
     25  ![](https://espresso.codeforces.com/4be8aa994b2575b7403f51ec6b3ff596fd769534.png) Types of pipes 
     26 
     27 You can turn each of the given pipes $90$ degrees clockwise or counterclockwise arbitrary (possibly, zero) number of times (so the types $1$ and $2$ can become each other and types $3, 4, 5, 6$ can become each other).
     28 
     29 You want to turn some pipes in a way that the water flow can start at $(1, 0)$ (to the left of the top left pipe), move to the pipe at $(1, 1)$, flow somehow by connected pipes to the pipe at $(2, n)$ and flow right to $(2, n + 1)$.
     30 
     31 Pipes are connected if they are adjacent in the system and their ends are connected. Here are examples of connected pipes:
     32 
     33  ![](https://espresso.codeforces.com/896b4e9fc4f89bf45d8e468fdd7909e1353c256a.png) Examples of connected pipes 
     34 
     35 Let's describe the problem using some example:
     36 
     37  ![](https://espresso.codeforces.com/d31de5d4a5e62f813fc7f6ba357fb87f15ccd776.png) The first example input 
     38 
     39 And its solution is below:
     40 
     41  ![](https://espresso.codeforces.com/08173690b40b66f316bdd136920a033e07af4677.png) The first example answer 
     42 
     43 As you can see, the water flow is the poorly drawn blue line. To obtain the answer, we need to turn the pipe at $(1, 2)$ $90$ degrees clockwise, the pipe at $(2, 3)$ $90$ degrees, the pipe at $(1, 6)$ $90$ degrees, the pipe at $(1, 7)$ $180$ degrees and the pipe at $(2, 7)$ $180$ degrees. Then the flow of water can reach $(2, n + 1)$ from $(1, 0)$.
     44 
     45 You have to answer $q$ independent queries.
     46 
     47 Input
     48 
     49 The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of queries. Then $q$ queries follow.
     50 
     51 Each query consists of exactly three lines. The first line of the query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of pipes in each row. The next two lines contain a description of the first and the second rows correspondingly. Each row description consists of $n$ digits from $1$ to $6$ without any whitespaces between them, each digit corresponds to the type of pipe in the corresponding cell. See the problem statement to understand which digits correspond to which types of pipes.
     52 
     53 It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$.
     54 
     55 Output
     56 
     57 For the $i$-th query print the answer for it — "YES" (without quotes) if it is possible to turn some pipes in a way that the water flow can reach $(2, n + 1)$ from $(1, 0)$, and "NO" otherwise.
     58 
     59 Example
     60 
     61 Input
     62 
     63 ```
     64 6
     65 7
     66 2323216
     67 1615124
     68 1
     69 3
     70 4
     71 2
     72 13
     73 24
     74 2
     75 12
     76 34
     77 3
     78 536
     79 345
     80 2
     81 46
     82 54
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 YES
     89 YES
     90 YES
     91 NO
     92 YES
     93 NO
     94 ```
     95 
     96 Note
     97 
     98 The first query from the example is described in the problem statement.