codeforces-scrape

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

1031B.md (2553B)


      1 Source: https://codeforces.com/problemset/problem/1031/B
      2 
      3 B. Curiosity Has No Limits
      4 
      5 time limit per test
      6 
      7 1 second
      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 When Masha came to math classes today, she saw two integer sequences of length $n - 1$ on the blackboard. Let's denote the elements of the first sequence as $a_i$ ($0 \le a_i \le 3$), and the elements of the second sequence as $b_i$ ($0 \le b_i \le 3$).
     22 
     23 Masha became interested if or not there is an integer sequence of length $n$, which elements we will denote as $t_i$ ($0 \le t_i \le 3$), so that for every $i$ ($1 \le i \le n - 1$) the following is true:
     24 
     25 * $a_i = t_i | t_{i + 1}$ (where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR)) and
     26 * $b_i = t_i \& t_{i + 1}$ (where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND)).
     27 
     28 The question appeared to be too difficult for Masha, so now she asked you to check whether such a sequence $t_i$ of length $n$ exists. If it exists, find such a sequence. If there are multiple such sequences, find any of them.
     29 
     30 Input
     31 
     32 The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the length of the sequence $t_i$.
     33 
     34 The second line contains $n - 1$ integers $a_1, a_2, \ldots, a_{n-1}$ ($0 \le a_i \le 3$) — the first sequence on the blackboard.
     35 
     36 The third line contains $n - 1$ integers $b_1, b_2, \ldots, b_{n-1}$ ($0 \le b_i \le 3$) — the second sequence on the blackboard.
     37 
     38 Output
     39 
     40 In the first line print "YES" (without quotes), if there is a sequence $t_i$ that satisfies the conditions from the statements, and "NO" (without quotes), if there is no such sequence.
     41 
     42 If there is such a sequence, on the second line print $n$ integers $t_1, t_2, \ldots, t_n$ ($0 \le t_i \le 3$) — the sequence that satisfies the statements conditions.
     43 
     44 If there are multiple answers, print any of them.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 4  
     52 3 3 2  
     53 1 2 0
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 YES  
     60 1 3 2 0
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 3  
     67 1 3  
     68 3 2
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 NO
     75 ```
     76 
     77 Note
     78 
     79 In the first example it's easy to see that the sequence from output satisfies the given conditions:
     80 
     81 * $t_1 | t_2 = (01_2) | (11_2) = (11_2) = 3 = a_1$ and $t_1 \& t_2 = (01_2) \& (11_2) = (01_2) = 1 = b_1$;
     82 * $t_2 | t_3 = (11_2) | (10_2) = (11_2) = 3 = a_2$ and $t_2 \& t_3 = (11_2) \& (10_2) = (10_2) = 2 = b_2$;
     83 * $t_3 | t_4 = (10_2) | (00_2) = (10_2) = 2 = a_3$ and $t_3 \& t_4 = (10_2) \& (00_2) = (00_2) = 0 = b_3$.
     84 
     85 In the second example there is no such sequence.