TopCoder problem "TheAirTripDivOne" used in SRM 479 (Division I Level Two)



Problem Statement

    In some country there are n cities numbered from 1 to n. There are also several types of flights between them. Each flight type is characterized with 5 integers A, B, F, T and P. All flights of this type depart from city A and arrive at city B (without changing planes in any intermediate cities). Each flight type is one-directional, so it is impossible to fly from city B to city A using the same flight type. All flights of the same type depart with some periodicity. More precisely, the first flight of this type departs from A at time F, the next flight departs at time F + P, then at F + 2P, and so on (there are infinitely many flights of the same type). Each flight of the same type has the same flight time T. I.e., if a plane departs from A at time T0, then it arrives to B at time T0 + T.



The description of all flight types is given in String[] flights. Concatenate the elements of this String[] in the same order as they are given without any delimiters between its elements to get a single String. This String will contain a single space separated list of flight type descriptions. Each such description will be of the form "A,B,F,T,P" (quotes for clarity), where the meaning of integers A, B, F, T and P is exactly the same as defined in the previous paragraph.



John would like to travel from city 1 to city n where his friend Brus is waiting for him. Unfortunately, there are no direct flights from 1 to n, so he will have to use several flights to reach city n. He can't use any other transport besides planes, so the departure city of each next flight he takes must be the same as the arrival city of the previous flight he has taken. Moreover, in order for him to be able to change planes, the departure time of each next flight must be strictly greater than the arrival time of the previous flight. If he arrives at some city at time T1 and then departs at time T2, the waiting time in this city is equal to T2 - T1. John defines the safety of his route from 1 to n as the minimum of waiting times over all cities where he changes flights.



John wants to arrive at city n no later than at time moment time. If there are several routes that achieve this goal, he wants to choose the route among them with the maximum possible safety. Return this maximum possible safety. If there are no such routes, return -1.
 

Definition

    
Class:TheAirTripDivOne
Method:find
Parameters:int, String[], int
Returns:int
Method signature:int find(int n, String[] flights, int time)
(be sure your method is public)
    
 

Constraints

-n will be between 3 and 477, inclusive.
-flights will contain between 1 and 47 elements, inclusive.
-Each element of flights will contain between 1 and 47 characters, inclusive.
-The concatenation of all elements of flights will be a single space separated list of flight type descriptions without leading or trailing spaces.
-Each flight type description will be of form "A,B,F,T,P" (quotes for clarity), where A, B, F, T and P are integers formatted with no extra leading zeros.
-In each flight type, A and B will be distinct integers between 1 and n, inclusive.
-In each flight type, F, T and P will be between 1 and 1,000,000,000, inclusive.
-There will be no flight from city 1 to city n.
-time will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
3
{"1,2,1,4,7 ", "2,3,9,1,10"}
20
Returns: 14
The optimal way is to take the first flight at time 1 and the second one at time 19.
1)
    
3
{"1,2,1,1,1 2,3,2,1,98"}
100
Returns: -1
Since John needs a strictly positive time to change a flight, it is possible to get to city 3 only at time 101.
2)
    
477
{"47,74,1,1,1"}
20
Returns: -1
It is impossible to reach the destination at all.
3)
    
7
{"1,3,15,17,11 1,3,14,16,14 5,7,12,18,18 1,6,13,1", 
 "6,12 1,2,18,14,13 5,6,10,10,18 3,1,10,10,10 1,3",
 ",17,16,10 2,3,16,18,16 6,1,15,12,10 2,1,15,18,1",
 "0 4,7,10,16,15 6,3,10,14,10 1,6,19,19,15 1,4,12",
 ",10,14 4,7,10,18,14 2,3,16,12,12 1,3,14,10,19 3",
 ",7,17,10,12 2,1,14,12,16 4,3,19,11,12 1,6,10,18",
 ",12 2,3,16,12,10 6,2,10,18,12 5,1,14,18,12 5,1,",
 "18,10,10 3,2,19,15,10 7,4,16,19,14 6,3,16,12,10",
 " 5,7,14,13,13 1,3,12,10,16 5,7,16,18,15 6,2,18,",
 "12,14 3,2,10,18,16 4,2,18,18,14 1,5,10,18,16 2,",
 "3,10,19,16 1,4,11,18,15 2,1,15,15,14 7,2,10,12,",
 "10"}
74
Returns: 33
Note that there can be multiple flight types with the same departure city and the same arrival city.
4)
    
7
{"1,4,10,8,2 4,6,14,8,2 6,2,8,1",
 "0,1 2,7,19,5,1 ",
 "1,5,15,17,11 5,3,10,1",
 "0,18 3,7,12,18,18"}
147
Returns: 35
Take the flight from city 1 to city 4 at time 10 to arrive at city 4 at time 18. Then take the flight from city 4 to city 6 at time 54 to arrive at city 6 at time 62. Next take the flight from city 6 to city 2 at time 97 to arrive at city 2 at time 107. Finally, take the flight from city 2 to city 7 at time 142 to arrive at city 7 exactly at time 147. The safety of this route is min{54 - 18, 107 - 62, 142 - 107} = 35.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11030

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14158&pm=11030

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , ivan_metelsky , gojira_tc

Problem categories:

Graph Theory, Simple Math