Styjun

You have n stores in a line, each with an associated amount of money $c_i$. At time 1, you start at store 1. At each subsequent time, you can choose to visit store i-1, stay at store i, or visit store i+1. At each time step, you can collect $c_i$ money assuming you’re at store i, regardless of how many times you already visited that store.

Given a list of times $t_j$, find the maximum amount of money that can be collected given you can collect money for $t_j$ time steps.

I’m having trouble coming up with a way to preprocess the data. My idea is that for each booth, I want to find a time interval for which it is optimal to rush straight to that booth and stay there, collecting money at each time step. I’m not sure of a correct way to do this efficiently in either O(n) time or O(nlogn) time.

Edit: What I’m currently doing is for each booth, I have an expression as a function of time that represents the maximum amount of money I can collect if I go straight to the booth and stay there. Then for each time, I take the max of all these functions. This takes linear time to process each time query. I’d like to have a logarithmic procedure for doing so.

Your revenue function that returns the amount of money by going straight to shop i and staying there for a given total time t is

r_i(t) = sum(j from 1 to i - 1: c_j) + c_i * (t - i + 1)

The sums can be calculated incrementally for each i and you get a neat linear function:

r_i(t) = a_i + b_i * t

with a_i = sum as above + (1 - i) * c_i and b_i = c_i.

Now, for each time t, you want to find the maximum of all the r_i(t). For this, we can use an ordering of the functions. Specifically, we can order them such that a function f1 appears earlier than f2 in an ordered sequence if function f1 is greater than f2 before their intersection point. Then, if we have the available functions for a given point t (which are all r_i that are reachable in t), we just need to step through the ordered sequence. The first element will be the best function for the starting time. Then, we can check the intersection with the next function. If t is after that intersection, we continue to this function as this will be the new maximum for the current interval. And so on. This can be done incrementally for each query if you sort the queries by time. While doing this process, you also need to add new functions that become available. Using an appropriate data structure (e.g. a binary search tree), you can do the insertion in O(log n).

So, how can we compare two functions f1(t) = a1 + t * b1 and f2(t) = a2 + t * b2? The intersection point is ti = (a2 - a1) / (b1 - b2). And f1 is greater than f2 before that point if b1 < b2.

Here is the overall algorithm:

input: n stores, q queries Q
sort queries by time - O(q log q)
create empty BST
currentBestFunction = empty //pointer to element in BST
nextQuery = Q.first
sumCi = 0 //temporary variable for incremental sum
for t = 1 to maxQ
 if t <= n
 // we can reach a new store
 a = sumCi + (1 - t) * c_t
 b = c_t
 sumCi += c_t
 insert function (a, b) into BST - O(log n)
 if currentBestFunction = empty
 currentBestFunction = the inserted function
 while currentBestFunction is not the last function in BST
 successor = find successor function to currentBestFunction in BST
 calculate intersection ti = (successor.a - currentBestFunction.a) / (currentBestFunction.b - successor.b)
 if ti > t
 break //we are in the interval for the current best function
 else
 currentBestFunction = successor
 loop
 if nextQuery == t
 answer query by evaluating currentBestFunction at t
 advance nextQuery
 if no more queries then stop