Statistics

Problem Statement for "ColorfulBalls"

Problem Statement

We have a bag that contains N balls of different colors. In each turn we pick two balls from the bag, one after another, and paint the second one with the first one's color. After the paint dries, we put both balls back into the bag and shuffle its contents.

You are given a String colors describing the initial colors. More precisely, each character in colors corresponds to a single ball. Balls represented by equal characters have the same color.

Return the expected number of turns until all the balls have the same color.

Definition

Class:
ColorfulBalls
Method:
expectedStepCount
Parameters:
String
Returns:
double
Method signature:
double expectedStepCount(String colors)
(be sure your method is public)

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • colors will contain between 1 and 24 characters, inclusive.
  • Each character in colors will be an uppercase letter ('A'-'Z').

Examples

  1. "AB"

    Returns: 1.0

    In the first turn we will paint one ball with the other's color, and we are done.

  2. "Q"

    Returns: 0.0

    If there is just a single ball, all balls already have the same color, and thus the correct answer is zero.

  3. "AAAAAAA"

    Returns: 0.0

    All balls already have the same color.

  4. "ZCZ"

    Returns: 3.0

  5. "KLM"

    Returns: 4.0

    After the first turn we are sure to get a situation that's similar to the one in the previous example.

  6. "QWERTYUIOPASDFGHJKLZXCVB"

    Returns: 529.0

  7. "WWER"

    Returns: 8.0

  8. "QQQQQQQQQQQQQQQQQQQQQQQQ"

    Returns: 0.0

  9. "AAABB"

    Returns: 11.666666666666668

  10. "AABB"

    Returns: 7.0

  11. "ABBB"

    Returns: 5.5

  12. "QQWWEERRTTYYUUIIOOPPAASS"

    Returns: 517.0

  13. "WQFSDFADGHDERTFGHJSFSRTY"

    Returns: 512.7229437229577

  14. "QWWEEERRRRTTTTTYYYYYYUUU"

    Returns: 489.2680451127883

  15. "MNBVCXZLKJHGFDSAPOIUYTTT"

    Returns: 525.9545454545696

  16. "ABBCCC"

    Returns: 20.74999999999998

  17. "ABCDEFFF"

    Returns: 45.833333333333265

  18. "ABCDEFGGG"

    Returns: 60.85714285714299

  19. "ABCDEFGHIII"

    Returns: 96.8888888888891

  20. "ABCDEFGHIJJJ"

    Returns: 117.89999999999944

  21. "ABCDEFGHIJKLMNOPQRSTUVVV"

    Returns: 525.9545454545696

  22. "AABCDDEFG"

    Returns: 62.0

  23. "QQQQQQQQQQQQQQQQQQQZQQQQ"

    Returns: 85.88870475499701

  24. "GNXNXHFDHGZDG"

    Returns: 136.90909090908957

  25. "NCFDSRTRDFGDSSDFGBVFDSSE"

    Returns: 499.8601731601823

  26. "BAAAAAAB"

    Returns: 28.29999999999999

  27. "BEECFEADCCFADEDEDCAADA"

    Returns: 402.2131578947361

  28. "AAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 0.0

  29. "ABEDFGECGED"

    Returns: 94.88888888888906

  30. "AABB"

    Returns: 7.0

  31. "CEACDECEDA"

    Returns: 72.7499999999999

  32. "FIIFCBJAIJF"

    Returns: 92.77777777777793

  33. "DIIKGAIIEIDCHEILJBGHA"

    Returns: 378.8531991743998

  34. "DADFCABAEFADECEC"

    Returns: 208.48901098901254

  35. "CBBBCCAA"

    Returns: 41.66666666666663

  36. "AAB"

    Returns: 3.0

  37. "ADEEAC"

    Returns: 23.0

  38. "HFCABEEBDFFBHF"

    Returns: 157.56818181818124

  39. "DGEGBDB"

    Returns: 33.0

  40. "EFFDACE"

    Returns: 34.0

  41. "AA"

    Returns: 0.0

  42. "IJAIIBAAFCCCJAHFCJBA"

    Returns: 336.07066993464156

  43. "ADDEFACBGGBD"

    Returns: 114.89999999999961

  44. "CABCB"

    Returns: 14.0

  45. "HCHEDGEFIAFEHBCBAH"

    Returns: 275.6791666666663

  46. "JILKDKFAEGLMLMKJDDHBDAL"

    Returns: 465.56190476189937

  47. "BBAAABBAAAA"

    Returns: 67.35317460317461

  48. "DIBIFAIJCFEBEHIGBHGEIKD"

    Returns: 463.40401002505826

  49. "BAAAABABAABABBBAABAABA"

    Returns: 302.3042064488658

  50. "EAEECACCEDDCEACC"

    Returns: 193.5457042957055

  51. "AAAAA"

    Returns: 0.0

  52. "AAAAAAAA"

    Returns: 0.0

  53. "BBBCDDDDACBCC"

    Returns: 124.8545454545449

  54. "AADEABEBDBCBDCC"

    Returns: 179.44871794871744

  55. "BGJBGDDBBG"

    Returns: 70.33928571428561

  56. "BBCCAACC"

    Returns: 40.26666666666664

  57. "AAAAAAAAA"

    Returns: 0.0

  58. "CBCBD"

    Returns: 14.0

  59. "CBCBAABACACB"

    Returns: 101.7333333333333

  60. "KJLERTURIUKIJSOPQFSKKTLQ"

    Returns: 514.8138528138678

  61. "BAEDDEBCFADCFC"

    Returns: 158.8333333333328

  62. "JEGCBEBFGGH"

    Returns: 94.88888888888906

  63. "BBHDDAFGDHE"

    Returns: 94.88888888888906

  64. "BCADDBBCGCFDF"

    Returns: 133.7272727272717

  65. "ABABBAAABBAAAABABBBBBA"

    Returns: 309.97238826704773

  66. "GFGAEAFCDBGBCBDCDCGBCCDE"

    Returns: 491.463499658243

  67. "AABBAAAB"

    Returns: 33.783333333333324

  68. "AAABAAAAABBA"

    Returns: 69.05595238095235

  69. "CABCCCCAABBBDBDBDCCDDA"

    Returns: 385.2289860681122

  70. "BBABABBAABAB"

    Returns: 84.39047619047612

  71. "MILLMCMACNNQJGMECKIBPJPO"

    Returns: 514.7683982684132

  72. "AEBAABACDDBCBC"

    Returns: 152.21969696969663

  73. "A"

    Returns: 0.0

  74. "AAABCBABAC"

    Returns: 65.42857142857133

  75. "EBCFEBG"

    Returns: 34.0

  76. "ABCDEFGHIJKLMNOPQRSTUVWW"

    Returns: 528.0

  77. "ABCDEFGHIJKLMNOPQRSTUVWX"

    Returns: 529.0

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: