Statistics

Problem Statement for "BlackWhiteMagic"

Problem Statement

Powerful sorceress Camomile has N magical creatures sitting in cages in a row. Each creature is either black or white. Cages are conveniently numbered from 1 to N. Camomile's dark twin sister Romashka has shuffled these creatures. Their order after they have been shuffled is given in the String creatures, where the i-th (1-based) character is 'B' if the creature in cage i is black and 'W' if it is white.

Now Camomile wants to put the creatures back in order. The creatures are considered to be in order if the white creatures all sit in cages with numbers from 1 to W, where W is the total number of white creatures, and the black creatures all sit in cages with numbers from W+1 to N. To achieve the necessary order, Camomile can use N different spells, also numbered from 1 to N. The spell with number i can swap creatures from two cages if the distance between those cages is exactly equal to i. The distance between cages with numbers a and b is calculated as |a - b|. She can use each spell at most once and each spell can swap only one pair of creatures.

Return the minimum number of spells that she needs to use in order to put creatures back in order. If it is impossible, return -1.

Definition

Class:
BlackWhiteMagic
Method:
count
Parameters:
String
Returns:
int
Method signature:
int count(String creatures)
(be sure your method is public)

Constraints

  • creatures will contain between 1 and 50 characters, inclusive.
  • Each character in creatures will be either 'B' or 'W'.

