DP problem interesting doubt

general
44

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.

45

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

46

Yeah that’s why. Test cases for this problem may be weak. Bitmask DP is the only solution.

47

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.

48

Yeah it’s in fact optimized \mathcal{O}(N^32^{N}) . That precomputation gave a huge boost in runtime but not in the complexity . You can actually get rid of that extra N by noticing that the round of any state can be computed from the number of set bits in the the state. Round number will just be setBits(i)/2+1 (or unset bits depends on your implementation)

1 Like
49

Yes, I tried removing the extra N that way, but I wasn’t able to. To be specific, I don’t know how to iterate over masks with two set bits, then masks with four set bits, and so on. Do you know how to do this?

50

These 2 should give a fair idea. Ping me if you don’t get it.

1 Like
51

Thanks, I understood. Using unset bits instead of set bits is very cool (and new to me). Great solution!

1 Like
52

I think greedy might work here, the case which you have given that is a tie, you have gcd as 6 but you broke the tie randomly, I am thinking if we can break the tie in some way which can give optimal solution.

Imagine about the optimal solution, the coefficient of each round will be in non-decreasing order starting from first round.

53

This question i found on leetcode : - LeetCode

1 Like
54

Today I read about bitmask dp. Can you tell its comp

int fun(int mask, int round)
    {
        if(mask==all)
            return 0;
        
        if(dp[mask][round]!=-1)
            return dp[mask][round];
        
        int ans=0;
        for(int i=0;i<N;i++)
        {
            if( ( (mask>>i) & 1 ) == 0)
            {
                for(int j=i+1;j<N;j++)
                {
                    if( ((mask>>j) & 1)==0 && j!=i)
                    {
                        ans=max(ans, fun(( mask | (1<<j) | (1<<i) ), round+1) + round *__gcd(num[i],num[j]));
                    }
                }
            }
        }
        return dp[mask][round]=ans;
    }
55

I think it’s amortized \mathcal{O}(N^22^NlogA)

56

What about round

57

Oh right, my bad, it’s \mathcal{O}(N^32^NlogA)