Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2305.html

2305. Fair Distribution of Cookies (Medium)

You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.

The unfairness of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.

Return the minimum unfairness of all distributions.

 

Example 1:

Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.

Example 2:

Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.

 

Constraints:

• 2 <= cookies.length <= 8
• 1 <= cookies[i] <= 105
• 2 <= k <= cookies.length

Related Topics:
Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Similar Questions:

• Split Array Largest Sum (Hard)
• Split Array with Equal Sum (Hard)
• Partition to K Equal Sum Subsets (Medium)
• Minimum XOR Sum of Two Arrays (Hard)
• The Number of Good Subsets (Hard)
• Minimum Number of Work Sessions to Finish the Tasks (Medium)
• Partition Array Into Two Arrays to Minimize Sum Difference (Hard)

Solution 1. DP

Brute force is assigning each bag to different children. So there are 8^8 ~= 2e7 ways and will get TLE.

The Brute force way has lots of duplicated computations. We can use DP to reduce such duplication.

Let dp[k][m] be the min unfairness of bags represented by bitmask m distributed to k children.

If we assign bags represented by m to a single child, the unfairness is sum(m), i.e. the sum of cookies in bags represented by m.

dp[1][m] = sum(m)

For dp[k][m], we can try m’s different subset s as the bags assigned to the last child, so this child get sum(s). The rest of bags represented by m-s are assigned to k-1 children.

dp[k][m] = min( max(dp[k-1][m-s], sum(s)) | s is a subset of m )

The answer is dp[K][(1<<N)-1].

// OJ: https://leetcode.com/problems/fair-distribution-of-cookies/
// Time: O(2^N * N + K * 3^N)
// Space: O(K * 2^N)
class Solution {
public:
    int distributeCookies(vector<int>& A, int K) {
        int N = A.size();
        vector<vector<int>> dp(K + 1, vector<int>(1 << N, INT_MAX));
        vector<int> sum(1 << N);
        for (int m = 1; m < (1 << N); ++m) {
            int s = 0;
            for (int i = 0; i < N; ++i) {
                if (m >> i & 1) s += A[i];
            }
            sum[m] = s;
            dp[1][m] = s;
        }
        for (int k = 2; k <= K; ++k) {
            for (int m = 1; m < (1 << N); ++m) {
                for (int s = m; s; s = (s - 1) & m) {
                    dp[k][m] = min(dp[k][m], max(dp[k - 1][m - s], sum[s]));
                }
            }
        }
        return dp[K][(1 << N) - 1];
    }
};

Solution 2. DP with Space Optimization

Since dp[k][m] only depends on dp[k-1][m-s], we can reduce the space for the dp array from K * 2^N to 2^N.

// OJ: https://leetcode.com/problems/fair-distribution-of-cookies/
// Time: O(2^N * N + K * 3^N)
// Space: O(2^N)
class Solution {
public:
    int distributeCookies(vector<int>& A, int K) {
        int N = A.size();
        vector<int> dp(1 << N, INT_MAX), next(1 << N), sum(1 << N);
        for (int m = 1; m < (1 << N); ++m) {
            int s = 0;
            for (int i = 0; i < N; ++i) {
                if (m >> i & 1) s += A[i];
            }
            sum[m] = s;
            dp[m] = s;
        }
        for (int k = 2; k <= K; ++k) {
            fill(begin(next), end(next), INT_MAX);
            for (int m = 1; m < (1 << N); ++m) {
                for (int s = m; s; s = (s - 1) & m) {
                    next[m] = min(next[m], max(dp[m - s], sum[s]));
                }
            }
            swap(dp, next);
        }
        return dp[(1 << N) - 1];
    }
};

All Problems

All Solutions