PROBLEM STATEMENT
Three friends enter a bus. There are two rows of seats with 10 seats in each row along the left
and right side of the bus. For this problem, consider the seats to be points. Each seat in the
same row is separated from the one in front of it and the one behind it by exactly 1 meter, and
from the one directly opposite it (i.e., in the other row) by exactly 2 meters. Some of the seats
are occupied by passengers. The friends want to know which seats they should occupy so as to
minimize the sum of the Euclidean distances between each pair of friends. Recall that the
Euclidean distance is simply the length of the line segment joining two points.
Create a class BusSeating that contains a method getArrangement. The method takes two strings as
arguments, leftRow and rightRow. Each string is composed of the characters '-' and 'X' only, with
'-' denoting an empty seat, and 'X' denoting an occupied seat. The seats are given in order from
the front to the back of the bus in each row. The method should return a double corresponding to
the sum of the Euclidean distances between friends in the optimal arrangment.
DEFINITION
Class:BusSeating
Method:getArrangement
Parameters:string, string
Returns:double
Method signature:double getArrangement(string leftRow, string rightRow)
NOTES
-Your return value must have an absolute or relative error less than 1e-9.
CONSTRAINTS
-leftRow and rightRow will each contain exactly 10 characters.
-leftRow and rightRow will contain only the characters '-' and uppercase 'X'.
-There will be at least 3 empty seats among the 2 rows of seats.
EXAMPLES
0)
"----------"
"----------"
Returns: 4.0
The minimum sum of distances in this situation is achieved when the three friends sit behind each
other in the same row of seats, giving a minimum distance of 4.0.
1)
"XXX-X-XX-X"
"-XXXX---XX"
Returns: 4.0
Once again, the friends can minimize the sum of distances by sitting behind each other in a row.
This time, however, there is only one way to seat themselves in this manner.
2)
"XXXXXXXXXX"
"-XX-XX-X--"
Returns: 6.0
3)
"XXX-X-XX-X"
"XXX-X-XX-X"
Returns: 6.82842712474619
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.