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]$.