Bitmask DP

Considerations?

• Do I iterate over set bits and remove them? Is optimal structure a vine
• Do I iterate over submasks and remove them? Is optimal structure a tree

Think bitmask dp, when iterating over permutations of processing order would works. And simplification to operation over “sets” instead of permutations is possible.

pattern for type 1 - element addition

f(i) = agg{ f(i / elem) + merge cost( i, elem ) } for all elem in i

pattern for type 2 - set addition

f(i) = agg{ f(i / sub), f(sub), merge cost( i/sub, sub ) } for all sub = submasks in i

Variations

Other dimensions can get added based on what the problem needs to uniquely describe the reduced state.

Submask iteration

start at mask and go down to 0. You need to & to zero out non submask bits and this & decreases value. So you process high to low so that duplicates are not processed. Break when 0.

for(int sub = mask; ; sub = (sub-1) & mask ){
	...
	if( sub == 0 ) break;
}

Merge K Sorted Lists with Median Costs

k sorted lists, merge two cost = len a + len b + abs diff of median a, median b. Min cost.

Subproblems

• precompute medians of mask
• median of k lists via binary search

Rem: masks to start at 1, submasks must be proper subsets.

Also note the continous val binary search, to find median, it should push towards min. So the first branch must be >= based is valid as this will allow to push.

Think: 20 - 29 as valid median range. This gives you 20, else you get 29.

code

class Solution {
  public:
    long long minMergeCost(vector<vector<int>> &lists) {
// brute force is 12 factorial
// observation : state of lists is determined by set unions that have been done so far
// optimal structure is a tree so submask iteration
// I need to efficiently get len(mask), median(mask) to get cost(mask a, mask b)
#define int long long
        int N = lists.size();
        int MASK_N = (1ll << N);
        const int INF = (int)1e18;
        vector<int> len(MASK_N), mid(MASK_N);

        // preprocess
        {
            for (int mask = 1; mask < MASK_N; mask++) {
                int tot_len = 0;
                int num_min = INF, num_max = -INF;

                // range bin search based k list median
                // REM: start at 1, else search will hit assert
                for (int i = 0; i < N; i++) {
                    if (!((mask >> i) & 1))
                        continue;

                    auto &list = lists[i];
                    tot_len += (int)list.size();
                    num_min = min(num_min, (int)list[0]);
                    num_max = max(num_max, (int)list.back());
                }

                int l = num_min, r = num_max;
                int cnt_needed = (tot_len - 1) / 2 + 1;
                int median = INF;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    int cur_cnt = 0;
                    for (int i = 0; i < N; i++) {
                        if (!((mask >> i) & 1))
                            continue;

                        int cnt =
                            upper_bound(lists[i].begin(), lists[i].end(), mid) - lists[i].begin();
                        cur_cnt += cnt;
                    }

                    if (cur_cnt >= cnt_needed) {
                        r = mid - 1;
                        median = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                assert(median != INF);

                mid[mask] = median;
                len[mask] = tot_len;
            }
        }

        vector<int> dp(MASK_N, INF);
        for (int i = 0; i < N; i++)
            dp[(1 << i)] = 0;

        for (int mask = 1; mask < MASK_N; mask++) {
            for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask) {
                int excl = (~sub) & mask;
                int cost = len[sub] + len[excl] + abs(mid[sub] - mid[excl]);
                dp[mask] = min(dp[mask], dp[excl] + dp[sub] + cost);
            }
        }

        return dp.back();
#undef int
    }
};