dhana_sekar's blog

By dhana_sekar, history, 11 months ago, In English

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

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it -31 Vote: I do not like it
Hint 1
  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it -28 Vote: I do not like it

    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 a and b.

    Case 1
    Case 2
  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it -19 Vote: I do not like it

    [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   Vote: I like it +10 Vote: I do not like it
      Spoiler
»
11 months ago, # |
  Vote: I like it -11 Vote: I do not like it

blank_manash Bitmask DP is cool~

This code may help you dhana_sekar

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 7   Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The graph isn't bipartite here.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can you tell me where you saw this problem?

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.