# DP problem interesting doubt

yes N <=10 but if N = 10 means, 20 elemts there in array given in prob statement

Oh my bad, yeah then that would also do the job since 10! is reasonably small.

plz explain

No, you are correct. If n=10 then there are 20 elements

Yeah, then bitmask dp is the only workaround I can think of.

Okay so assuming you have a decent grasp in bitmask dp, this problem doesn’t require much explanation.
Some notation.

DP[i] : is the maximum score we can achieve by reaching state i.
c(i,j) boolean function which returns whether j th bit in i is set or not.
B(i) is the number of set bits in i
F(i)=(N-B(i))/2+1 is the round number of state i .
Transitions are trivial and will look like.

\displaystyle DP[i \oplus j \oplus k] = \max\limits_{c(i,j)=1,c(i,k)=1} (DP[i]+F(i)\times \gcd(A[j],A[k])

Final answer would just be DP[0]

1 Like

My approach:
Let dp[round][mask] denote the maximum score after round rounds for the subset mask.
Obviously,
dp[round][mask] = \max{(dp[round][mask], \ dp[round - 1][mask \oplus 2^i \oplus 2^j] + \gcd{(a_i, \ a_j) \times round})} \ (i \neq j)
and the ith and jth bits are set in mask.
The final answer is dp[n][2^{2n} - 1].

Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define mp make_pair

template <typename Container>
void Print(Container& container) {
auto Start = container.begin(), End = container.end();
while (Start != End) cout << *(Start++) << " ";
cout << '\n';
}

template <typename T> using oset = tree <pair <T, T>, null_type, less <pair <T, T>>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
void print(T&& t) {cout << t << '\n';}

template <typename T, typename... Args>
void print(T&& t, Args&&... args) {
cout << t << " ";
print(forward<Args>(args)...);
}

inline void solve() {
int n;
cin >> n;
int rounds = n, total = (n << 1);
int64_t dp[rounds + 1][1 << total];
memset(dp, 0, sizeof dp);
int64_t a[total];
for (int i = 0; i < total; ++i) cin >> a[i];
for (int round = 1; round <= rounds; ++round) {
for (int i = 0; i < total; ++i) {
for (int j = 0; j < total; ++j) {
if ((mask & (1 << i)) && (mask & (1 << j)) && i != j) {
dp[round][mask] = max(dp[round][mask], dp[round - 1][mask ^ (1 << i) ^ (1 << j)] + __gcd(a[i], a[j]) * round);
}
}
}
}
}
cout << dp[rounds][(1 << total) - 1] << '\n';
}

int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
for (int test = 1; test <= T; ++test) {
// cout << "Case #" << test << ": ";
solve();
}
}

2 Likes

thank u so much. very clear

1 Like
2 Likes

try this

CODE
class Solution {
public:
int maxScore(vector<int>& a) {
int n = a.size() ;
#define vt vector
vt<int>dp((1<<n))  ;
for(int i=(1<<n)-1;~i;--i){
int c=__builtin_popcount(i) ;
if(c&1)
continue  ;
int f = (n-c)/2+1 ;   // round number calculation
for(int j=0;j<n;j++){
if(!(i>>j&1))
continue ;
for(int k=j+1;k<n;k++){
if(!(i>>k&1))
continue  ;
dp[i^(1<<k)^(1<<j)]=max(dp[i^(1<<k)^(1<<j)],dp[i]+f*__gcd(a[j],a[k])) ;
}
}
}
return dp[0] ;
}
};

2 Likes

workig thanks

Time complexity of this sol. is O(n * n * log(n))

vector used(nums.size(), false);

vector<vector<int>>pairs;
for (int i = 0; i < nums.size() - 1; i++) {
for (int j = i + 1; j < nums.size(); j++) {
pairs.push_back({__gcd(nums[i], nums[j]), i, j});
}
}
sort(pairs.begin(), pairs.end(), [](vector<int>&a, vector<int>&b) {
return a[0] > b[0];
});
int res = 0;
int i = nums.size() / 2;
for (vector<int>& p : pairs) {
if (used[p[1]] || used[p[2]]) continue;
res += p[0] * i--;
used[p[1]] = true;
used[p[2]] = true;
}
return res;
}
1 Like

If I’m not mistaken then isn’t this solution \mathcal{O}(N^32^N)? This won’t fit in the time limit I think.

no. O(n * n * 2^(2*n))
i changed to
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
it passed

If you don’t mind can you share the original source of this code so that we can ensure its correctness ?

Yes, it can be speeded up by precomputing GCDs and only making pairs when the number of set bits in the mask are equal to 2 * round.

Code
class Solution {
public:
int maxScore(vector<int>& nums) {
int n = nums.size() >> 1;
int rounds = n, total = (n << 1);
int32_t dp[rounds + 1][1 << total];
memset(dp, 0, sizeof dp);
int32_t gcd[total][total];
for (int i = 0; i < total; ++i) {
for (int j = i + 1; j < total; ++j) {
gcd[i][j] = __gcd(nums[i], nums[j]);
}
}
for (int round = 1; round <= rounds; ++round) {
if (__builtin_popcount(mask) == (round << 1)) {
for (int i = 0; i < total; ++i) {
if (mask & (1 << i)) {
for (int j = i + 1; j < total; ++j) {
if (mask & (1 << j)) {
dp[round][mask] = max(dp[round][mask], dp[round - 1][mask ^ (1 << i) ^ (1 << j)] + gcd[i][j] * round);
}
}
}
}
}
}
}
return dp[rounds][(1 << total) - 1];
}
};


This runs in 36 ms.

it from leetcode. i think we cant provide submision link. but u can check. in accepted sol details, in Accepted Solutions Runtime Distribution, clcik 1st bar, u can see the solution

Isn’t it still \mathcal{O}(4N^32^{2N}) though ?

my question. this solution doing greedy. how this not failing but passing?? @cubefreak777