Examples

  1. "WBBW"

    Returns: 1

    By using the second spell and swapping the creatures in the second and last cages we will obtain the required order: "WWBB".

  2. "WWWWBBBB"

    Returns: 0

    Here all creatures are already in the required order, so no spells are needed.

  3. "BBWW"

    Returns: 2

    One possible way is to start with swapping the first and third creatures: BBWW -> [spell 2 on creatures 1 and 3] -> WBBW WBBW -> [spell 1 on creatures 1 and 2] -> BWBW BWBW -> [spell 3 on creatures 1 and 4] -> WWBB However, a better solution can be obtained if you start with swapping the second and third creatures: BBWW -> [spell 1 on creatures 2 and 3] -> BWBW BWBW -> [spell 3 on creatures 1 and 4] -> WWBB

  4. "BWWWWWWWBBBBBBBW"

    Returns: 1

  5. "WBWBWBWBWWBWBWBWBBBWBW"

    Returns: 5

  6. "B"

    Returns: 0

  7. "W"

    Returns: 0

  8. "BB"

    Returns: 0

  9. "WB"

    Returns: 0

  10. "BW"

    Returns: 1

  11. "WW"

    Returns: 0

  12. "BBB"

    Returns: 0

  13. "WBB"

    Returns: 0

  14. "BWB"

    Returns: 1

  15. "WWB"

    Returns: 0

  16. "BBW"

    Returns: 1

  17. "WBW"

    Returns: 1

  18. "BWW"

    Returns: 1

  19. "WWW"

    Returns: 0

  20. "BBBB"

    Returns: 0

  21. "WBBB"

    Returns: 0

  22. "BWBB"

    Returns: 1

  23. "WWBB"

    Returns: 0

  24. "BBWB"

    Returns: 1

  25. "WBWB"

    Returns: 1

  26. "BWWB"

    Returns: 1

  27. "WWWB"

    Returns: 0

  28. "BBBW"

    Returns: 1

  29. "WBBW"

    Returns: 1

  30. "BWBW"

    Returns: 1

  31. "WWBW"

    Returns: 1

  32. "BBWW"

    Returns: 2

  33. "WBWW"

    Returns: 1

  34. "BWWW"

    Returns: 1

  35. "WWWW"

    Returns: 0

  36. "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"

    Returns: 0

  37. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 0

  38. "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW"

    Returns: 13

  39. "WBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWB"

    Returns: 12

  40. "BWBWBWBWBWBWBWBWBWBWBWBWBBWBWBWBWBWBWBWBWBWBWBWBWB"

    Returns: 12

  41. "WBWBWBWBWBWBWBWBWBWBWBWBWWBWBWBWBWBWBWBWBWBWBWBWBW"

    Returns: 12

  42. "BWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"

    Returns: 1

  43. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBW"

    Returns: 1

  44. "BBBBBBBBBBBBBBBBBBBBBBBBBWWWWWWWWWWWWWWWWWWWWWWWWW"

    Returns: 25

  45. "WWWWWWWWWWWWWWWWWWWWWWWWWBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 0

  46. "WBBWBBBBBWWWWWWWBWBWBBWBBWBBWWBWBWBWWWBWWB"

    Returns: 11

  47. "WBWWWBWBBWWWWWWBBWBBBBBBBBBWBWBBBW"

    Returns: 4

  48. "BWWBBBBBBWBBWBWWBBBWWWWWBBBWBWBWWBBBWWWWBBBW"

    Returns: 13

  49. "WWWBWBBBWBBBWWWWWWWWWWWBWBBBBBWBBWBWB"

    Returns: 7

  50. "BWBWWWBBWB"

    Returns: 2

  51. "BBWBWBBWBWWBBBBWWBWBWWWBW"

    Returns: 7

  52. "BWBWWBWWBBWBBB"

    Returns: 3

  53. "WBWWWWWWBW"

    Returns: 1

  54. "BBBBBBWWBWWBBBBBWBWBWWBBWBBBWBBBBWWWBBBWBBWWWWBBW"

    Returns: 13

  55. "BBBWWWBWWWWBWBWBBWWBBWBWWB"

    Returns: 6

  56. "WBBWBBBWBWWWBWBWWBBWBWBWBBBBBWBWBWBBBBBBWWBBBBWBWW"

    Returns: 10

  57. "BWBWBBWBBBWWWBBWBBWWBBBBBBBWWBBBWBWWBBBBBBBWBBWWBB"

    Returns: 10

  58. "BWBWBWBWWBWWBBBBWBBBWBBBBWWWBBBBBBBWBWBWBWWWBBWWWB"

    Returns: 12

  59. "BBWWWBBBBWWBWBBWWWWWWBWBWBWBWBWWBBBBBWWWWWWBWWBWWB"

    Returns: 13

  60. "BWWWWBWBWBBWBBWBBWWWBWBBBWBWWWWBWWWWWBWBBWWBWBWWBB"

    Returns: 14

  61. "WBBBWWWBWWWWBWWBWWBBWBWBBBBWBBWBBWBBBBWWWWWWBBBWWB"

    Returns: 11

  62. "WBBBBWWWWBBWWBBWBBWWWWWWWWWWBBWWWBBBBWWWWBWBWWWWWW"

    Returns: 12

  63. "WWBBBBBWWBBBWWWWBWBWWWBWWWWWBWBWBWBBBBWWBBWWBWWWWW"

    Returns: 12

  64. "WWWBWBBWWWWWBWWBBWWWBBWWWBBBBBWBBWBBWBWBBBWWBBWBBB"

    Returns: 8

  65. "BBBWWWWBBBBWBBBBBWWWWBWBWWWBBWWWWWWWBWWWBWBWBWBWWW"

    Returns: 16

  66. "BBBBB"

    Returns: 0

  67. "BBWWBBWBBBBBWWBBBBWWWWBBBBWBWBWBWWWBBWWWBBBWWWB"

    Returns: 13

  68. "BBBBBBBBBBW"

    Returns: 1

  69. "WBWBW"

    Returns: 1

  70. "BWBBBBBBBBBBBBBB"

    Returns: 1

  71. "BBBBW"

    Returns: 1

  72. "WWWWWBW"

    Returns: 1

  73. "BBWWWWWBBWWWB"

    Returns: 3

  74. "WWWWWWWWWWWWWWWBW"

    Returns: 1

  75. "WWWWBW"

    Returns: 1

  76. "WBWBWBW"

    Returns: 2

  77. "BWWBWW"

    Returns: 2

  78. "WWWWWWWWWWW"

    Returns: 0

  79. "WWWWW"

    Returns: 0

  80. "WWWWWWWWWWWWWB"

    Returns: 0

  81. "BWBBB"

    Returns: 1

  82. "WBBBBB"

    Returns: 0

  83. "BBBBWW"

    Returns: 2

  84. "WWBBBBBBBB"

    Returns: 0

  85. "WWWBW"

    Returns: 1

  86. "WWWWWWBW"

    Returns: 1

  87. "BWWWW"

    Returns: 1

  88. "WBBBBBBBB"

    Returns: 0

  89. "BBBBBBBBB"

    Returns: 0

  90. "BBBBBBBBBBBB"

    Returns: 0

  91. "BBBBBBBBBW"

    Returns: 1

  92. "BWBBBBB"

    Returns: 1

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: