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
#define random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
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 mask = 0; mask < (1 << total); ++mask) {
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
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))
can u explain little only about this
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) {
for (int mask = 0; mask < (1 << total); ++mask) {
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 ?
Will this solution pass this test case
[415,230,471,705,902,87] .
Share full formatted code so that I can stress test this. For some reason I doubt it’s correctness.
hey man great. the solution failed for your test case. but in leetcode, in accepted submissions the solution displaing under accepted sol. with 0ms time
Yeah that’s why. Test cases for this problem may be weak. Bitmask DP is the only solution.
Yes, to me it looks like \mathcal{O}(n^32^{2n}), but it’s much faster because it doesn’t compute unnecessarily. For example, when I precomputed GCDs, it ran in 440 ms (TLE without precomputation). Then, I added the popcount condition which reduced it to 40 ms. Using 32 bit integers reduced it to 36 ms.