BAKERY Editorial

Let us iterate the second we are at, from t=0 to t=n-1.

Let T_0 \le T_1 \le \cdots \le T_{m-1} be the random variables representing the first moment when the various employees become free after all the customers entered at times 0, 1, \dots, t-1 have been served. If an employee is already free, we set T_0=t.

We would like to understand how the random variables change when we move from t to t+1. Let T'_0,\dots, T'_{m-1} be the random variables at time t+1.

If after t seconds noone enters, then T'_i = max(t+1, T_i).
If someone enters, then T'_i=max(t+1, T_{i+1}) for each i=0,\dots,m-2 and T'_{m-1}=T_0 + d (it is fundamental that all the employees spend the same time serving customers, so that we can be sure that the one serving becomes the last one getting free).

Hence, if we know the probability distribution of each T_j, we can compute the probability distribution of T'_i for each i.
Moreover, if we know the probability distribution of T_0, we can compute the expected value of the waiting times (indeed the waiting time of the customer entering at time t, who exist with probability p, is \mathbb E[T_0]-t). Therefore, we don’t need to keep track of the joint distributions of (T_0,T_1,\dots,T_{m-1}) as it is sufficient to keep track of the distributions of each random variable.

Since the probability distribution of a random variable which takes values in [a,b] can be encoded in a vector of length b-a+1 and T_i\in[t, \frac{td}m], the above mentioned algorithm can be implemented with complexity O(n^2d), which is too slow. Let us optimize this solution.

If pd>m, after an initial time, a huge queue will be formed and the employees will work non-stop. Indeed if the m employees work non-stop for t minutes, they serve \frac{mt}{d} customers, while in the same amount of time \approx pt customers enter the shop. Since pt>\frac{mt}d, the queue keeps growing (with high probability).

On the other hand, if pd < m we don’t expect a big queue (because if there is a long queue, the amount of customers processed in a certain amount of time is at least the same as the expected number of customers entering the bakery in the same amount of time) and thus if we ignore the negligible tails we expect the random variables T_i to be concentrated on a relatively small interval.

The two observations provide two optimizations which, when used simultaneously, are sufficient to solve the problem. Morally, if there is a short queue the naïve solution is fast enough, if there is a long queue the problem simplifies.

  • Short queue:
    Instead of keeping the whole probability distribution of T_j, we keep only the ``likely values’’ (i.e., the values with probability \ge 10^{-15}) and speed up the algorithm to O(nm\#\{\text{likely values}\}).

  • Long queue: If, at a certain step of the algorithm we see that the probability of an employee being free is extremely small (i.e., \mathbb P(T_0=t) < 10^{-15}), we can assume that from this moment on the employees will work non-stop. In this case, we can exploit the fact that we don’t need to keep the whole distribution of T_0,T_1,\dots,T_{m-1} because the expected values are sufficient (indeed we have T'_i = \frac{T_i + T_{i+1}}2 for 0\le i < m-1 and T'_{m-1} = \frac{T_{m-1} + T_0 + d}{2}).

1 Like