Link to problem and solution: Here

In part (d) of this problem, they assume P to be also augmented w.r.t M. How's this assumed? And after assuming this, they prove something else, and since that is proved, they say the condition they assumed earlier is true.

It seems very cyclic to me. In the previous part (part (c)), they had proved that P is augmented if it is vertex disjoint. But in this part, it is not vertex disjoint. Am I missing something?

Let's call a sequence of numbers b[1]...b[n] fancy if gcd(b[i], b[j]) = 1 for all 1 <= i < j <= n. (Meaning all the elements of the array are coprime to each other).

Given a sequence of numbers a[1], a[2], ..., a[n], what is the minimum possible value of abs(a[1]-b[1]) + abs(a[2]-b[2]) + ... + abs(a[n]-b[n]), where b[1]...b[n] is a fancy sequence?

EXAMPLE:

Input — [1, 1, 1, 1, 1] Output — 0 Explanation: [1, 1, 1, 1, 1] itself is a "fancy" sequence, so the minimum possible distance is 0.

Input — [1, 6, 4, 2, 8] Output — 3 Explanation — One of the optimal "fancy" sequences is [1, 5, 3, 1, 8]. distance([1, 6, 4, 2, 8], [1, 5, 3, 1, 8]) = |1-1| + |6-5| + |4-3| + |2-1| + |8-8| = 3.

Input — [1, 2, 4] Output — 1 Explanation — Zero distance is impossible because [1, 2, 4] is not "fancy". One of the optimal "fancy" sequences is [1, 2, 3]. distance([1, 2, 4], [1, 2, 3]) = |1-1| + |2-2| + |4-3| = 1.

Constraints

1 ≤ n ≤ 10^2 [Size of the array] 1 ≤ arr[i] ≤ 30 [Meaning the input array can have elements with values in this range]

I had encountered this particular problem during an online intervview round. Any idea how to approach this problem? P.S: The round is over, I was just curious about how to approach the problem