TopCoder problem "LongStraightRoad" used in SRM 426 (Division I Level Three)

Problem Statement

You are driving on a long, straight road, on your way to a place whose name is given in destination. After a while, you lose track of how far you've driven and realize that you may even have driven past your destination without noticing. "Don't worry!" says your friend, who is in the car with you, "I have an excellent memory and can remember not only what was written on every road sign that we have passed, but also what order they were in. Let's continue until we see the next road sign and maybe we'll be able to work out how far we still have to go." You agree to his plan, but don't quite trust his memory as much as he clearly does. You decide that you'll believe what he says as long as it is entirely consistent, otherwise you'll try to find somewhere that you can buy a map.

The information written on each sign is a semi-colon separated list, where each element of the list is the name of a place and the distance to that place from the sign separated by a space. For example, if sign i contained "A 10;B 15" (quotes for clarity) and the sign were located a distance of S[i] units down the road, then the place called "A" would be located P["A"] = S[i] + 10 units down the road and the place called "B" would be located P["B"] = S[i] + 15 units down the road. The distances will never be negative, so only places that are at least as far along the road as the sign can be listed. Note that the values in S[] and P[] need not be integers and that places will have distinct names. You are given the information written on sign i as your friend remembers it in signs[i]. Your friend claims to remember the order of the signs too, so if you wrote down the values of S[i] for each sign, they would be in strictly increasing order (no two signs were colocated).

You are currently at the same position as the sign given in the last element of signs. If the information given in signs is consistent, you can determine the remaining distance to your destination and this distance is non-negative, then return this distance. Otherwise, if there is no way that the data given in signs could represent a set of signs and places as described above, or you cannot determine the distance to your destination from the information in the signs, or you have already driven past your destination, return -1 instead.

Definition

Class:	LongStraightRoad
Method:	distanceToDestination
Parameters:	String[], String
Returns:	int
Method signature:	int distanceToDestination(String[] signs, String destination)
(be sure your method is public)

Notes

While no two signs were at the same position on the road, places may be legitimately colocated with other places and with the signs.

Constraints

A place is a string containing betweeen 1 and 50 uppercase letters ('A' - 'Z'), inclusive.

A distance is an integer between 0 and 10000, inclusive, formatted without leading zeros.

signs will contain between 1 and 50 elements, inclusive.

Each element of signs will contain between 1 and 50 characters, inclusive.

Each element of signs will be a semicolon-separated list, each item of which will be a place and a distance, separated by a space.

No element of signs will contain the same place more than once.

signs will contain no more than 100 distinct places.

destination will be a place.

Examples

{"COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13"
,"MARLBOROUGH 2"}

"GLASTONBURY"

Returns: 14

The first sign tells you that GLASTONBURY is 12 units further than MARLBOROUGH. Since you're now 2 units from MARLBOROUGH, you must be 14 units from GLASTONBURY.

{"COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13"
,"GLASTONBURY 13;MARLBOROUGH 2"}

"GLASTONBURY"

Returns: -1

The distance between GLASTONBURY and MARLBOROUGH has changed between the first and second signs, so they're inconsistent. Even though you are standing next to a sign that tells us how far you are from your destination, return -1.

{"A 25;B 15"
,"A 2"}

"B"

Returns: -1

You've driven past your destination by 8 units.

{"YVO 60;J 62"
,"K 45"
,"K 40;MV 17"
,"K 37;YVO 44;HY 48;CC 69;D 77;YXF 80"
,"YVO 30;B 37;RB 59"}

"MV"

Returns: 0

You're standing right at your destination.

{"A 200;B 150"
,"C 45;D 100;E 150"
,"C 25;E 130"
,"F 80;G 65"
,"G 35;H 160"
,"A 160"
,"H 130"}

"F"

Returns: -1

There is no way the signs could be in this order.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13517&pm=9894

Writer:

StevieT

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Geometry, Graph Theory