Statistics

Problem Statement for "OptimalGroupMovement"

Problem Statement

NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.

There is a horizontal row of N squares, each of which either contains a counter or is empty. A set of counters in this row is called a group if it meets all of the following requirements:

  • They form a contiguous part of the row.
  • The square immediately to the left of the leftmost counter in the set is empty, or the leftmost counter in the set is in the leftmost square of the row.
  • The square immediately to the right of the rightmost counter in the set is empty, or the rightmost counter in the set is in the rightmost square of the row.

In one move, we can take any group and simultaneously move all of its counters one square to the right (only if the rightmost counter in the group is not in the rightmost square of the row), or one square to the left (if the leftmost counter in the group is not in the leftmost square of the row). The cost of such a move is C2, where C is the number of counters in the group.

You will be given a String board that represents the initial row from left to right. Each character of board represents the content of a single square and is either uppercase 'X' (counter) or '.' (empty). Your goal is to have all the counters in the row form exactly one group. Return the minimum possible total cost required to achieve this.

Definition

Class:
OptimalGroupMovement
Method:
minimumCost
Parameters:
String
Returns:
int
Method signature:
int minimumCost(String board)
(be sure your method is public)

Constraints

  • board will contain between 1 and 50 characters, inclusive.
  • Each character of board will be '.' or 'X'.
  • At least one character of board will be 'X'.

