Codeforces Round #720 - 1521B. Nastia and a Good Array

This is an unofficial editorial for [Nastia and a Good Array](https://codeforces.com/contest/1521/problem/B). ## Problem Statement Nastia has received an array of n positive integers as a gift. She calls such an array a good that for all i ($ 2 <= i <= n $) takes place $ gcd(a_i − 1, a_i )$ = 1, where $ gcd(u, v) $ denotes the greatest common divisor (GCD) of integers u and v. You can perform the operation: select two different indices $i$, $j$ ($1 <= i, j <= n, i \neq j$) and two integers $x$, $y$ ($1 <= x,y <= 2 * 10^9$) so that $ min(a_i, a_j) = min(x, y)$. Then change $a_i$ to $x$ and $a_j$ to $y$. The girl asks you to make the array good using at most $n$ operations. It can be proven that this is always possible. ## Approach From the statement, we can have our first obversation which is $ a_i - 1 $ and $a_i$ are coprime, denoted by $ gcd(a_i − 1, a_i )$ = $1$. Two integers are coprime if the only positive integer that is a divisor of both of them is 1, mathematically $ gcd(a, b) = 1 $. Therefore, this question can be rephrased as "how to make a_i - 1 and a_i coprime using at most $n$ operations". ### Solution 1 We can use the fact that an integer $x$ and $ x \pm 1 $ are coprime. First let's find the min value $x$ and its position $pos$ in array $a$ as we have to use this value to perform the operations. For all integer $i$ where $ 1 <= i <= n $, we can perform $ (pos, i, x ,abs(pos - i)) $ to replace $a_i$ to $x$ + $abs(pos - i)$. For the first test case, we can make $ [9, 6, 3, 11, 15] $ to $ [5, 4, 3, 4, 5] $ using $ n - 1 $ operations. ### Solution 2 We can put a prime number, let's say $ 1e9 + 7$ on every odd index if the minimum value is on even index and vice versa. In this case, we just need $ (n + 1) / 2 $ operations to turn $ [9, 6, 3, 11, 15] $ to $ [9, 1e9 + 7, 3, 1e9 + 7, 15] $.

Nezzar and Symmetric Array

This is an unofficial editorial for [Nezzar and Symmetric Array](https://codeforces.com/problemset/problem/1478/C). ## Problem Statement Long time ago there was a symmetric array $a_1$, $a_2$, ... ,$a_{2n}$ consisting of $2n$ distinct integers. Array $a_1$, $a_2$, ... ,$a_{2n}$ is called symmetric if for each integer $1 <= i <= 2n$, there exists an integer $1 <= j <= 2n$ such that $a_i = -a_j$. For each integer $1<=i<=2n$, Nezzar wrote down an integer $d_i$ equal to the sum of absolute differences from $a_i$ to all integers in $a$, i. e. $d_i$ = $\sum_{j=1}^{2n} |a_i - a_j|$. Now a million years has passed and Nezzar can barely remember the array $d$ and totally forget $a$. Nezzar wonders if there exists any symmetric array 𝑎 consisting of $2n$ distinct integers that generates the array $d$. ## Input The first line contains a single integer $t$ ($1 <= t <= 10^5$) — the number of test cases. The first line of each test case contains a single integer 𝑛 ($1 <= n <= 10^5$). The second line of each test case contains $2n$ integers $d_1, d_2, ..., d_{2n}$ ($1 <= d_i <= 10^{12}$). It is guaranteed that the sum of 𝑛 over all test cases does not exceed $10^5$. ## Output For each test case, print "YES" in a single line if there exists a possible array 𝑎. Otherwise, print "NO". You can print letters in any case (upper or lower). ## Approach Here's the simulation of the first example. ``` a = [1 -3 -1 3] i = 0 : 0 + 4 + 2 + 2 = 8 i = 1 : 4 + 0 + 2 + 6 = 12 i = 2 : 2 + 2 + 0 + 4 = 8 i = 3 : 2 + 6 + 4 + 0 = 12 d = [8, 12, 8, 12] ``` Each element has a positive and negative value. Supposing the positive value is $ x $, and the absolute difference to $(y, -y)$ would be $| x - y | + | x + y | $. Similarly, for $ -x $, that would be $ |-x - y | + |-x + y |$, which is also $|x - y| + |x + y|$. Therefore, for each $ d[i] $, there would be a pair as well. For $|x - y| + |x + y|$, we have two different cases. For $x > y$, $|x - y| + |x + y|$ would be $ 2 * x $. For $x > y$, $|x - y| + |x + y|$ would be $ 2 * y $. Now we know that $|x - y| + |x + y|$ = $2 * max(x, y)$. For each $ d[i] $, it is the sum of each absolute differences from $a[i]$ to all integers. Combined with the previous finding, we got $$ d[i] = \sum_{j=1}^{2n} max(abs(a[i]), abs(a[j])) $$ Given the array $d$, how can we generate the array $a$ back? Supposing the maximum element in $a$ is called $max_1$, the corresponding $d[i]$ would be $max_1 * 2 * n$. Therefore, we now have $max_1 = d[i] / 2 / n$. For the second maximum element, let's say $max_2$, as there is only $max_1$ which is greater than $max_2$, all other $(n - 1)$ elements are less than or equal to $max2$. The sum of absolute differences to them would be $max_2 * 2 * (n - 1)$. As $max_2 < max_1$, we need to add $max_1 * 2$ back to $d[i]$. Similarly, we can do the same thing one by one to get the original array $a$ back. We can induce that $$ max_1 = d[i] / 2 / n $$ $$ max_2 = (d[i] - max_1 * 2) / 2 / (n - 1) $$ $$ max_3 = (d[i] - max_2 * 2) / 2 / (n - 2) $$ $$ max_4 = (d[i] - max_3 * 2) / 2 / (n - 3) $$ $$ \vdots $$ $$ max_m = (d[i] - max_{m - 1} * 2) / 2 / (n - k) $$ For each elelment $x$, we need to check the occurence of its absolute value. If $x$ is odd or its occurence is odd, then the answer is $NO$. Also, if $x$ appears more than 2 times, that would be also $NO$. For each $max_m$, we can verify that if we can retrieve an integer, i.e. $(d[i] - max_{m - 1} * 2) / 2 % (n - k) $ is $0$ or not. If not, that is also $NO$. if $(d[i] - max_{m - 1} * 2) / 2 / (n - k) $ appears before or it is less than or equal to $0$, that is also not a correct answer. Therefore, we have 6 cases to check in total. For other cases, that would be $YES$. ## Solution ``` void solve() { long long n; cin >> n; map<long long, long long> vis, m; for(int i = 0; i < 2 * n; i++) cin >> d[i], m[-d[i]]++; long long cur_sum = 0, k = 0; EACH(it, m) { long long abs_difference = -it.fi, occurrence = it.se; if(abs_difference % 2 || occurrence % 2 || occurrence > 2) { cout << "NO" << "\n"; return; } long long p = (abs_difference - cur_sum * 2) / 2; long long q = n - k; if(p % q) { cout << "NO" << "\n"; return; } p /= q; if(vis.count(p) || p <= 0) { cout << "NO" << "\n"; return; } vis[p] = 1, cur_sum += p, k++; } cout << "YES" << "\n"; } ```