codeforces-scrape

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

2241D.md (2454B)


      1 Source: https://codeforces.com/problemset/problem/2241/D
      2 
      3 D. An Alternative Way
      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 two arrays $a$ and $b$, each of length $n$. You are allowed to perform the following operation on array $a$ any number of times (including zero):
     22 
     23 1. Choose two indices $l$ and $r$ such that $1 \le l \le r \le n$;
     24 2. For each index $i$ from $l$ to $r$ (both inclusive),
     25    * Set $a_i := a_i - 1$ if $i - l$ is odd.
     26    * Set $a_i := a_i + 1$ if $i - l$ is even.
     27 
     28 Determine whether you can make the array $a$ equal to the array $b$ by performing the operation any number of times.
     29 
     30 Input
     31 
     32 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of each test case follows.
     33 
     34 The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the arrays $a$ and $b$.
     35 
     36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.
     37 
     38 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) — the elements of the array $b$.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     41 
     42 Output
     43 
     44 For each test case, print "YES" if you can make array $a$ equal to array $b$ and "NO" otherwise.
     45 
     46 You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 7
     54 
     55 3
     56 
     57 1 2 3
     58 
     59 1 2 3
     60 
     61 4
     62 
     63 1 4 5 2
     64 
     65 1 5 4 3
     66 
     67 1
     68 
     69 9
     70 
     71 8
     72 
     73 6
     74 
     75 6 7 6 7 6 7
     76 
     77 7 6 7 6 7 6
     78 
     79 9
     80 
     81 9 8 7 6 5 4 3 2 1
     82 
     83 9 9 8 2 4 4 3 5 3
     84 
     85 3
     86 
     87 1 1 2
     88 
     89 2 1 1
     90 
     91 2
     92 
     93 1 2
     94 
     95 1 1
     96 ```
     97 
     98 Output
     99 
    100 ```
    101 YES
    102 
    103 YES
    104 
    105 NO
    106 
    107 YES
    108 
    109 NO
    110 
    111 YES
    112 
    113 NO
    114 ```
    115 
    116 Note
    117 
    118 For the first test case, arrays $a$ and $b$ are already equal.
    119 
    120 For the second test case, let us choose $l = 2$ and $r = 4$. Now, we update the array $a$ in the following manner:
    121 
    122 * For $i = 2$, we have $i - l = 2 - 2 = 0$, which is even. Hence, set $a_2 := a_2 + 1 = 4 + 1 = 5$.
    123 * For $i = 3$, we have $i - l = 3 - 2 = 1$, which is odd. Hence, set $a_3 := a_3 - 1 = 5 - 1 = 4$.
    124 * For $i = 4$, we have $i - l = 4 - 2 = 2$, which is even. Hence, set $a_4 := a_4 + 1 = 2 + 1 = 3$.
    125 
    126 Finally, we have array $a = [1, 5, 4, 3]$ and array $b = [1, 5, 4, 3]$.
    127 
    128 For the third test case, it can be shown that it is impossible to make array $a$ equal to array $b$.