Examples

  1. ".XXX.XXXX."

    Returns: 9

    Initially, there are two groups of counters: a group of 3 on the left side and a group of 4 on the right side. To form a single group, we can move the group of 3 one square to the right (at a cost of 9), or move the group of 4 one square to the left (at a cost of 16). The first option is cheaper.

  2. "X"

    Returns: 0

    Here we already have one group of 1 counter.

  3. "XXXXX...X..X.X"

    Returns: 14

    The leftmost group is large, so we don't move it. We move the other three groups to the left.

  4. ".X.X.X..X.X.X.......XX..X.X..X"

    Returns: 70

  5. ".X"

    Returns: 0

  6. "X."

    Returns: 0

  7. "XX"

    Returns: 0

  8. "X.X"

    Returns: 1

  9. "...X...X.X.XXX..XXXX....X.X.X.X.XX.XX.X...X...XX.X"

    Returns: 226

  10. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: 0

  11. "X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X."

    Returns: 156

  12. "XXXXXXXXXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXXXXX"

    Returns: 576

  13. "XXXXXXXXXXXXXXXXX................XXXXXXXXXXXXXXXXX"

    Returns: 4624

  14. "X..XXXXXXX.XXXX...XX..XX.X..XX..X.XX.....XXXXXXXX."

    Returns: 1136

  15. ".X..XXXXXXX.XXX..X.X.XX.X.X....XX..XXXXXXX..X.X.XX"

    Returns: 779

  16. "X.XXXXX...XXX...X..XX.XX......X..X..X..X....XXXXXX"

    Returns: 908

  17. "XXXXXXX..X..X..X.X.XXX.XXXX.X...X....X..XXXXXXXXXX"

    Returns: 1264

  18. "XX.XXXXXXXXXXX...X..X.X.....XXXXXX..X..XXXXXXXXX.."

    Returns: 1642

  19. "XXXXXXXXX...X.X.XX..X..XX...XX..XX......XXXXXXXXXX"

    Returns: 1826

  20. ".....X............................................"

    Returns: 0

  21. "...................X..........................X..."

    Returns: 26

  22. "....................X.X....X........X.X...X..X...."

    Returns: 44

  23. "..X.........X...XX........X......X.X.............X"

    Returns: 80

  24. "..X.....XX.XXXX.....X.X..XXXX....X.X.X......XX..X."

    Returns: 260

  25. "XXXXXXX.XXXXX.XXXXXX.XXXXXXXX.XX.XXXXXX..XXXXX.XXX"

    Returns: 454

  26. "XXXXXXXXXXXXXX.XXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXX"

    Returns: 561

  27. "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXXXXXX"

    Returns: 64

  28. "....................XXXXXXXXXXXXXXXXXXXXXXX......."

    Returns: 0

  29. "X..XXXXXXXXXXXXXX.....XXXXXXX....................."

    Returns: 247

  30. "........XXXXXXX..........X.XX...XX.....XXXXXX..XXX"

    Returns: 930

  31. "..XX....XXX.XXX..XX...XX...X.XXXX.X.XX.X...XX..XXX"

    Returns: 380

  32. "..X.XXX..X.X..XX.X..X.XXX.X.XX.X..X..X..X.X.X.X.X."

    Returns: 203

  33. "X.X.X.X.X.X...X.X.XX.X..X.X.X..X.XX.XX.X.X.X.X.X.X"

    Returns: 190

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

    Returns: 177

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

    Returns: 163

  36. ".X.........XX....X..........."

    Returns: 13

  37. "X.X.XX....X.X..X.XXXX...XXX..XX.X.XXXXXX"

    Returns: 275

  38. "X...X.XX.X."

    Returns: 6

  39. "XXXXX.XX..X..XXXX.X.X....XX.XXX.X..XXXX.XXX"

    Returns: 500

  40. "X............"

    Returns: 0

  41. "..X.X.XXX.XXXX..XX.X"

    Returns: 25

  42. "X.........X..............XXX........."

    Returns: 37

  43. "..XXX."

    Returns: 0

  44. "X.XXXXXXXXX.XXXX.XXXXXXXXX"

    Returns: 164

  45. "XX.XXXXXXX....XXXX.X.X....X."

    Returns: 89

  46. ".X.XX..X.X.XX..XXX...X.X.........X..XXX"

    Returns: 201

  47. "XX..XXX..X.X.X.XXXXXX....XXXX.XXXX.XXXX.XXXX.XXXX"

    Returns: 447

  48. "XX.XXX.XX...X.X.X..X.XXX...........XXX......"

    Returns: 260

  49. ".X.XX.XXX..X...XX.X.XXX.X.X.X....XXXX.X.X"

    Returns: 253

  50. ".XX.XXXX.XXXXX..XXXXX..XXXXX.XXXXXX.XX..X.X...X..."

    Returns: 311

  51. "XXXX....XXX...XXXX..XX....XXXXXXXXXX....X...XX.X"

    Returns: 441

  52. "XXX.XXX.X"

    Returns: 10

  53. "XX.....X.XX......X......XXX.X.X........XXX.....X"

    Returns: 247

  54. ".....XXXXX......XXXXX......XXXXX.....XXXXX"

    Returns: 575

  55. "X..X.X.X.X..X.X.X...X....X..X.X..X.X.X..X...X"

    Returns: 134

  56. "XXXX.XXXX.X.XXXXX"

    Returns: 67

  57. ".XX.XX.X."

    Returns: 5

  58. "X.XX..XXX...XXXX....XXX....XXXX...XXX...XX.X"

    Returns: 351

  59. "XXXXX.X.X.X.X................XXXXXX"

    Returns: 570

  60. "XX......X.X.X.X.X.X.X.X.X.X.X.X.X"

    Returns: 86

  61. ".XX.XX.X.X..X.X.X..XXX..XX.X..X"

    Returns: 106

  62. "XXX..XXX.XXXX"

    Returns: 34

  63. "...XXX..XXX.....X...XXXXX....."

    Returns: 165

  64. "X.X...XXXXXXX.X.XX....XXX.XXX...XX..XXXXX.XXX.X..."

    Returns: 580

  65. "X....X.X"

    Returns: 5

  66. ".XX..XX.X.X.X"

    Returns: 14

  67. "...XXX.....XXX..XX......XXX"

    Returns: 125

  68. ".X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X"

    Returns: 156

  69. ".X..XXXX.....X.X.X..X.X..XXXX.....X.X.X..X"

    Returns: 252

  70. "X.XXX...XXX..XX.X"

    Returns: 42

  71. "......XX...XX.....X..X..XX.X.X....XX..XXXX......X."

    Returns: 223

  72. ".XX...XXX.XX....XXXXX.X...X.X...XXXXX"

    Returns: 303

  73. ".X.X.X.X.X.X.XX."

    Returns: 19

  74. "......XX.X..XXX.....X.X....XX.X....XXXXX.X...XXX.X"

    Returns: 309

  75. "X.X.X.X.X"

    Returns: 6

  76. "XXXXXXXXXXXXXXXXX.XXXXXXXXX.XXXXXX"

    Returns: 153

  77. "XXXXXXXXXX..........XXXXXXXXXX"

    Returns: 1000

  78. "XXXXXXXX........XX........XXXXXXXX"

    Returns: 1024

  79. "X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX"

    Returns: 138

  80. "X.XX....XX.X.XXX....X..XX...XXX...XXXXXX..X.XXXX.X"

    Returns: 381

  81. "X.X.X.X.X.X.....................................XX"

    Returns: 163

  82. "XXXX......X.XXX.X......XXXX"

    Returns: 226

  83. ".XXX.XXX.XXXX."

    Returns: 25

  84. "XXX........XX..XX..XX.XX..XXXXX.....XXXXX...XX"

    Returns: 360

  85. "..X..XXXX"

    Returns: 2

  86. "XXXXXX.XXXX.X.XXXX.XXXXXX"

    Returns: 176

  87. ".XX.XX.X.."

    Returns: 5

  88. ".X.X.X.X.X.X.X.X.X.X.XXX.XXX.XXX.XXX.XXX.X.X.X.X"

    Returns: 147

  89. "XX.XX.XX"

    Returns: 8

  90. "XXXXXX......XXXXX.XXXXX"

    Returns: 241

  91. "X.X.X.X.X...XX"

    Returns: 22

  92. ".XX...X..X..X..X..X..X..X...X...X...X...X...X...X"

    Returns: 157

  93. "XXX...XXX...XXX...XXX...XXX"

    Returns: 162

  94. "XX............................X.X.X.X.X.X.X.X.X.X"

    Returns: 151

  95. ".XX..XXX.XXXX..XX..XXXX.X.X"

    Returns: 104

  96. "X.X.X.X.X.X.........XX"

    Returns: 51

  97. "X....XXXXX.......XX......XXX.....XXXX.....XX"

    Returns: 480

  98. "XXX..X.XXX.X"

    Returns: 29

  99. ".XX...X.X.XX..XX....X.XX..XX.XXX..X.XX.XX.XX..X.XX"

    Returns: 264

  100. "XX..X.XX"

    Returns: 12

  101. "X.XXXX"

    Returns: 1

  102. "..XXX...X....XX...X"

    Returns: 41

  103. "..X.XX"

    Returns: 1

  104. "XX.X.X.X.X.X.X.X.X.X.X.X"

    Returns: 50

  105. "XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X"

    Returns: 190

  106. "...XXXXX..........XXXX.XXXX.XXXX"

    Returns: 298

  107. "XX..X.X.X.X.X"

    Returns: 18

  108. "X.XXXX.XXXXXX.XXXXX.XXXX.XXX.XX.X"

    Returns: 121

  109. ".....XX......XXXXXX"

    Returns: 24

  110. "XXX...XX...XX...XX"

    Returns: 63

  111. "X.XXXXXXXXXXXXXXX"

    Returns: 1

  112. "XX...X...XXX"

    Returns: 27

  113. ".X.X.XXX"

    Returns: 3

  114. "XXXXX.XXXX.XXXX"

    Returns: 41

  115. "XXXX.XXX.XXX"

    Returns: 25

  116. "X.XX.XXX.XXXX.XXXXX..X.XX.XXX.XXXX.XXXXX..XXXXXX"

    Returns: 478

  117. ".XX....XXXXXXXX"

    Returns: 16

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: