kishoreganesh's blog

By kishoreganesh, history, 4 years ago, In English

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

  • Vote: I like it
  • +9
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

This problem is from Codeforces itself on Bitmask Dp. You can read it's editorial here.Click