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.

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