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

• -3

 » 11 months ago, # |   -31 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 →   -28 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.
•  » » » 11 months ago, # ^ |   +5 I think the time complexity is (2*n C n) * n!
•  » » 11 months ago, # ^ | ← Rev. 2 →   -19 [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 →   +10 Spoiler$dp[\text{mask}\mid i \mid j] = dp[mask] + gcd(a[i],a[j])$
 » 11 months ago, # |   -11 blank_manash Bitmask DP is cool~This code may help you dhana_sekar
•  » » 6 months ago, # ^ |   0 There is no need for the outer most for loop which reduces reduce the time complexity by a factor of n.
 » 11 months ago, # |   +2 I suppose, this task can be solved in polynomial time: this task is simply a maximum weight matching problem. It can be solved using Edmonds algorithm. But, of course, when you have n<=20, you can solve it in O(C(2n, n) × n).
•  » » 2 months ago, # ^ |   0 Wind_Eagle ,can you share some resource for maximum matching problem in weighted graphs?
•  » » » 2 months ago, # ^ |   0 https://en.wikipedia.org/wiki/Maximum_weight_matchingJust copy some solution from some chinese OJ, that's what I did last time it appeared in codechef long
•  » » » » 2 months ago, # ^ | ← Rev. 7 →   0 Edit : didn't notice it's not bipartite. If we create bipartite graph and put all vertices in left and same vertices on right , and apply hungarian can we prove that answer will be double of the optimal cost which we get from maximum matching.
•  » » » » » 2 months ago, # ^ |   0 The graph isn't bipartite here.
 » 6 months ago, # |   0 can you tell me where you saw this problem?
 » 2 months ago, # | ← Rev. 4 →   0 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[0]][index[1]]; } 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[0]]); //pairing 0th set bit to kth set dp[j] = max(dp[j] , gcdd[index[0]][index[k]] + dp[val] ); } } } cout<
•  » » 2 months ago, # ^ |   0 A 400 factor should not affect the run time a lot I believe. Also (I have not seen the other submission) it might be the case that his has a smaller constant factor.