codeforces-scrape

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

2067B.md (2806B)


      1 Source: https://codeforces.com/problemset/problem/2067/B
      2 
      3 B. Two Large Bags
      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 You have two large bags of numbers. Initially, the first bag contains $n$ numbers: $a_1, a_2, \ldots, a_n$, while the second bag is empty. You are allowed to perform the following operations:
     22 
     23 * Choose any number from the first bag and move it to the second bag.
     24 * Choose a number from the first bag that is also present in the second bag and increase it by one.
     25 
     26 You can perform an unlimited number of operations of both types, in any order. Is it possible to make the contents of the first and second bags identical?
     27 
     28 Input
     29 
     30 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.
     31 
     32 The first line of each test case contains an integer $n$ ($2 \le n \le 1000$) — the length of the array $a$. It is guaranteed that $n$ is an even number.
     33 
     34 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
     35 
     36 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^6$.
     37 
     38 Output
     39 
     40 For each test case, print "YES" if it is possible to equalize the contents of the bags. Otherwise, output "NO".
     41 
     42 You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 9
     50 
     51 2
     52 
     53 1 1
     54 
     55 2
     56 
     57 2 1
     58 
     59 4
     60 
     61 1 1 4 4
     62 
     63 4
     64 
     65 3 4 3 3
     66 
     67 4
     68 
     69 2 3 4 4
     70 
     71 6
     72 
     73 3 3 4 5 3 3
     74 
     75 6
     76 
     77 2 2 2 4 4 4
     78 
     79 8
     80 
     81 1 1 1 1 1 1 1 4
     82 
     83 10
     84 
     85 9 9 9 10 10 10 10 10 10 10
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 Yes
     92 No
     93 Yes
     94 Yes
     95 No
     96 Yes
     97 No
     98 Yes
     99 Yes
    100 ```
    101 
    102 Note
    103 
    104 Let's analyze the sixth test case: we will show the sequence of operations that leads to the equality of the bags. Initially, the first bag consists of the numbers $(3, 3, 4, 5, 3, 3)$, and the second bag is empty.
    105 
    106 1. In the first operation, move the number $3$ from the first bag to the second. State: $(3, 4, 5, 3, 3)$ and $(3)$.
    107 2. In the second operation, increase the number $3$ from the first bag by one. This operation is possible because the second bag contains the number $3$. State: $(4, 4, 5, 3, 3)$ and $(3)$.
    108 3. In the third operation, move the number $4$ from the first bag to the second. State: $(4, 5, 3, 3)$ and $(3, 4)$.
    109 4. In the fourth operation, increase the number $4$ from the first bag by one. State: $(5, 5, 3, 3)$ and $(3, 4)$.
    110 5. In the fifth operation, move the number $5$ from the first bag to the second. State: $(5, 3, 3)$ and $(3, 4, 5)$.
    111 6. In the sixth operation, increase the number $3$ from the first bag by one. State: $(5, 3, 4)$ and $(3, 4, 5)$.
    112 
    113 As we can see, as a result of these operations, it is possible to make the contents of the bags equal, so the answer exists.