PROBLEM STATEMENT
The mayor of your city has asked you to calculate the cost of his new project.
Currently all of the roads in your city are two-way (they allow traffic in both
directions). He wants to change all of the roads to one-way (so that they only
allow traffic in one direction). The problem is, he can't disconnect any parts
of the town that were previously connected. In other words, given any two
locations in the town A and B, if A and B were connected before the project,
they must still be connected after the project. Two locations A and B are
connected if you can get from A to B taking any number of roads necessary, and
you can get from B to A taking any number of roads necessary. He is letting
you decide which way each of the new one-way roads will be directed. For
example:
One Two Three Four
A------B A-------B A-------B A---B E--G
| | | \ / | | | /
| | | \ / D---C |/
| | | \ / F
C D-------C C------D
In picture One above all of the locations are connected before the project but
there is no way you can change all the roads to one-way and maintain
connectivity. In picture Two all of the locations are connected before the
project, and will remain connected if we make all of the one way roads point
around the square to form a cycle (for example, A->B->C->D->A). In picture
Three all of the locations are connected before the project but will not remain
connected after the project regardless of which way we make the roads one-way.
In picture Four A,B,C, and D are connected and E,F, and G are connected. If
both connected sets are made to form cycles then all will still be connected
(for example, A->B->C->D->A and E->G->F->E). See examples for further
clarification.
If the given project cannot be done because connectivity cannot be maintained
your method will return -1. If the project is doable your method will return
the total cost of the entire project which can be calculated as follows:
TotalCost = costPerRoad * Total#ofRoads. This is a straightforward calculation
since all of the two-way roads are being changed to one-way roads if the
project goes through. The project goes through if and only if connectivity can
be maintained once all two-way roads are converted to one-way roads.
The map you are given will be specified in two arrays (locationA and locationB):
- Two-way road K is between locationA[K] and locationB[K]
- All locations are connected to at least one other location
- Every location is uniquely defined by its name
So picture One from before could be given as:
locationA = {"A","A"}
locationB = {"B","C"}
Signifying a two-way road between A and B, and a two-way road between A and C.
Since no roads can be repeated in the input, if you are given a two-way road
between A and B, you will not also be given another two-way road between A and
B, or a two-way road between B and A. This means that there cannot be more
than one two-way road DIRECTLY connecting two locations. There may be multiple
indirect paths connecting two locations (passing through intermediate locations).
Create a class OneWayRoad that contains the method totalCost, which takes a
String[] locationA, a String[] locationB, and an int costPerRoad, and returns
an int representing the totalCost of the project or -1 if the project is
impossible.
DEFINITION
Class: OneWayRoad
Method: totalCost
Parameters: String[], String[], int
Returns: int
Method signature (be sure your method is public): int totalCost(String[]
locationA, String[] locationB, int costPerRoad);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- costPerRoad will be between 1 and 1000 inclusive
- locationA will contain between 1 and 50 elements inclusive
- locationA and locationB will contain exactly the same number of elements
- There will be no repeated roads (If there is a road between A and B then
there will be no other roads between A and B or B and A in the inputs)
- A location will never connect to itself (locationA[K] != locationB[K])
- Each element in locationA will contain only capital letters ('A'-'Z')
- Each element in locationB will contain only capital letters ('A'-'Z')
- Each element in locationA will have length between 1 and 50 inclusive
- Each element in locationB will have length between 1 and 50 inclusive
EXAMPLES
'-','|' are used to describe roads
'<','>','^','v' are used to describe the orientation of one-way roads
1) locationA = {"A","A"}
locationB = {"B","C"}
costPerRoad = 1000
This road map would look like:
C------A-------B
One possible one-way configuration:
C----->A<------B
Using two-way roads, all of the locations are connected. In the possible
one-way configuration drawn directly above, C and B are both connected to A,
but A is not connected to either one. C and B are not connected to each other
either. No other possibilities do not maintain connectivity either.
Method returns -1.
2) locationA = {"A","B","C","D"}
locationB = {"B","C","D","A"}
costPerRoad = 555
This road map could be drawn as:
--------B
| |
| |
A C
| |
| |
--------D
One possible one-way connected configuration:
------->B
| |
| v
A C
^ |
| v
--------D
Using two-way roads, all of the locations are connected. The picture directly
above shows a possible configuration that allows all of the locations to remain
connected as one-way roads. Each road costs 555 so 4*555 = 2220.
Method returns 2220.
3) locationA = {"A","B","C","D","A"}
locationB = {"B","C","D","A","C"}
costPerRoad = 555
This road map could be drawn as:
--------B
| |
| |
A-------C
| |
| |
--------D
One possible one-way connected configuration:
------->B
| |
| v
A------>C
^ |
| v
--------D
This is just like example 1 except an extra road has been added. Using two-way
roads, all of the locations are connected. The picture directly above shows a
possible configuration that allows all of the locations to remain connected as
one-way roads. Each road costs 555 so 5*555 = 2775.
Method returns 2775.
4) locationA = {"A","B","C","D","E","F"}
locationB = {"B","C","A","E","F","D"}
costPerRoad = 20
This road map could be drawn as:
A-----| D-----|
| | | |
| B | E
| | | |
C_____| F-----|
One possible one-way connected configuration:
A-----| D-----|
^ v ^ v
| B | E
| | | |
C<----| F<----|
Using two way roads, there were two separate sets of connected locations
(namely {A,B,C} and {D,E,F}). The picture directly above shows a possible
configuration that allows all of the locations to remain connected as one-way
roads. Each road costs 20 so 6*20 = 120.
Method returns 120.
5) locationA = {"ALICE","BRETT","CHRIS","DAVID"}
locationB = {"BRETT","CHRIS","DAVID","ALICE"}
costPerRoad = 555
This is the same as example 2 except the names are not single capital letters.
Method returns 2220.
6) locationA = {"A","B","C","C","D","E","F"}
locationB = {"B","C","A","D","E","F","D"}
costPerRoad = 1000
Method returns -1.