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

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.

~~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 approach

Suppose dp[M] stores the answer for a mask M of elements. Now you add 2 more elements to it

aandb.Case 1Element

aandbpair up with each other. The transition is`dp[M|a|b] = gcd(a,b) + dp[M]`

Case 2Element

aandbpair up with elementsxandyrespectively. The transition is`dp[M|a|b] = max(gcd(a,x) + gcd(b,y) + dp[M^x^y], dp[M|a|b]`

for all possiblexandy.I think the time complexity is (2*n C n) * n!

[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

Spoiler$$$dp[\text{mask}\mid i \mid j] = dp[mask] + gcd(a[i],a[j])$$$

blank_manash Bitmask DP is cool~

This code may help you dhana_sekar

There is no need for the outer most for loop which reduces reduce the time complexity by a factor of n.

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).

Wind_Eagle ,can you share some resource for maximum matching problem in

weighted graphs?https://en.wikipedia.org/wiki/Maximum_weight_matching

Just copy some solution from some chinese OJ, that's what I did last time it appeared in codechef long

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.

The graph isn't bipartite here.

can you tell me where you saw this problem?

why this O(n*(2^n)) solution takes almost same time as O(n^3*(2^n)) solution given by dna049?

codeA 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.