codeforces-scrape

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

2061D.md (2470B)


      1 Source: https://codeforces.com/problemset/problem/2061/D
      2 
      3 D. Kevin and Numbers
      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 Kevin wrote an integer sequence $a$ of length $n$ on the blackboard.
     22 
     23 Kevin can perform the following operation any number of times:
     24 
     25 * Select two integers $x, y$ on the blackboard such that $|x - y| \leq 1$, erase them, and then write down an integer $x + y$ instead.
     26 
     27 Kevin wants to know if it is possible to transform these integers into an integer sequence $b$ of length $m$ through some sequence of operations.
     28 
     29 Two sequences $a$ and $b$ are considered the same if and only if their multisets are identical. In other words, for any number $x$, the number of times it appears in $a$ must be equal to the number of times it appears in $b$.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     34 
     35 The first line of each test case contains two integers $n$ and $m$ ($1\leq m \leq n \leq 2\cdot 10^5$) — the length of $a$ and the length of $b$.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i \leq 10^9$).
     38 
     39 The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1\leq b_i \leq 10^9$).
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output "Yes" if it is possible to transform $a$ into $b$, and "No" otherwise.
     46 
     47 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 9
     55 
     56 2 1
     57 
     58 4 5
     59 
     60 9
     61 
     62 2 1
     63 
     64 3 6
     65 
     66 9
     67 
     68 4 2
     69 
     70 1 2 2 2
     71 
     72 3 4
     73 
     74 4 2
     75 
     76 1 1 3 3
     77 
     78 3 5
     79 
     80 4 2
     81 
     82 1 2 3 4
     83 
     84 3 5
     85 
     86 5 5
     87 
     88 1 2 3 4 5
     89 
     90 5 4 3 2 1
     91 
     92 4 2
     93 
     94 1 1 1 1
     95 
     96 1 1
     97 
     98 4 4
     99 
    100 1 1 1 1
    101 
    102 1 1 1 2
    103 
    104 1 1
    105 
    106 1
    107 
    108 1000000000
    109 ```
    110 
    111 Output
    112 
    113 ```
    114 Yes
    115 
    116 No
    117 
    118 Yes
    119 
    120 Yes
    121 
    122 No
    123 
    124 Yes
    125 
    126 No
    127 
    128 No
    129 
    130 No
    131 ```
    132 
    133 Note
    134 
    135 In the first test case, you can erase $4, 5$, and write down $9$.
    136 
    137 In the second test case, you can't erase $3, 6$.
    138 
    139 In the third test case, one possible way could be:
    140 
    141 * Erase $2, 2$, and write down $4$. The remaining numbers are $1, 2, 4$ now.
    142 * Erase $1, 2$, and write down $3$. The remaining numbers are $3, 4$ now.
    143 
    144 In the fourth test case, one possible way could be:
    145 
    146 * Erase $1, 1$, and write down $2$. The remaining numbers are $2, 3, 3$ now.
    147 * Erase $2, 3$, and write down $5$. The remaining numbers are $3, 5$ now.