TopCoder problem "TimeTravellingGogo" used in SRM 492 (Division I Level Three)



Problem Statement

    Gogo lives in Rainyland and wants to attend a party. There are N houses in Rainyland, conveniently numbered 0 through N-1. Gogo lives in house 0 and the party is in house N-1. There are several bidirectional roads of various lengths that Gogo can traverse.



It rains a lot in Rainyland. In fact, with the exception of several sunny intervals, it rains all the time. The i-th sunny interval starts at the beginning of minute sunnyStart[i] and ends at the beginning of minute sunnyEnd[i]. Gogo can't get his party clothes wet, so whenever it is raining, he must be inside a house. He can only traverse roads during sunny intervals. More exactly, if he starts traversing a road at the beginning of minute A and ends at the beginning of minute B, there must exist such i that sunnyStart[i] <= A < B <= sunnyEnd[i].



The roads are given in the String[] roads. Concatenate the elements of roads to get a single space separated list of roads. Each road is formatted "a,b,travelcost" (quotes for clarity), which means that the bidirectional road connects city a and city b, and requires travelcost minutes to traverse either way.



Gogo also has a time machine, which he can use to go back in time. He can only use the time machine inside a house, and it requires machineStartTime + X minutes to go back in time by X minutes. He can go back as far as time 0, but no further. For example, suppose the time is currently 100, machineStartTime is 10, and he wants to go back to time 80 because it was sunny then. It will take him 10 + 20 = 30 minutes to get back to time 80. Note that when he uses the time machine, his position will not change. In other words, he won't go back to where he happened to be at time 80 the last time he was there.



Gogo is initially in his house at the beginning of minute 0. Return the minimum number of minutes Gogo needs to reach house N-1 without getting wet. Return -1 if it's impossible. Note that Gogo does not have to be in constant motion. For example, he can wait inside a house while waiting for a sunny interval. Also, note that time travel does not affect Gogo's total time. For example, in the scenario described above, if he used the time machine for the first time at time 100, then when he goes back to time 80, his total time will be 130 minutes, not 80 minutes.
 

Definition

    
Class:TimeTravellingGogo
Method:determineTime
Parameters:int, int[], int[], String[], int
Returns:long
Method signature:long determineTime(int N, int[] sunnyStart, int[] sunnyEnd, String[] roads, int machineStartTime)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 20, inclusive.
-sunnyStart will contain between 1 and 20 elements, inclusive.
-Each element of sunnyStart will be between 0 and 999,999,999, inclusive.
-sunnyEnd will contain the same number of elements as sunnyStart.
-sunnyEnd[i] will be between sunnyStart[i]+1 and 1,000,000,000, inclusive.
-There will be at least a minute of rain between two sunny intervals, that is, sunnyEnd[i] < sunnyStart[i+1].
-roads will contain between 1 and 50 elements, inclusive.
-Each element of roads will contain between 1 and 50 characters, inclusive.
-Each character in roads will be '0'-'9', ' ', or ','.
-roads will be formatted as described in the problem statement without leading or trailing spaces.
-All integers in the concatenation of all the elements of roads in the order they are given will have no extra leading zeroes.
-In each road, a and b as described in the problem statement will be different and will each be between 0 and N-1, inclusive.
-In each road, travelcost as described in the problem statement will be between 1 and 1,000,000,000, inclusive.
-For each two different houses, there will be at most one road connecting them.
-machineStartTime will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
3
{0,8}
{4,12}
{"0,1,3 1,2,3"}
1
Returns: 9
First, walk from house 0 to house 1, arriving at minute 3. Then, go back in time to minute 1. This time travel requires 1+2=3 minutes. Finally, walk 3 minutes from house 1 to house 2, arriving at minute 4. The total time is 3+3+3=9 minutes.
1)
    
3
{0,8}
{4,12}
{"0,1,3 1,2,4"}
18
Returns: 12
First, walk from house 0 to house 1, arriving at minute 3. Then, wait inside house 1 for 5 minutes. Finally, walk 4 minutes from house 1 to house 2, arriving at minute 12. The total time is 3+5+4=12 minutes.
2)
    
2
{1,3}
{2,4}
{"0,1,2"}
1
Returns: -1
The length of each sunny interval is 1 minute, but the road from house 0 to house 1 requires 2 minutes to traverse, so it is impossible for Gogo to arrive at the party without getting his clothes wet.
3)
    
3
{0,17}
{15,37}
{"0,1,1","5"," 1,2,12 2,0,17"}
10
Returns: 29

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14245&pm=11117

Writer:

dolphinigle

Testers:

PabloGilberto , ivan_metelsky , it4.kp

Problem categories:

Graph Theory