# NPLFAGL - Editorial

Practice

Contest

Author: nmalviya1929
Editorialist: nmalviya1929

MEDIUM

### 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++){
}

``````

Check editorial code for more understanding.

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.

### RELATED PROBLEMS:

1 Like

What is overall complexity required?

1 Like

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).

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