TABUS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Binary Search, Dynamic Programming, Graph Theory

PROBLEM

You 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 un-boarding 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 EXPLANATION

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

EXPLANATION

How 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)

  • u is the label of a bus station
  • x is the time stamp between 0 and T

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 1014. This is of course an impossible number to consider. But, there are some insights that help

  • You can only reach a new station by using some bus
  • If you can reach (u,x), after using some bus
    • you can reach (u,x+w) also
    • where 1 ≤ w ≤ W

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 ( start-station, end-station, start-time, end-time )

  • Search for a t in S(start-station) such that
    • t ≤ start-time
    • start-time - t ≤ W

This way we can insert end-time in S(end-station) if such a t is found. This of course denotes the reachability of (end-station, end-time).

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 end-time instead of start-time

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 end-times are larger than the previous end-times. 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 SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

6 Likes

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 :-/

1 Like

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 .

3 Likes

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

5 10 5
1 2 0 1
2 1 1 2
1 2 2 3
2 1 3 4
1 5 4 9

Answer is 0

is simple dijstra algo logically correct to apply for this problem

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 ?

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 .

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?

Yes. Such cases are possible.

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

I think it could be.that dijstra algorith will produce some result

How would you take the maximum time T in account in that case?