TopCoder problem "BusSeating" used in SRM 319 (Division I Level One , Division II Level Two)

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.



Parameters:String, String
Method signature:double getArrangement(String leftRow, String rightRow)
(be sure your method is public)


-Your return value must have an absolute or relative error less than 1e-9.


-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.


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.
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.
Returns: 6.0
Returns: 6.82842712474619

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy , ged

Problem categories:

Brute Force, Geometry, Simple Math