codeforces-scrape

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

1806C.md (1844B)


      1 Source: https://codeforces.com/problemset/problem/1806/C
      2 
      3 C. Sequence Master
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 For some positive integer $m$, YunQian considers an array $q$ of $2m$ (possibly negative) integers good, if and only if for every possible subsequence of $q$ that has length $m$, the product of the $m$ elements in the subsequence is equal to the sum of the $m$ elements that are not in the subsequence. Formally, let $U=\{1,2,\ldots,2m\}$. For all sets $S \subseteq U$ such that $|S|=m$, $\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$.
     22 
     23 Define the distance between two arrays $a$ and $b$ both of length $k$ to be $\sum\limits_{i=1}^k|a_i-b_i|$.
     24 
     25 You are given a positive integer $n$ and an array $p$ of $2n$ integers.
     26 
     27 Find the minimum distance between $p$ and $q$ over all good arrays $q$ of length $2n$. It can be shown for all positive integers $n$, at least one good array exists. Note that you are not required to construct the array $q$ that achieves this minimum distance.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot10^5$).
     34 
     35 The second line of each test case contains $2n$ integers $p_1, p_2, \ldots, p_{2n}$ ($|p_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 distance between $p$ and a good $q$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 1
     51 
     52 6 9
     53 
     54 2
     55 
     56 1 2 2 1
     57 
     58 2
     59 
     60 -2 -2 2 2
     61 
     62 4
     63 
     64 -3 -2 -1 0 1 2 3 4
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 3
     71 2
     72 5
     73 13
     74 ```
     75 
     76 Note
     77 
     78 In the first test case, it is optimal to let $q=[6,6]$.
     79 
     80 In the second test case, it is optimal to let $q=[2,2,2,2]$.