For simplicity, let's make the following assumptions (we can relax these later and work out the edge cases):
- Each machine produces a 'fractional gift' of 1/l[i] at every time step.
- All S[i] are different, i.e., no two machines start dispensing at the same time.
Let's consider the two border cases first:
- If we have more pouches than machines, we don't have to choose between them; at every time step S[i], we add a pouch to machine i, and keep collecting all gifts until we have a total of C.
- If |B| = 1 (only one pouch), we add the pouch at the minimum S[i]. We keep stepping through time until either we reach C, or until another machine would have led to a higher total at that time, then switch the pouch due to 20-20 hindsight. Note that mathematically, the switch point is the intersection of the two lines that cross the x-axis at S[i], and have slope 1/l[i]. We will come back to that later.
Above considerations lead to the following general (naive) algorithm, in pseudocode.
def min_time_to_reach_c(S,l):
def function yield(m, t) = max(0, t-S[m])/l[m]
Active = {} # The currently best set of machines that we attach our pouches to
Inactive = {1,..,A} # The other machines
t = 0 # time step
sum = 0 # total gifts collected so far
gift_rate = 0 # gifts we receive at every time step
while sum < C:
if |Active| < B and t == S[m’] for some m’ in InActive:
# we have not used up all our pouches yet
Active += {m’}
InActive -= {m’}
gift_rate += l[m’]
else if yield(m’,t) > yield(m,t) for some m’ in InActive, m in Active: (*)
# for all successive time steps, m’ will be preferable to m
Active += {m’} - {m}
InActive -= {m’}
sum += yield(m’,t) - yield(m,t)
gift_rate += l[m’] - l[m]
sum += gift_rate
t += 1
return t
The complexity of this naive algorithm is at most O( t_min * A), if in each step (*) we determine the 'crossing' by finding the maximum (minimum) yields of the (In)Active sets by one linear pass each.
If A < t_min, we can actually do better by thinking about the geometry - it can be viewed as a sweep line algorithm. In fact, it is not necessary to visit each time point, we only need to look at the 'interesting' points where a machine starts or lines cross. In a preprocessing step, we calculate all time steps with intersections (if a line does not cross another one and is dominated, it can be dropped right away). At each such point, we can update our active set and the yield rate as above. We also calculate the distance to reach C at the current rate; if this occurs before the next S[i] or crossing, we are done.
The complexity of the sweep line algorithm is O(A^2) for the preprocessing step, plus another O(A^2) for the at most 2A update steps (or better, O(A log A) if we use a priority queue to keep track of the relative order of lines). Note that this is independent of t_min.
I think an interesting follow-up question would be: What would be the best strategy if you didn't know the S[i] and l[i] in advance?
