Code Problem

Found this problem in a Facebook group. It is likely a homework problem from an undergraduate computer science class.

Solution: Python 3.10

import math

chef = [2,2,5]
customer = [4,5,6,30,123456789012]

lcm_C = math.lcm(*chef)
fx = []
for i in range(lcm_C // min(chef)):
    for ti in chef:
        nti = i * ti
        if (nti < lcm_C):
            fx.append(nti)
fx.sort()
print(lcm_C)
print(fx)
len_fx = len(fx)
for ci in customer:
    k = (ci-1) // len_fx
    x = (ci-1) % len_fx
    print(f'{ci}: k={k} x={x} ans={k*lcm_C+fx[x]}')

Solution explained by Gemini

The post on Vorasilp’s blog tackles a restaurant/queuing optimization puzzle (commonly found in computer science interviews or competitions). It determines the exact timestamp when the $c$-th customer gets served, given a list of chefs with different processing times.

Here is a breakdown of how the Python solution works step-by-step:

1. Problem Setup

import math

chef = [2, 2, 5]
customer = [4, 5, 6, 30, 123456789012]

• chef: Represents the time it takes for each chef to complete a task (e.g., Chef 1 takes 2 minutes, Chef 2 takes 2 minutes, Chef 3 takes 5 minutes).
• customer: A list of customer queue numbers we want to find the serving times for (including a very large number, showing the solution handles big inputs efficiently).

2. Finding the Least Common Multiple (lcm)

lcm_C = math.lcm(*chef)

• The code computes the Lowest Common Multiple (lcm) of all the chefs’ times.
• For [2, 2, 5], the lcm is 10.
• Why? The schedule of when chefs finish tasks repeats cyclically every lcm minutes. Knowing this period allows us to handle massive customer numbers without simulating every single minute.

3. Generating and Sorting the Unique Service Times in One Cycle

fx = []
for i in range(lcm_C // min(chef)):
    for ti in chef:
        nti = i * ti
        if (nti < lcm_C):
            fx.append(nti)

fx.sort()

• This block generates all the unique timestamps within a single period (from time 0 up to strictly less than lcm_C).
• It loops through multiples of each chef’s time, adds them to a list fx, filters out any timestamps that equal or exceed lcm_C, and then sorts them in ascending order.
• For [2, 2, 5], this generates the exact sequence of service events within the 10-minute cycle.

4. Answering for Each Customer Using Modular Arithmetic

len_fx = len(fx)
for ci in customer:
    k = (ci - 1) // len_fx
    x = (ci - 1) % len_fx
    print(f'{ci}: k={k} x={x} ans={k * lcm_C + fx[x]}')

Instead of simulating minute-by-minute (which would timeout for a customer number like 123456789012), the code uses math:

1. len_fx: Tells us how many customers are served in one full cycle (lcm_C).
2. k: Determines how many full cycles have passed before the $c$-th customer is served.
3. x: Determines the index within the current cycle where the customer falls.
4. ans: Calculates the final time using the formula: $$\text{Answer} = (k \times \text{lcm_C}) + \text{fx}[x]$$ (It adds the time elapsed from completed cycles plus the offset into the current repeating cycle).