Question

1815. Maximum Number of Groups Getting Fresh Donuts

中文文档

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] <= 109

Solutions

Solution 1: Greedy + State Compression + Memorized Search

The problem actually asks us to find an arrangement order that maximizes the number of groups whose prefix sum (referring to "number of people" here) modulo $batchSize$ equals $0$. Therefore, we can divide all customers into two categories:

• Customers whose number is a multiple of $batchSize$. These customers will not affect the donuts of the next group of customers. We can greedily arrange these groups of customers first, so these groups of customers will be happy. The "initial answer" is the number of these groups.
• Customers whose number is not a multiple of $batchSize$. The arrangement order of these customers will affect the donuts of the next group of customers. We can take the modulo $batchSize$ for the number of people $v$ in each group here, and the remainders form a set. The range of element values in the set is $[1,2…,batchSize-1]$. The maximum length of the $groups$ array is $30$, so the maximum number of each remainder does not exceed $30$. We can use $5$ binary bits to represent the quantity of a remainder, and the maximum $batchSize$ is $9$, so the total number of binary bits required to represent these remainders and their quantities is $5\times (9-1)=40$. We can use a $64$-bit integer $state$ to represent it.

Next, we design a function $dfs(state, mod)$, which represents the number of groups that can be happy when the arrangement state is $state$ and the current prefix remainder is $mod$. Then our "initial answer" plus $dfs(state, 0)$ is the final answer.

The implementation logic of the function $dfs(state, mod)$ is as follows:

We enumerate each remainder $i$ from $1$ to $batchSize-1$. If the quantity of the remainder $i$ is not $0$, we can subtract $1$ from the quantity of the remainder $i$, add $i$ to the current prefix remainder and take modulo $batchSize$, then recursively call the function $dfs$ to find the optimal solution of the sub-state, and take the maximum value. Finally, check whether $mod$ is $0$. If it is $0$, we return after adding $1$ to the maximum value, otherwise we directly return the maximum value.

During the process, we can use memorized search to avoid repeated calculation of states.

The time complexity does not exceed $O(10^7)$, and the space complexity does not exceed $O(10^6)$.

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

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;
  }
}

class Solution {
public:
  int maxHappyGroups(int batchSize, vector<int>& groups) {
    using ll = long long;
    unordered_map<ll, int> f;
    ll state = 0;
    int ans = 0;
    for (auto& v : groups) {
      int i = v % batchSize;
      ans += i == 0;
      if (i) {
        state += 1ll << (i * 5);
      }
    }
    function<int(ll, int)> dfs = [&](ll state, int mod) {
      if (f.count(state)) {
        return f[state];
      }
      int res = 0;
      int x = mod == 0;
      for (int i = 1; i < batchSize; ++i) {
        if (state >> (i * 5) & 31) {
          int t = dfs(state - (1ll << (i * 5)), (mod + i) % batchSize);
          res = max(res, t + x);
        }
      }
      return f[state] = res;
    };
    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
}

Solution 2

class Solution:
  def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
    @cache
    def dfs(state, x):
      if state == mask:
        return 0
      vis = [False] * batchSize
      res = 0
      for i, v in enumerate(g):
        if state >> i & 1 == 0 and not vis[v]:
          vis[v] = True
          y = (x + v) % batchSize
          res = max(res, dfs(state | 1 << i, y))
      return res + (x == 0)

    g = [v % batchSize for v in groups if v % batchSize]
    mask = (1 << len(g)) - 1
    return len(groups) - len(g) + dfs(0, 0)