Editorial for Baltic OI '05 P5 - Bus Trip
Submitting an official solution before solving the problem yourself is a bannable offence.
For each bus line, save the earliest departure time (start time), the latest arrival time (finish time), and the maximum waiting time (the maximum time we have to wait in bus stops during the time interval from start to finish time, if we take the current bus line).
For each town, we maintain a dynamically sized array (such as a C++ vector) of states. The array contains a sorted list of times when we can arrive at the town paired with total waiting time till that point. If we need to be in a certain town at time
Instead of using dynamically sized arrays, we may calculate the sizes of the arrays and allocate memory for them at the beginning of the program. State array for town
We sort the bus lines in nondecreasing order by finish time. If some bus finishes at a certain time, the next bus we take cannot start earlier than that time, so we may consider the bus lines in the sorted order. For each bus line, find using the state array of the source town the waiting time till the start time of the bus line and add the finish time to the state array of the destination town. If the finish time is later than
After we have considered all bus lines, we check if the state array for town
Time complexity:
Memory complexity:
Comments