codeforces-scrape

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

1904C.md (2137B)


      1 Source: https://codeforces.com/problemset/problem/1904/C
      2 
      3 C. Array Game
      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$ positive integers. In one operation, you must pick some $(i, j)$ such that $1\leq i \lt j\leq |a|$ and append $|a_i - a_j|$ to the end of the $a$ (i.e. increase $n$ by $1$ and set $a_n$ to $|a_i - a_j|$). Your task is to minimize and print the minimum value of $a$ after performing $k$ operations.
     22 
     23 Input
     24 
     25 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.
     26 
     27 The first line of each test case contains two integers $n$ and $k$ ($2\le n\le 2\cdot 10^3$, $1\le k\le 10^9$) — the length of the array and the number of operations you should perform.
     28 
     29 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 10^{18}$) — the elements of the array $a$.
     30 
     31 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $4\cdot 10^6$.
     32 
     33 Output
     34 
     35 For each test case, print a single integer — the smallest possible value of the minimum of array $a$ after performing $k$ operations.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 4
     43 
     44 5 2
     45 
     46 3 9 7 15 1
     47 
     48 4 3
     49 
     50 7 4 15 12
     51 
     52 6 2
     53 
     54 42 47 50 54 62 79
     55 
     56 2 1
     57 
     58 500000000000000000 1000000000000000000
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 1
     65 0
     66 3
     67 500000000000000000
     68 ```
     69 
     70 Note
     71 
     72 In the first test case, after any $k=2$ operations, the minimum value of $a$ will be $1$.
     73 
     74 In the second test case, an optimal strategy is to first pick $i=1, j=2$ and append $|a_1 - a_2| = 3$ to the end of $a$, creating $a=[7, 4, 15, 12, 3]$. Then, pick $i=3, j=4$ and append $|a_3 - a_4| = 3$ to the end of $a$, creating $a=[7, 4, 15, 12, 3, 3]$. In the final operation, pick $i=5, j=6$ and append $|a_5 - a_6| = 0$ to the end of $a$. Then the minimum value of $a$ will be $0$.
     75 
     76 In the third test case, an optimal strategy is to first pick $i=2, j=3$ to append $|a_2 - a_3| = 3$ to the end of $a$. Any second operation will still not make the minimum value of $a$ be less than $3$.