NPLFAGL - Editorial

general
1

PROBLEM LINK:

Practice

Contest

Author: nmalviya1929
Editorialist: nmalviya1929

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP with Bitmasking

PROBLEM:

We have to buy N different gadgets on N different days buying one gadget each day. Price for buying ith gadget on jth day is (cost of ith gadget on jth day * cost of previous gadget bought on (j-1)th day).

QUICK EXPLANATION:

We have to maintain previously brought gadget and mask representing all the gadgets brought so far in dp. Current day is not required in dp state as it can be found using number of sets bits in mask.

EXPLANATION:

Let P[i][j] denote price of jth gadget on ith day. We can maintain a mask to represent gadgets brought so far as well as index of gadget brought on previous day.
Now current day will be equal to (number of set bits in mask) +1.

Iterate over all the items not brought so far and call the function recursively.

 

        for(int i=0;i<n;i++){
            if(((mask>>i)&1)==0)
            dp[mask][prev]=min(dp[mask][prev],p[curr][i]*p[curr-1][prev]+func(mask|(1<<i),i));
        }

Check editorial code for more understanding.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

RELATED PROBLEMS:

1 Like
2

What is overall complexity required?

1 Like
3

Can’t we also solve it this way: for a given mask, iterate over all of the set bits and look for the cheapest way to arrive at that mask with the ith item being the last bought item.
so something like this:
for(auto j:sb[i])
{
dp[i][j]=1000000000000;
for(auto k:sb[i]){
if(j==k) continue;
dp[i][j]=min(dp[i][j], dp[(i&(~(1<<j)))][k] + prices[j][sb[i].size()]*prices[k][sb[i].size()-1]);
}
}
where sb is an array of vectors storing all of the bits set in the ith number, j is the last item bought and k is the item we bought before the jth one (just used for the transition). The state would be dp[mask][last_item]. I’m getting WA with this approach (though I can’t understand why).

4

where can i find good tutorials on dp with bitmasking except hackerearth(i have read it )