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

This is an unofficial editorial for Nastia and a Good Array.

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.

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";
}