Welcome to Subscribe On Youtube

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

1815. Maximum Number of Groups Getting Fresh Donuts

Level

Hard

Description

There is a donuts shop that bakes donuts in batches of batchSize. They have a rule where they must serve all of the donuts of a batch before serving any donuts of the next batch. You are given an integer batchSize and an integer array groups, where groups[i] denotes that there is a group of groups[i] customers that will visit the shop. Each customer will get exactly one donut.

When a group visits the shop, all customers of the group must be served before serving any of the following groups. A group will be happy if they all get fresh donuts. That is, the first customer of the group does not receive a donut that was left over from the previous group.

You can freely rearrange the ordering of the groups. Return the maximum possible number of happy groups after rearranging the groups.

Example 1:

Input: batchSize = 3, groups = [1,2,3,4,5,6]

Output: 4

Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1st, 2nd, 4th, and 6th groups will be happy.

Example 2:

Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6]

Output: 4

Constraints:

  • 1 <= batchSize <= 9
  • 1 <= groups.length <= 30
  • 1 <= groups[i] <= 10^9

Solution

The aim of this problem is to find a permutation of groups such that the number of prefix sums of groups that can be divisible by batchSize is the most. Use dynamic programming with compressed states to solve this.

  • class Solution {
    public int maxHappyGroups(int batchSize, int[] groups) {
        long state = 0;
        int mod0 = 0;
        for (int group : groups) {
            group %= batchSize;
            if (group == 0)
                mod0++;
            else
                state += 1L << (group * 5);
        }
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        return mod0 + dp(0, state, batchSize, map);
    }

    public int dp(int curr, long state, int batchSize, Map<Long, Integer> map) {
        if (!map.containsKey(state)) {
            if (state == 0)
                map.put(state, 0);
            else {
                int val = 0;
                for (int i = 1; i < batchSize; i++) {
                    if ((state >>> (i * 5)) % 32 != 0) {
                        int nextVal = dp((curr + i) % batchSize, state - (1L << (i * 5)), batchSize, map);
                        val = Math.max(val, curr != 0 ? nextVal : nextVal + 1);
                    }
                }
                map.put(state, val);
            }
        }
        return map.get(state);
    }
}

############

class Solution {
    private Map<Long, Integer> f = new HashMap<>();
    private int size;

    public int maxHappyGroups(int batchSize, int[] groups) {
        size = batchSize;
        int ans = 0;
        long state = 0;
        for (int g : groups) {
            int i = g % size;
            if (i == 0) {
                ++ans;
            } else {
                state += 1l << (i * 5);
            }
        }
        ans += dfs(state, 0);
        return ans;
    }

    private int dfs(long state, int mod) {
        if (f.containsKey(state)) {
            return f.get(state);
        }
        int res = 0;
        for (int i = 1; i < size; ++i) {
            if ((state >> (i * 5) & 31) != 0) {
                int t = dfs(state - (1l << (i * 5)), (mod + i) % size);
                res = Math.max(res, t + (mod == 0 ? 1 : 0));
            }
        }
        f.put(state, res);
        return res;
    }
}

  • // OJ: https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/
// Time: O(N^B)
// Space: O(B)
// Ref: https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/discuss/1140644/C%2B%2B-0-ms%3A-Greedy-%2B-DP
class Solution {
    map<vector<int>, int> dp;
    int dfs(vector<int> &cnt, int left) {
        auto it = dp.find(cnt);
        if (it != end(dp)) return it->second;
        int ans = 0, B = cnt.size();
        for (int i = 1; i < B; ++i) {
            if (--cnt[i] >= 0) ans = max(ans, (left == 0) + dfs(cnt, (B + left - i) % B));
            ++cnt[i];
        }
        return dp[cnt] = ans;
    }
public:
    int maxHappyGroups(int B, vector<int>& A) {
        vector<int> cnt(B);
        int ans = 0;
        for (auto &n : A) {
            n %= B;
            if (n == 0) ++ans;
            else if (cnt[B - n]) {
                --cnt[B - n];
                ++ans;
            } else ++cnt[n];
        }
        return ans + dfs(cnt, 0);
    }
};

  • class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        @cache
        def dfs(state, mod):
            res = 0
            x = int(mod == 0)
            for i in range(1, batchSize):
                if state >> (i * 5) & 31:
                    t = dfs(state - (1 << (i * 5)), (mod + i) % batchSize)
                    res = max(res, t + x)
            return res

        state = ans = 0
        for v in groups:
            i = v % batchSize
            ans += i == 0
            if i:
                state += 1 << (i * 5)
        ans += dfs(state, 0)
        return ans



  • func maxHappyGroups(batchSize int, groups []int) (ans int) {
	state := 0
	for _, v := range groups {
		i := v % batchSize
		if i == 0 {
			ans++
		} else {
			state += 1 << (i * 5)
		}
	}
	f := map[int]int{}
	var dfs func(int, int) int
	dfs = func(state, mod int) int {
		if v, ok := f[state]; ok {
			return v
		}
		res := 0
		x := 0
		if mod == 0 {
			x = 1
		}
		for i := 1; i < batchSize; i++ {
			if state>>(i*5)&31 != 0 {
				t := dfs(state-1<<(i*5), (mod+i)%batchSize)
				res = max(res, t+x)
			}
		}
		f[state] = res
		return res
	}
	ans += dfs(state, 0)
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions