Statistics

Problem Statement for "BusSeating"

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)
(be sure your method is public)

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

  1. "----------"

    "----------"

    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.

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

  3. "----------"

    "-XXXX---XX"

    Returns: 4.0

  4. "-X-X-X-X-X"

    "X-X-X-X-X-"

    Returns: 6.47213595499958

  5. "XXXXXXXXXX"

    "-XX-XX-X--"

    Returns: 6.0

  6. "XXX-X-XX-X"

    "XXX-X-XX-X"

    Returns: 6.82842712474619

  7. "X--X------"

    "X-XXX---XX"

    Returns: 4.0

  8. "XXXXXXXXX-"

    "--XXXXXXXX"

    Returns: 18.465755708528206

  9. "-X---X---X"

    "X--XXX---X"

    Returns: 4.0

  10. "XX--------"

    "XX-XX-XXXX"

    Returns: 4.0

  11. "X-XX-X--X-"

    "X-XX--XX--"

    Returns: 5.23606797749979

  12. "XXXXX---XX"

    "X-X-XXX-X-"

    Returns: 4.0

  13. "-X---X----"

    "-XXXX-XX--"

    Returns: 4.0

  14. "-XXX--XX--"

    "-XX-X-XX-X"

    Returns: 5.23606797749979

  15. "X-X-X-X-XX"

    "-XXX-X-X--"

    Returns: 6.0

  16. "--XXX-X-XX"

    "--XXX-X---"

    Returns: 4.0

  17. "XXX--XX-X-"

    "XX---XX---"

    Returns: 4.0

  18. "X-XXX-X---"

    "-XXX-X-X-X"

    Returns: 4.0

  19. "XX--XXX-XX"

    "X-X-X--X--"

    Returns: 5.23606797749979

  20. "X-X-XXX-XX"

    "X-----X---"

    Returns: 4.0

  21. "XX-XX-XXX-"

    "X--X---X-X"

    Returns: 4.0

  22. "XX-XXXX-XX"

    "X-XXXXXXX-"

    Returns: 13.56062329783655

  23. "---XX-XXXX"

    "X--X--XX--"

    Returns: 4.0

  24. "XX-X-X-XX-"

    "X--XXXX-X-"

    Returns: 5.23606797749979

  25. "X-XXXXX---"

    "--X-XXXX-X"

    Returns: 4.0

  26. "XXX---XX--"

    "XX---XX---"

    Returns: 4.0

  27. "---XXX----"

    "XXX-XX-X--"

    Returns: 4.0

  28. "XXXXXXXX-X"

    "X--XXX-XX-"

    Returns: 8.06449510224598

  29. "XX--XXX--X"

    "-------X--"

    Returns: 4.0

  30. "XX-XXX-X-X"

    "-X--X-X---"

    Returns: 4.0

  31. "X--X----X-"

    "--X-X-XX-X"

    Returns: 4.0

  32. "X--X-XXXXX"

    "X--X--X-XX"

    Returns: 5.23606797749979

  33. "-XXX-X-X--"

    "XX-XX-X-X-"

    Returns: 5.23606797749979

  34. "-XX--X--XX"

    "XXX--XX---"

    Returns: 4.0

  35. "-XX-X---X-"

    "-XXXXX-XXX"

    Returns: 4.0

  36. "X---XXX-XX"

    "--X----X-X"

    Returns: 4.0

  37. "XXX--XXXXX"

    "X-XXX-XXXX"

    Returns: 6.06449510224598

  38. "-XXXXXX--X"

    "XX--X-XX--"

    Returns: 5.23606797749979

  39. "---XX---XX"

    "X---X--X--"

    Returns: 4.0

  40. "-X--XX-X-X"

    "X-X-----X-"

    Returns: 4.0

  41. "X--XXXXX-X"

    "XXXXX-X-XX"

    Returns: 7.841619252963779

  42. "XX--X-XX--"

    "XX-X-XX--X"

    Returns: 5.23606797749979

  43. "X-X-X-X--X"

    "-XX-X-XX--"

    Returns: 5.23606797749979

  44. "-XXXXX--XX"

    "XXX-X---X-"

    Returns: 4.0

  45. "XXX-X-XXXX"

    "XXXX-XXXXX"

    Returns: 6.47213595499958

  46. "-X-XXXXX--"

    "XXX-X-X-XX"

    Returns: 6.06449510224598

  47. "X-X--XX--X"

    "X--XXX-X--"

    Returns: 5.23606797749979

  48. "XXXXXXXXXX"

    "XXX-X-X-X-"

    Returns: 8.0

  49. "XX-X--X-X-"

    "X-X-X-XX-X"

    Returns: 5.23606797749979

  50. "-X-XXXX-XX"

    "-X-X--XXX-"

    Returns: 6.0

  51. "X--X--X-XX"

    "XX-X-X-X-X"

    Returns: 5.23606797749979

  52. "X---XX---X"

    "-XXX--X---"

    Returns: 4.0

  53. "XXX--XX-XX"

    "XX--XXXX-X"

    Returns: 5.23606797749979

  54. "X-X-XX--X-"

    "--XX-XX-X-"

    Returns: 5.23606797749979

  55. "XXXXX-X--X"

    "XXXXXX--XX"

    Returns: 5.23606797749979

  56. "----X-X--X"

    "X---XXX-XX"

    Returns: 4.0

  57. "-XXXXXXXX-"

    "-XXXXXXXX-"

    Returns: 20.219544457292887

  58. "--X-X-XX--"

    "X--XX--X--"

    Returns: 5.23606797749979

  59. "-X--X-XXX-"

    "X-X--XXXX-"

    Returns: 5.23606797749979

  60. "-X-XXXX-XX"

    "XXXXXXXXX-"

    Returns: 14.0

  61. "XX-X--X--X"

    "-X-X-X-XXX"

    Returns: 5.23606797749979

  62. "-X--XX--X-"

    "-X--X-X--X"

    Returns: 5.23606797749979

  63. "-X--X-X-X-"

    "XXXX-X-X-X"

    Returns: 6.0

  64. "--XXX-X--X"

    "X-X-XX--X-"

    Returns: 5.23606797749979

  65. "-XXX-XXXXX"

    "--XXX-X---"

    Returns: 4.0

  66. "-XXX-X--X-"

    "-XX-XXX--X"

    Returns: 5.23606797749979

  67. "-X-XX--X--"

    "X-XXXXXXXX"

    Returns: 6.0

  68. "X-X-XX-X--"

    "XX-XXXXXXX"

    Returns: 6.0

  69. "XX-X-X-X--"

    "XXX-XXXXXX"

    Returns: 6.0

  70. "XXX-XX-X--"

    "XX-X-XXXXX"

    Returns: 6.0

  71. "X-X-X-X-X-"

    "-X-X-X-X-X"

    Returns: 6.47213595499958

  72. "XXX-X-XX-X"

    "XXX-X-XX-X"

    Returns: 6.82842712474619

  73. "XXXXXXXXXX"

    "-XX-XX-X--"

    Returns: 6.0

  74. "----------"

    "----------"

    Returns: 4.0

  75. "XXXXXXXXX-"

    "--XXXXXXXX"

    Returns: 18.465755708528206

  76. "---XXXXXXX"

    "XXXXXXXXXX"

    Returns: 4.0

  77. "------XXXX"

    "----------"

    Returns: 4.0

  78. "-XXXXXXXX-"

    "-XXXXXXXXX"

    Returns: 20.219544457292887

  79. "XXXXXXXXXX"

    "---XXX---X"

    Returns: 4.0

  80. "XXXXXXXXXX"

    "---XXXXXXX"

    Returns: 4.0

  81. "-XXXXXXXX-"

    "XXXXX-XXXX"

    Returns: 18.857300762134084

  82. "XXXXX-XXXX"

    "-XXXXXXXX-"

    Returns: 18.857300762134084

  83. "XXXXXXXXX-"

    "--XXXXXX--"

    Returns: 5.23606797749979

  84. "XXXXXXXXX-"

    "XXXXXXXX--"

    Returns: 5.23606797749979

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: