[Leetcode] 1981. Minimize the Difference Between Target and Chosen Elements

 1981. Minimize the Difference Between Target and Chosen Elements

You are given an m x n integer matrix mat and an integer target.

Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized.

Return the minimum absolute difference.

The absolute difference between two numbers a and b is the absolute value of a - b.

Constraints:

m == mat.length

n == mat[i].length

1 <= m, n <= 70

1 <= mat[i][j] <= 70

1 <= target <= 800

Analysis:

Let look at the brute-force way: there are n^m combinations in total. If n == m == 70, this number could be as large as 70^70, which is too overwhelming...

We need to figure out some way with reduced complexity.

Bitset would be a good choice to this question. The key idea is to use the index of the bits representing the sums.

For example, if a bitset bt[80] = 1, meaning the bit at the index of 80 is 1, then there is a sum equal to 80.

Bitset has an important operation: bit shift.

When we need to add a number to many others sums, then bit shift would greatly reduce the time complexity: since one bit shift operation would shift all the bits in a bitset by only one operation! More details can be found here.

In this question, initially we can have a bitset to record all the elements in the first row: basically set the corresponding bits as 1.

Then move on to the next row. 

For each number in the second row, we need to add it to all the possible sums stored in the bitset from the previous row. Bit shift can perfectly handle this. After performing this bit shift operation to each number in the row, we need to store all the possible sums into a new bitset, which is needed for the next row. An or (|) operation is good enough for this.

We just repeat this step row by row, to the last row.

After finishing all of this, all the possible sums are stored in the last bitset. We just need to check all the possible sums, to see which one gives the minimum abs(sum - target).

See the code below:

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat.front().size(), cs = 40000, res = cs;
        bitset<40000> bt;
        for(int i=0; i<n; ++i) bt[mat[0][i]] = 1;
        for(int i=1; i<m; ++i) {
            bitset<40000> pre = bt, nxt;
            for(int j=0; j<n; ++j) {
                nxt |= pre << mat[i][j];
            }
            bt = nxt;
        }
        for(int i=0; i<cs; ++i) {
            if(bt[i]) res = min(res, abs(i-target));
        }
        return res;
    }
};

This question can also be solved by dfs + memo.  

memo[r][sum] means: the minimum abs(possible sums - target) starting with row number r and the starting sum value as sum.

The optimization lines and trim lines are needed, otherwise, it cannot pass the OJ.

See the code below:

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat.front().size();
        for(auto &a : mat) {
            sort(a.begin(), a.end());
        }
        sort(mat.begin(), mat.end(), greater());
        memset(memo, -1, sizeof(memo));
        return dfs(mat, 0, 0, target);
    }
private:
    int memo[71][4901];
    int dfs(vector<vector<int>>& ms, int r, int sum, int& target) {
        if(r == ms.size()) {
            return abs(sum - target);
        }
        if(memo[r][sum] != -1) return memo[r][sum];
        int res = INT_MAX;
        for(int i=0; i<ms[r].size(); ++i) {
            if(sum + ms[r][i] > target && abs(sum + ms[r][i] - target >= res)) break;
            res = min(res, dfs(ms, r+1, sum + ms[r][i], target));
        }
        return memo[r][sum] = res;
    }
};