## Thursday, January 8, 2015

### Codeforces 453B - Little Pony and Harmony Chest

Problem Statement:
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.

#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;
}