Longest chain (Editorial)

Editorial: Longest Chain

Problem Interpretation

We are asked to find the size of the largest subset of a list of positive integers such that its elements can be arranged into a chain where for every consecutive pair $(x,y)$, one divides the other:

[ x y  or  y x ]

Since N \le 17, the number of elements is small enough to allow checking all subsets with bitmask dynamic programming.

Key Observations

• For each subset of elements, we can try to build chains ending at different elements.

• We define a DP state as follows: [ dp[mask][i] = 1 ] if there exists a valid chain using exactly the elements in "mask" ending with element $i$.

• We can transition by adding a new element $nxt$ not in the current mask, if it is divisible with the last element: [ a_last a_nxt  or  a_nxt a_last ]

DP Initialization

[ dp[1 i][i] = 1  for all i ]

Transition

For every mask and last element:

[ if dp[mask][last] = 1 then for all nxt not in mask: ] [ if a[last] a[nxt] or a[nxt] a[last], then dp[mask|(1«nxt)][nxt]=1 ]

Answer Computation

The maximum size of a chain is the largest popcount of a mask where dp[mask][last] = 1 for some last.

Complexity

[ O(2^N N^2),  N 17 ]

This is efficient for the problem constraints.

C++ Solution Code

#include <bits/stdc++.h>
using namespace std;

void solve(int tc){
    int N; cin >> N;
    vector<long long>a(N);
    for(int i=0;i<N;i++) cin>>a[i];

    int M = 1<<N;
    vector<vector<char>> dp(M, vector<char>(N,0));
    for(int i=0;i<N;i++) dp[1<<i][i]=1;

    int ans=1;

    for(int mask=1; mask<M; mask++){
        for(int last=0; last<N; last++){
            if(!dp[mask][last]) continue;
            ans = max(ans, __builtin_popcount(mask));

            for(int nxt=0; nxt<N; nxt++){
                if(mask & (1<<nxt)) continue;
                if(a[last]%a[nxt]==0 || a[nxt]%a[last]==0)
                    dp[mask | (1<<nxt)][nxt] = 1;
            }
        }
    }

    cout << "Case #" << tc << ": " << ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    for(int i=1;i<=T;i++){
        solve(i);
        cout << "\n";
    }
}