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.↵
↵
↵
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.↵
↵
