453B - Little Pony and Harmony Chest

Solution:

Learnt new thing thanks to the official editorial :)

The low constraints for both n and \(a_i\) suggests that we can do a complete search, and in fact we can use a bitmasking technique to perform this search more efficiently. Firstly, to minimize \(|a_i-b_i|\), we would like to choose \(b_i\) that can do better than just simply assigning 1 to \(b_i\). This means that \(b_i\) should be between [1..\(2a_i-1\)], and thus 2*30-1 = 59 marks the upperbound for \(b_i\). Our strategy would be simply try each of these 59 numbers on each i, but simply trying all combinations would be too slow. So what we can do a dynamic programming approach: d[i][bm] be the minimum possible \(\sum_{k=1}^{i} |a_k-b_k|\), while bm indicates the bitmask, where if k-th bit is on, then we have assigned number k a \(b_i\). However, using such bitmask prove to be too big in space, since bm can go up to \(2^{59}\). We can do better, but just bitmasking the prime factors that have been used (i.e. if bit k is set, then some \(b_i\) is divisible by k-th prime)! There are only 17 primes in [1..59], so we reduced the bitmask states to \(2^{17}\) :D

Next, pre-calculate factor[k], which is a bitmask where i-th bit is on if number k is divisible by i-th prime. To fill up d[i][bm], we can make use of values in d[i-1], as follows:

Suppose we want to assign \(b_i\) with j. That means we want to find all bitmask bm such that factor[j] AND bm does not intersect at all. This will allow us to update d[i][bm OR factor[j]] to d[i-1][bm] + | a[i] - j | accordingly.

Here is the final trick to push down the search space. Let x be the highest possible bitmask such that x AND factor[j] does not intersect. Initially, we set bm equals to x. Then to find all other bm, we can do:

bm := (bm - 1) & x.

Very clever bitmasking technique!

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; /* make use of the prime numbers */ int mark[63]; vector<int> primes; int a[103]; int dp[103][1<<17]; int par[103][1<<17]; int g[64][18]; int dep[64]; int N; int iabs(int x){return (x>0?x:-x);} void print_out(int k,int idx){ if(k==1){ printf("%d",par[k][idx]); return; } print_out(k-1,idx^dep[par[k][idx]]); printf(" %d", par[k][idx]); } int main(){ for(int i=2;i*i<=60;++i){ for(int j=i;j*i<=60;++j){ mark[i*j]=1; } } for(int i=2;i<=60;++i){ if(!mark[i])primes.push_back(i); } for(int i=1;i<=60;++i){ for(int j=0;j<17;++j){ if(i%primes[j]==0)g[i][j]=1; } int tmp = 0; for(int j=16;j>=0;--j){ tmp <<= 1; tmp += (g[i][j]?1:0); } dep[i] = tmp; } scanf("%d", &N); for(int i=1;i<=N;++i){ scanf("%d",&a[i]); } for(int i=1;i<=N;++i){ for(int j=0;j<(1<<17);++j){ dp[i][j] = 123456; } } for(int i=1;i<=N;++i){ for(int j=1;j<=60;++j){ int bm = ((1<<17)-1)^(dep[j]); for(int k=bm;;k=(k-1)&bm){ int tmp = dp[i-1][k] + iabs(a[i]-j); if(tmp < dp[i][k|dep[j]]){ dp[i][k|dep[j]] = tmp; par[i][k|dep[j]] = j; } if(k==0)break; } } } int ans = 123456; int idx = -1; for(int j=0;j<(1<<17);++j){ if(ans > dp[N][j]){ ans = dp[N][j]; idx = j; } } print_out(N, idx);printf("\n"); return 0; }