PROBLEM LINKSDIFFICULTYEASY PREREQUISITESBinary Search, Dynamic Programming, Graph Theory PROBLEMYou are given N bus stations and M buses that run between these bus stations. Each bus is described as ( start station, end station, start time, end time ) Now, you wish to travel from station 1 to station N. While doing so, you may have to wait before boarding a bus, because you reached the bus station from which you wish to catch the next bus, earlier than the time the bus arrives at. You wish the find a strategy for taking buses such that the longest wait time spent between unboarding a bus and boarding the next bus, is as small as possible. Also, you must reach N within time T. So do not consider schedules that make you reach N after time T. QUICK EXPLANATIONWe note that the answer needed, the maximum wait time in the optimal schedule (that minimizes the maximum wait time) satisfies the following property If there is a schedule in which the wait time is never more than x, then there is a schedule in which the wait time is never more than x + y, for any positive y This hints us at the possibility of binary searching over the answer. Thus, if we fix how long we are going to wait  say W  we can test whether there is a way to reach N before time T, or not  while never waiting for more than W units of time. EXPLANATIONHow do you determine if it is possible to reach N, within time T, while never waiting for more than W units of time? Consider a graph G, whose vertices are defined by the pair (u,x)
A vertex in this graph represents whether a bus station u could be reached at time x, or not, by finding its reachability from (1,0). The edges in this graph are determined by the buses and our threshold for wait. The number of vertices in the graph are potentially 10^{14}. This is of course an impossible number to consider. But, there are some insights that help
Thus, the only (u,x) pairs we need to store are (1,0)  the initial position  and those defined by some or the other bus. Thus, O(W) vertices only. Our algorithm now looks like a breadth first search. If we sort the buses by start times, we can parse through the buses exactly once and be assured that any possible strategy has been considered (since any strategy will be a ordered subset of this ordered set of buses). Let us talk about the implementation of the above ideas. We can maintain a set of times at which bus station u can be reached by using a bus, for each u. Let this be denoted by S(u). S(1) = {0} S(k) = ∅, for all k ≠ 1 For some bus ( startstation, endstation, starttime, endtime )
This way we can insert endtime in S(endstation) if such a t is found. This of course denotes the reachability of (endstation, endtime). The result (yes / no) will depend upon whether the smallest value in S(N) is smaller than T, or not. S(k) should be a data structure that supports efficient insertion and search. Using a self balanced tree (such as set in C++) is enough. Alternately, you can use the following trick Sort the buses by endtime instead of starttime We note that any strategy of bus selections will still be an ordered subset of this ordered set of buses. The additional benefit we get is that S(k) can be simple arrays. Any new insert in S(k) is a simple append, because all new endtimes are larger than the previous endtimes. We can use standard binary search in the search step above. The complexity of the algorithm still remains the same, but this solution will most probably have smaller constants. The expected complexity of the solution is O(M log M log T). SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 25 Mar '13, 00:15

Is there any solution possible without use of binary search on answer? I am getting wrong answer in this solution . Create a graph with buses as vertices and there would be edge between vertices if one bus ends at and other bus starts at same vertex . then I used dijksta on this graph but there won't be need to consider all edges . http://www.codechef.com/viewplaintext/1964391 did anyone had similar solution and passed ? Update : it seems 3 out of 4 fastest solutions are not using binary search and have similar approach . answered 25 Mar '13, 01:11
I am also a little bit confused about the explaination that how answar of Input given example come to 2 in output.I don't understand this can anyone has same issue if no then please answar y question or suggest some way to understand output part.. Warms regards
(25 Mar '13, 12:21)

Nice problem, but I misundestood the statement and I thought we have to optimize sum of waiting times first and from all such optimal ways to choose the one, where wait time for one bus is maximal :/ answered 25 Mar '13, 00:50

My implementation is same as what smithinsu described. WA for me too. Also are there test cases which considered where one can move between same stops to utilize time instead of waiting and then go to destination. Example
Answer is 0 answered 25 Mar '13, 02:05

is simple dijstra algo logically correct to apply for this problem answered 25 Mar '13, 08:40

I am new to Code Chef.How to take input for the program?(Via File or Through Command Line) I m able to get the the correct output for the Test Case of in the problem and the one given up there. Any help ? answered 15 Apr '13, 17:39

I think , If we consider a graph in which each bus station is considered a vertex and each bus can be considered as edge between two vertices than a simple dfs to the nth bus station could give as the answer . time complexity is also less O(N+M). Correct me if i'm wrong . answered 31 May '14, 11:55

The limited input example is beyond nonsensical. If you cannot give the inputs on which our code is run upfront, atleast we should be provided that particular input on which our code failed to give the correct result. Not knowing just where your code is failing is beyond frustrating. Can we get some help on this PLEASE? answered 21 Feb '15, 13:47
