You are given an array of N integers (N is even), at each round you have to select 2 numbers $$$(A[i],A[j])$$$, and do $$$ Sum = Sum + GCD(A[i], A[j]) * round $$$, post calculating sum remove those 2 numbers from Array. What is the maximum possible sum you can obtain?
Round's value starts from 1.
Constraints
$$$ 2 \leq N \leq 20 $$$
$$$ 1 \leq A[i] \leq 1e9 $$$
I tried Bitmasking Dp ( $$$ O(2 ^N * N ^2) $$$ ) but got TLE.
Example :
2 3 5 9
1st Round — 2 5, Sum = GCD(2,5) * 1
2nd Round — 3 9, Sum = GCD(3,9) * 2
The maximum possible sum is 7
Any insights?
I did the same and got AC, u did it in recursive or iterative approach?
recursion
can u explain the solution i was only getting 15/25 tc
for mask : [1, 2^20]: for ith setbit in mask: for jth setbit in mask: dp[mask] = max(dp[mask], dp[mask ^ (1 << i) ^ (1 << j)] + (gcd(a[i],a[j]) * m))
where 'm' refers to the round number that can be found for every mask in constant time.
same problem
but it is having constraints as N <= 14.
N = 14, makes sense, N = 20 was too edgy
Even I also did the same thing and got TLE.
Here is an online version of it: https://leetcode.com/contest/biweekly-contest-48/problems/maximize-score-after-n-operations/
Precompute all GCDs
But isn't the worst-case time complexity the same ?
Yes, but the running time decreases significantly as calculating GCD is O(log n) and precomputing will help. I was also getting TLE in the start but after precomputing, the code worked fine
oh ok
how does this state work, dp[mask] = max gcd pairwise sum you can achieve from bits present in mask
i wrote code with this as state and it passed all test cases except one due to recursion
I also wrote dp like this dp[mask][R] = max gcd pairwise sum you can achieve from bits present in mask and the current round is R,
I feel that the second dp notation has correctness in it, but for the first case since the round information is missing
my code: https://ideone.com/2Q4I3m , same code after removing the second state which stores the round number also passed.
my doubt is around the correctness of the first dp notation where we are only memoizing the mask
Notice that popcount/2 + 1 is the round number for particular mask (ignoring odd bits masks), hence round is a redundant state and need not to be present