Codeforces Round #290 (Div. 1 B / Div. 2 D) - Fox and Jumping

Problem Statement:
512B - Fox and Jumping

Solution:
The idea to solve this problem is pretty simple (but the DP is not :P): Find the lowest cost combination of cards for which their greatest common divisor is 1. The official editorial has succinctly explained the DP approach in merely a few lines, check it out!

The proper DP approach is to do a bitmask on prime factors, which will give a running time of \(O(2^k N^2)\), where k is at most 9, since there can at most be 9 different prime factors in any integer less than \(10^9\). How does it work?



Firstly notice that in order to visit all cells, we need a set of \(l_i\) such that there exist integers \(a_i\) such that \(\sum a_i l_i = 1\). This is exactly the definition of \(gcd(l_1,l_2,\ldots ,l_i) = 1\). Let's now focus on one card i. \(l_i\) must be divisible by a certain set of primes \(p_1,p_2,\ldots,p_k\). Let's suppose that this card must be included in our set of chosen card (i.e. we must have this card in our final deck). We want to compute the minimum cost needed to form the final deck consisting this card i. For all other card j, we can check which of these \(p_1, p_2,\ldots , p_k\) that also divides \(l_j\), and we can represent this information as a bitmask \(b_j\) containing k bits for which bit i is set if \(l_j\) is divisible by \(p_i\). Hence if we can find a combination of cards such that \(b_1\) AND \(b_2\) AND \(\ldots\) AND \(b_n\) is 0, then their greatest common divisor is 1! As such what we need to do is:
1. Let S[b] maintains the information about the minimum cost of getting bitmask b.
2. For each new card j, iterate through all possible bitmask and update S[b AND \(b_j\)]  to S[b] + cost[j] if it is lower.
3. Update our final answer with S[0] if it is lower.

Apparently we can also pass the system test using a naive DP on all GCDs, which implies to possibilities:
1. the number of GCDs are bounded at \( O(N^2)\), or
2. the test case used is rather weak

I provide both approaches for references.

Naive DP:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <cassert>
#include <map>
#include <set>
using namespace std;

/* MAYBE number of gcd s will be O(N^2) */
/* Accepted but maybe the test case is weak, or maybe number of gcd is really bounded at O(N^2) */
int N;
int u[303], v[303];
map<int,int> dp;
vector<int> st;
int gcd(int a, int b) {
    if(a < b) swap(a,b);
    if(b==0)return a;
    return gcd(b,a%b);
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&u[i]);
    }
    for(int i=0;i<N;++i){
        scanf("%d",&v[i]);
    }
    vector<int> tmp;
    for(int i=0;i<N;++i){
        for(int j=0;j<st.size();++j){
            int g = gcd(u[i],st[j]);
            if(dp.count(g)) {
                dp[g] = min(dp[g], v[i]+dp[st[j]]);
            } else {
                tmp.push_back(g);
                dp[g] = v[i] + dp[st[j]];
            }
        }
        if(dp.count(u[i])) {
            dp[u[i]] = min(dp[u[i]], v[i]);
        } else {
            tmp.push_back(u[i]);
            dp[u[i]] = v[i];
        }
        while(!tmp.empty()){
            st.push_back(tmp.back());
            tmp.pop_back();
        }
    }
    if(dp.count(1)){
        printf("%d\n", dp[1]);
    } else printf("-1\n");
    return 0;
}

Proper DP:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <cassert>
#include <map>
#include <set>
using namespace std;
int INF = (int) 1e9;
int mark[100000];
int N;
int dp[600];
int val[303], cost[303];
vector<int> primes;
vector<int> factors[303];
int main(){
    for(int i=2;i*i<=100000;++i){
        for(int j=2;i*j<=100000;++j){
            mark[i*j] = 1;
        }
    }
    for(int i=2;i<=100000;++i){
        if(mark[i]==0)primes.push_back(i);
    }
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&val[i]);
        bool isprime = true;
        for(int k=0;k<primes.size();++k){
            if(val[i]%primes[k])continue;
            isprime = false;
            factors[i].push_back(primes[k]);
        }
        if(isprime && val[i] != 1) factors[i].push_back(val[i]);
    }
    for(int i=0;i<N;++i){
        scanf("%d",&cost[i]);
    }
    int ans = INF;
    for(int k=0;k<N;++k){
        for(int i=0;i<600;++i)dp[i]=INF;
        dp[(1<<((int)factors[k].size()))-1] = cost[k];
        for(int i=0;i<N;++i){
            if(i == k) continue;
            int bm = 0;
            for(int j=0;j<factors[k].size();++j){
                for(int jj=0;jj<factors[i].size();++jj){
                    if(factors[k][j]==factors[i][jj]){
                        bm |= (1<<j);
                        break;
                    }
                }
            }
            for(int j=0;j<(1<<9);++j){
                int g = bm & j;
                dp[g] = min(dp[g], dp[j] + cost[i]);
            }
        }
        ans = min(ans, dp[0]);
    }
    if(ans != INF) {
        printf("%d\n",ans);
    }else{
        printf("-1\n");
    }
    return 0;
}