Jan 092009

ZJU 3075 – Ticket

You want to plan a training camp for your team in an N-days vacation (3 ≤ N ≤ 100000). The team must arrive at the camp before the first training day, and they may go home after the last training day. The training should be between P and Q days long, inclusive.

You decide to buy air tickets for all the team members. The price of air ticket in ith day is Ai. If the team arrive at the ith day and go back home at jth day, you need to pay Ai + Aj. You notice that sometimes the cost will be lower if they arrive earlier or back home later (the team may have free days). For each free day, you should pay F for their extra lunch fee.

Find the minimal total cost, including air tickets and extra lunch fee.

Let’s simplify the problem by considering only the cases where P equals to Q, which means, the training days should always be Q days long. For each feasible choice of (i, j): arrive at ith day and return at jth day, we only have to concern with the air tickets (Ai + Aj) and the number of free days (free = j – i – Q – 1). When the training will be conducted does not matter as long as they’re somewhere between ith and jth day.

Let Ai be the day when the team arrives, Ai+1..i+Q are the training days, Ai+1+Q is the earliest day in which they can go home and AN is the latest. We want to find j which minimize { Aj + free * F } and subject to i+1+Q ≤ j ≤ N. This can be done in O(1) by preprocessing table X1..N in O(N). Xk means j which meets the above criteria for k = i+1+Q. Alternatively, we can modify X to keep only the total cost to return at jth day as we don’t need the j value. This little modification may help you (at least me) in the implementation details.

To compute Xk we need to consider only Ak and Xk+1+F. This idea can be explained mathematically as follows:

Xk = min { Ak, Ak+1+F, Ak+2F, ..., AN+(N-k)F }
Xk = min { Ak, min{Ak+1+F, Ak+2F, ..., AN+(N-k)F} }
Xk = min { Ak, min{Ak+1, Ak+F, ..., AN+(N-(k+1))F} + F }
Xk = min { Ak, Xk+1+F }

A simple dynamic programming approach is sufficient to compute all X in O(N). The minimum cost if we arrive at ith day is Ai + Xi+1+Q, which costs O(1). So, to find the minimum cost for all i will need only O(N) computation.

Now let’s back to the real problem where P could be less than Q.

Notice that any feasible j should fall into one of these ranges:
– between i+1+P and 1+Q, inclusive.
– between i+1+Q and N, inclusive.

The second range has been handled by table X, but how about the first range? The answer was quite simple, yet the implementation is more complex. To handle the first range, we just need to find the lowest Aj in all i+1+P ≤ j ≤ 1+Q. Why? The reason is obviously we don’t want a “must-pay” free day while we can have a “free” training days. So, force the students to train (no free day).

To find the minimum element in a certain range, there are several data structures such as segment-tree or range-minimum-query. Although, we can also manipulate the usage of STL’s priority_queue to perform such task (note that the range we want to check slides from left to right with a static length) .

The final answer can be found by chosing j (return day) with the minimum cost between first range and second range for each chosen i (arrival day).

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>