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