### dhana_sekar's blog

By dhana_sekar, history, 11 months ago, You are given 2*n elements. You have to distribute the 2*n elements into n groups (each group has size exactly equal to 2) such that sum of gcd of the n groups is maximum. The task is to print the gcd of the n groups(whose sum is maximum possible).

input constraints: a[i]<=10**9 and 2*n<=20 #gcd, Comments (15)
 » Hint 1Bitmask DP Hint 2The states are elements chosen in one of the array. Hint 3The transition is adding an element in the array. Hint 4If you are still reading upto here, you simply need more practice.
•  » » 11 months ago, # ^ | ← Rev. 3 →   Or, you can divide 2*n numbers into 2 subsets of N elements each. Keep the first set as it is after generating it.Generate all permutations of the second set and take pairwise GCD with the first set. A better approachSuppose dp[M] stores the answer for a mask M of elements. Now you add 2 more elements to it a and b. Case 1Element a and b pair up with each other. The transition is dp[M|a|b] = gcd(a,b) + dp[M] Case 2Element a and b pair up with elements x and y respectively. The transition is dp[M|a|b] = max(gcd(a,x) + gcd(b,y) + dp[M^x^y], dp[M|a|b] for all possible x and y.
•  » » » I think the time complexity is (2*n C n) * n!
•  » » 11 months ago, # ^ | ← Rev. 2 →   [user:@kuhhaku]The task is not to divide 2*n elements into 2 groups with each group of size n, but rather to divide the given 2*n elements into n groups with each group of size 2
•  » » » 11 months ago, # ^ | ← Rev. 2 →   Spoiler$dp[\text{mask}\mid i \mid j] = dp[mask] + gcd(a[i],a[j])$
 » 2 months ago, # | ← Rev. 4 →   why this O(n*(2^n)) solution takes almost same time as O(n^3*(2^n)) solution given by dna049? code#include using namespace std; typedef long long ll; typedef vector vll; typedef vector vvll; typedef pair pll; typedef vector vpll; #define fi first #define se second #define mp make_pair #define pb push_back #define sep '#' #define forl(i,k,n) for(ll i=k;i>t; while(t--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs\n";return 0; } void solve() { ll n; cin>>n; n*=2; vector dp(1< pow2; vector> gcdd(n,vll(n,1)); vector> a(n+1); for(auto &i: b) cin>>i; //some preprocessing of gcd and powers of 2 forl(i,0,n) { forl(j,0,n) { gcdd[i][j] = __gcd(b[i],b[j]); } } forl(i,0,25) { pow2.push_back(1< x = i; vll index; forl(j,0,25) { if(x[j]==1) index.push_back(j); } dp[i] = gcdd[index][index]; } for(int i=4;i<=n;i+=2) { for(auto j:a[i]) { //index of set bits of j vll index; forl(k,0,25) { if(j&(pow2[k])) index.push_back(k); } forl(k,1,i) { ll val = j; //removing 0th set bit and kth set bit val ^= (pow2[index[k]]); val ^= (pow2[index]); //pairing 0th set bit to kth set dp[j] = max(dp[j] , gcdd[index][index[k]] + dp[val] ); } } } cout<