codeforces-scrape

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

2104D.md (2883B)


      1 Source: https://codeforces.com/problemset/problem/2104/D
      2 
      3 D. Array and GCD
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an integer array $a$ of size $n$.
     22 
     23 You can perform the following operations any number of times (possibly, zero):
     24 
     25 * pay one coin and increase any element of the array by $1$ (you must have at least $1$ coin to perform this operation);
     26 * gain one coin and decrease any element of the array by $1$.
     27 
     28 Let's say that an array is ideal if both of the following conditions hold:
     29 
     30 * each element of the array is at least $2$;
     31 * for each pair of indices $i$ and $j$ ($1 \le i, j \le n$; $i \ne j$) the greatest common divisor (GCD) of $a_i$ and $a_j$ is equal to $1$. If the array has less than $2$ elements, this condition is automatically satisfied.
     32 
     33 Let's say that an array is beautiful if it can be transformed into an ideal array using the aforementioned operations, provided that you initially have no coins. If the array is already ideal, then it is also beautiful.
     34 
     35 The given array is not necessarily beautiful or ideal. You can remove any elements from it (including removing the entire array or not removing anything at all). Your task is to calculate the minimum number of elements you have to remove (possibly, zero) from the array $a$ to make it beautiful.
     36 
     37 Input
     38 
     39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     40 
     41 The first line of each test case contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$).
     42 
     43 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 10^9$).
     44 
     45 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $4 \cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, print a single integer — the minimum number of elements you have to remove (possibly, zero) from the array $a$ to make it beautiful.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 5
     57 
     58 3
     59 
     60 5 5 5
     61 
     62 4
     63 
     64 2 3 2 4
     65 
     66 1
     67 
     68 3
     69 
     70 3
     71 
     72 2 100 2
     73 
     74 5
     75 
     76 2 4 2 11 2
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 0
     83 2
     84 0
     85 0
     86 1
     87 ```
     88 
     89 Note
     90 
     91 In the first example, you don't need to delete any elements, because the array is already beautiful. It can be transformed into an ideal array as follows: $[5, 5, 5] \rightarrow [4, 5, 5] \rightarrow [4, 4, 5] \rightarrow [4, 3, 5]$ (you end up with $3$ coins).
     92 
     93 In the second example, you need to remove $2$ elements so that the array becomes beautiful. If you leave the elements $[2, 3]$ and delete the other elements, then the given array is already ideal (and therefore, beautiful).
     94 
     95 In the third example, you don't need to delete any elements because the array is already ideal (and thus, beautiful).
     96 
     97 In the fourth example, the array is beautiful. It can be transformed into an ideal array as follows: $[2, 100, 2] \rightarrow [2, 99, 2] \rightarrow [2, 99, 3] \rightarrow [2, 98, 3] \rightarrow [2, 97, 3]$ (you end up with $2$ coins).