pabloskimg's blog

Need help with this problem: Freight Train (is it DP? how?)
By pabloskimg, history, 8 years ago, In English

Hello everybody. I'm struggling to figure out the solution for a problem but I still don't quite get it. It's the Problem A, Freight Train, of a latin american problem set, which you can find here: https://dl.dropboxusercontent.com/u/28504121/ProblemsetRPC08.pdf

I recommend you to read the problem statement directly from the link in order to have an unbiased interpretation thereof, otherwise you can read the following summary:

Basically you are given a sequence of N wagons, where W of those wagons have freight in them, and the rest is just empty wagons. You are given the actual indexes of the W wagons with freight (all wagons are arranged from 1 to N). You are also given a number L of locomotives. You can assign wagons to locomotives, but you can only assign contiguous sequences of wagons to locomotives. So for example one locomotive can pick the first 3 wagons, another locomotive can pick the next 4, etc. But you cannot have a locomotive picking the first and the third wagon an leave the second wagon unpicked in between, for instance. Ok, so there are two targets to send the wagons to, target A and target B. But, the thing is, you are required to send all the W wagons with freight to A, but the empty wagons can be sent to either A or B (but there cannot be wagons leftover, all the wagons must be sent to somewhere). So the challenge is to find an assignment of wagons to locomotives such that minimizes the longest train (locomotive + wagons) forwarded to A (trains sent to B don't matter, you can send huge trains to B and their lengths would be ignored). Also, you are not required to use all the L locomotives, you can use fewer if that is enough.

And let me not forget it: 0 <= N <= 10^9, 1 <= W, L <= 10^4, and W <= N

So even O(N) would yield time limit exceeded, which it's a clear indication that the algorithm complexity should be based on W and L instead. So my intuition is that there must be some reductions / simplifications around the empty wagons, in other words, it shouldn't be necessary to try every single position within a contiguous sequence of empty wagons to decide where the previous train ends and where the next one starts. For example, if you assign a partial substring of empty wagons to a train and then send the train to B, that would be stupid because you would be better off sending the whole string of empty wagons to B in one shot. Another insight is that you always have the suboptimal solution of splitting the wagons into L groups with sizes of at most ceil(N / L) each, so that would be an upperbound for any train forwarded to A. I have a feeling that this should be solvable using Dynamic Programming, but still I don't see a way to define some recursive formula or something that handles the empty wagons correctly.

So feel free to enjoy yourself solving this problem and any help, insight or advice that you can share would be really appreciated.

Note: if you actually want to solve the problem and submit a solution, you can try out this website: https://acm.javeriana.edu.co/maratones/2016/08/. Be aware, though, that the site is in Spanish since it's a latin american online judge, the server performance is not the best of the world, and in order to submit solutions you need to login using one of the dummy usernames provided in the page and leave the password field empty.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Just a tiny correction, if I understood it correctly; you said: "So the challenge is to find an assignment of wagons to locomotives such that minimizes the longest train (locomotive + wagons) forwarded to A (trains sent to B don't matter, you can send huge trains to B and their lengths would be ignored)". The locomotive doesn't count, only the wagons.

About the solution per se, I thought about some binary search on the number of vagons, i.e. the answer itself. How? Let's suppose we have a value X and we are able to verify whether it is possible to assign at most X wagons to any of the L locomotives heading to target A. If we have such method, then it's clear that is possible to assign at most X + 1 or X + 2 or X + 3 (and so on) wagons to the L locomotives.

Now, how to create such method to verificate whether, given the so called value X, it is possible to find a correct assignment? I thought something like this: we will create a variable called left, which will represent the first wagon to be assigned to the current locomotive, and a variable called used, which will represent how many locomotives we have used so far. Now, we start iterating over the array of wagons containing freight; whenever we find a value W[i] that makes W[i] - left + 1 > X, it means that left and W[i] cannot be carried by the same locomotive. Thus, in order to be optimal, we will find the greatest value j that is less than W[i] which obeys the condition j - left + 1 = X (it can be done with simple math). When we find such j, we need to update our left variable to j + 1 (i.e. the first wagon to be taken is the next one) and increment our variable used. Note that if there is no wagon with freight between left and the W[i] that 'breaks' the condition, then the value j is simply W[i] - 1, because doesn't matter how many empty wagons we take when we are heading to point B. Finally, after all the wagons have been assigned to some locomotive, the answer to the question "is it possible to assign the wagons to the L locomotives such that the locomotives heading to point A will have at most X wagons assigned to?" is simply given by the condition used <= L. I.e., if it is true, then the answer is yes; otherwise, it is no.

I didn't actually code this problem, so I may have committed some mistake in the above thinking. Feel free to criticize.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Hi :)

I got accepted using same idea that olenihc mentions.

First you have to note that if we fix value K = maximum number of wagons assigned to a locomotive going to A, then we can check in O(W + L) whether is possible to find an assignment of wagons satisfying this K. This is done using a greedy algorithm. We have a variable from = first wagon of next locomotive to assign and a variable Wnext = position of the first wagon with freight in range [from, N]. We start with from = 1.

  • If there isn't any wagon with freight in range [from, from + K), this is: from + K ≤ Wnext, then obviously all wagons in [from, from + K) must be sent to B, moreover, we can assign more wagons to this locomotive as long as they're empty. So greedily we assign to next locomotive all wagons in [from, Wnext) and continue with a new locomotive and from = Wnext.

  • If there is some wagon with freight in range [from, from + K), this is: Wnext < from + K then we assign Wnext to this locomotive, moreover, we can assign more wagons to it as long as the number of wagons doesn't exceed K, so we greedily assign all wagons in [from, from + K) to the next locomotive and continue with a new locomotive and from = from + K.

Doing this is optimal (We use the minimum number of locomotives such that we can satisfy this K).

  • First case is really intuitive.
  • Second case might not be so obvious. It's clear that we can take no more than K wagons because it will be invalid otherwise. So suppose that taking K wagons isn't optimal, in an optimal assignment we must then take J, with J < K. Consider the optimal assignment of [from + J, N], then you can expand the first locomotive assigned [from, from + J) to [from, from + K) and got a valid assignment that uses less or equal number of locomotives, so we get a contradiction and thus taking K wagons in this case is optimal :)

Now we note that if we can assign all wagons for some fixed K then we can assign them for K + 1, K + 2, ... and that if we can not assign all wagons for some fixed K we can not assign them for K - 1, K - 2, ... . This completes what we need for our solution. We do a binary search on the minimum K that let us assign all the wagons.

Time complexity: O((W + L) * log(N))

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Excellent explanation, I don't know how I didn't think of binary search at the moment, looking backwards it makes a lot of sense. Now I got accepted too. Thank you very much.

    → Reply