codeforces-scrape

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

1617C.md (2109B)


      1 Source: https://codeforces.com/problemset/problem/1617/C
      2 
      3 C. Paprika and Permutation
      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 Paprika loves permutations. She has an array $a_1, a_2, \dots, a_n$. She wants to make the array a permutation of integers $1$ to $n$.
     22 
     23 In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers $i$ ($1 \le i \le n$) and $x$ ($x \gt 0$), then perform $a_i := a_i \bmod x$ (that is, replace $a_i$ by the remainder of $a_i$ divided by $x$). In different operations, the chosen $i$ and $x$ can be different.
     24 
     25 Determine the minimum number of operations needed to make the array a permutation of integers $1$ to $n$. If it is impossible, output $-1$.
     26 
     27 A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.
     32 
     33 The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$).
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$. ($1 \le a_i \le 10^9$).
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output the minimum number of operations needed to make the array a permutation of integers $1$ to $n$, or $-1$ if it is impossible.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 2
     50 1 7
     51 3
     52 1 5 4
     53 4
     54 12345678 87654321 20211218 23571113
     55 9
     56 1 2 3 4 18 19 5 6 7
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 1
     63 -1
     64 4
     65 2
     66 ```
     67 
     68 Note
     69 
     70 For the first test, the only possible sequence of operations which minimizes the number of operations is:
     71 
     72 * Choose $i=2$, $x=5$. Perform $a_2 := a_2 \bmod 5 = 2$.
     73 
     74 For the second test, it is impossible to obtain a permutation of integers from $1$ to $n$.