codeforces-scrape

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

2032C.md (2301B)


      1 Source: https://codeforces.com/problemset/problem/2032/C
      2 
      3 C. Trinity
      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 an array $a$ of $n$ elements $a_1, a_2, \ldots, a_n$.
     22 
     23 You can perform the following operation any number (possibly $0$) of times:
     24 
     25 * Choose two integers $i$ and $j$, where $1 \le i, j \le n$, and assign $a_i := a_j$.
     26 
     27 Find the minimum number of operations required to make the array $a$ satisfy the condition:
     28 
     29 * For every pairwise distinct triplet of indices $(x, y, z)$ ($1 \le x, y, z \le n$, $x \ne y$, $y \ne z$, $x \ne z$), there exists a non-degenerate triangle with side lengths $a_x$, $a_y$ and $a_z$, i.e. $a_x + a_y \gt a_z$, $a_y + a_z \gt a_x$ and $a_z + a_x \gt a_y$.
     30 
     31 Input
     32 
     33 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     34 
     35 The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$.
     36 
     37 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$.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the minimum number of operations required.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 7
     53 
     54 1 2 3 4 5 6 7
     55 
     56 3
     57 
     58 1 3 2
     59 
     60 3
     61 
     62 4 5 3
     63 
     64 15
     65 
     66 9 3 8 1 6 5 3 8 2 1 4 2 9 4 7
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 3
     73 1
     74 0
     75 8
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, one of the possible series of operations would be:
     81 
     82 * Assign $a_1 := a_4 = 4$. The array will become $[4, 2, 3, 4, 5, 6, 7]$.
     83 * Assign $a_2 := a_5 = 5$. The array will become $[4, 5, 3, 4, 5, 6, 7]$.
     84 * Assign $a_7 := a_1 = 4$. The array will become $[4, 5, 3, 4, 5, 6, 4]$.
     85 
     86 It can be proven that any triplet of elements with pairwise distinct indices in the final array forms a non-degenerate triangle, and there is no possible answer using less than $3$ operations.
     87 
     88 In the second test case, we can assign $a_1 := a_2 = 3$ to make the array $a = [3, 3, 2]$.
     89 
     90 In the third test case, since $3$, $4$ and $5$ are valid side lengths of a triangle, we don't need to perform any operation to the array.