Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### LovesProgramming's blog

By LovesProgramming, history, 2 months ago, ,

We are given an array "A" of size "N"

Constraints :

1) 1<=N<=100

2) 1<=A[i]<=30

We have to generate an array "b" of size "N" such that for all pairs (i,j) , gcd(b[i],b[j]) = 1, holds true for array "b" .

The value to be calculated is : abs(A[1]-b[1]) + abs(A[2]-b[2]) + ...... + .... + ..... abs(A[n] — b[n]) = x

We have to minimize the value of 'x'.

How to generate an array "b" which minimizes the value of "x" ?

Example array "A" :- {1,2,4,6,8}

Output array "b" : — {1,2,3,5,7}

and x = 3, which is the minimum possible value.

I got code for this problem in a group : — https://ideone.com/VUyN5p

But still cannot get the idea behind the solution.

• -4

 » 2 months ago, # |   0 problem link ?
 » 2 months ago, # |   0 First thing to observe is $b[i] <= 58$. Otherwise we may replace, $b[i]$ with $1$ without increasing $x$. There are only $16$ primes not larger than $58$. Each prime may divide at most one of the values in $b$. We can represent any subset of these primes with a $16$ bit bitmask. Thus we can do a dp.$dp[i][mask] =$ minimum score considering only the first $i$ indexes using only primes from mask. For transitions, we can simply iterate over all $58$ possible values of $b[i]$ and update the mask accordingly.