Statistics

Problem Statement for "DiceOperation"

Problem Statement

We have a collection of regular dice. Different dice in this collection may have a different number of faces.

For each X, an X-sided die has faces numbered from 1 to X. When rolled, each face comes up with probability 1/X.


You are given the int[] dice: for each die in our collection the number of faces it has.


We are going to roll all dice in our collection (each of them exactly once) and then we'll compute the bitwise xor of all values rolled.

Calculate and return the expected value of the result we'll obtain.

Definition

Class:
DiceOperation
Method:
solve
Parameters:
int[]
Returns:
double
Method signature:
double solve(int[] dice)
(be sure your method is public)

Notes

  • The return value must have an absolute or a relative error at most 10^(-9).
  • All dice rolls are mutually independent.
  • See https://en.wikipedia.org/wiki/Expected_value if you need a definition of the expected value of a random variable.

Constraints

  • dice will contain between 1 and 10 elements, inclusive.
  • Each element of dice will be between 1 and 10^9, inclusive.

Examples

  1. {1, 1, 1, 1, 1}

    Returns: 1.0

    Five "dice", each of them is guaranteed to roll a 1. The xor of five 1s is 1.

  2. {1, 1, 1, 1, 1, 1}

    Returns: 0.0

    As above, but now the xor of six 1s is 0.

  3. {3, 3}

    Returns: 1.3333333333333335

    With probability 1/3 the two values rolled are equal and thus their xor is zero. with probability 2/9 we get the values {1, 2}, their xor is 3. with probability 2/9 we get the values {1, 3}, their xor is 2. with probability 2/9 we get the values {2, 3}, their xor is 1. Thus, the expected value of the result is (1/3)*0 + (2/9)*3 + (2/9)*2 + (2/9)*1 = 4/3.

  4. {3, 4}

    Returns: 2.5

    All the outcomes from the previous example are still possible but now they are somewhat less likely. Here it is also possible to roll {1,4}, {2,4}, or {3,4}, each with probability 1/12.

  5. {5, 9, 6}

    Returns: 5.277777777777778

  6. {47}

    Returns: 24.0

    With a single die the final result is simply the value you rolled.

  7. {67135897, 461908964, 594466507, 487125380, 612881717, 368797830, 276411074}

    Returns: 3.7412093458672154E8

  8. {415062493, 421352828, 660953938, 43925401, 853713570, 449395964, 707195154, 25404581, 110011132, 672709}

    Returns: 5.144498219567383E8

  9. {850666236, 517063357, 777236131, 587001531, 9809443, 985054801}

    Returns: 5.348628596969695E8

  10. {609421725, 459238763, 247011037, 255273358, 561856452, 551852548, 385561481}

    Returns: 3.606549468706943E8

  11. {259897951, 35717066, 602310785, 401759008, 769585355, 738306336, 379516816, 645292644, 367127109}

    Returns: 5.118087432222818E8

  12. {617512216, 818082096, 210435487, 256215402, 846762738, 902613029, 782917678, 982424201, 37880463, 134754155}

    Returns: 5.3675402224092835E8

  13. {105169865, 389595011, 621000791, 411864482, 545789167, 579958393, 872936871}

    Returns: 4.997937336615629E8

  14. {104258889, 696652798, 936243974, 946086476, 243694080, 995373587}

    Returns: 5.365946130573499E8

  15. {234670475, 505764850, 799056098, 118268044, 830082629, 447385547, 649243545}

    Returns: 5.1913297817341816E8

  16. {724619613, 936679872, 307431951, 943979839, 829933622, 869690043, 256605995}

    Returns: 5.3665562002161825E8

  17. {989998541, 280879786, 383264904, 571965508, 607076113, 43067573, 519633100, 335229333, 604235496, 837158198}

    Returns: 5.335083277564635E8

  18. {279434605, 784058148, 557700497, 858579683, 237229315, 651057818, 122337492, 673673333}

    Returns: 5.279911430362E8

  19. {407879374, 521192988, 271805618, 648024764, 994029813}

    Returns: 5.2271223403980637E8

  20. {160204726, 476619357, 16310368, 182853534, 587328862, 673404584, 863645038, 817622290, 88879942, 80106252}

    Returns: 5.267769942090597E8

  21. {548934240, 872583033, 668418987, 587191333, 511648896, 840026800}

    Returns: 5.285999799052236E8

  22. {392537041, 986210306, 815161858, 35628519, 652610127, 284556009, 965501522, 691803010}

    Returns: 5.365635672331726E8

  23. {723820367, 976562441, 506602157, 981853233, 760408747, 685395202, 857357004, 338221219, 890700443, 23872915}

    Returns: 5.3685623913814527E8

  24. {226951149, 371476398, 463467162, 930735751, 742802514}

    Returns: 5.180859273077767E8

  25. {189705945, 504436337, 988878480, 213327222}

    Returns: 5.130458678899559E8

  26. {105675227, 146737413, 784281967, 842998322}

    Returns: 4.9809547899009097E8

  27. {566292667, 421294033, 116055548, 286544299, 476656189, 485224, 700751159}

    Returns: 4.0878630645776457E8

  28. {444604327, 72117358, 396477634}

    Returns: 2.5403108123615634E8

  29. {283733900, 44780632}

    Returns: 1.4269569152438188E8

  30. {194539709, 793651123, 549388646, 897188378}

    Returns: 5.1888230296704924E8

  31. {215981478, 840829696, 829866349, 871544937, 531174523, 567230839, 487039673, 605166844, 609173463}

    Returns: 5.3419784010168123E8

  32. {746288200, 79290911}

    Returns: 3.7423479228087664E8

  33. {897404347, 161670310, 989836380, 583518862}

    Returns: 5.329039234180542E8

  34. {682389689, 931030469, 50128421, 942251503, 667919251, 251793814, 764765052}

    Returns: 5.36026595656366E8

  35. {406657324, 132229152}

    Returns: 2.0396010007722172E8

  36. {95121429, 325052045}

    Returns: 1.6670156754064155E8

  37. {944087159, 588255572}

    Returns: 5.040135525822609E8

  38. {256750959, 657829699, 962589204, 788143802, 574330896, 162354905}

    Returns: 5.306363737695493E8

  39. {622510787, 818650487, 293303964, 664632565, 921594082, 612929098, 86654361, 604472708, 527479944, 367988209}

    Returns: 5.3327479100199795E8

  40. {56030500, 123045708, 443968466, 448443767, 379828289, 973463064, 325142224, 605934919, 906551300, 815748423}

    Returns: 5.356246808114591E8

  41. {641733358, 149950279, 68221558, 545326954, 125699084, 969905991, 495279164, 701102585, 844881431}

    Returns: 5.3417175765698975E8

  42. {884403725, 19196100, 466629861, 869380779, 605515028, 560627571, 819709818, 71072588, 839253914}

    Returns: 5.3604265720726675E8

  43. {841539668, 756726467, 526350672, 539442013, 122544573, 810623579}

    Returns: 5.268948441152972E8

  44. {378160093, 854968509, 355526282, 179226443, 496671191}

    Returns: 4.675758142490338E8

  45. {631062847, 105426213}

    Returns: 3.1773462070089674E8

  46. {494488688, 297197666, 685081510, 585103879, 736604807, 746550456, 739996156, 986463311, 25537872}

    Returns: 5.3585260178198165E8

  47. {100, 3, 257604, 4656, 10217906, 524693902, 225958, 425563, 11548, 9922809}

    Returns: 2.623835828931341E8

  48. {105512, 6821, 225475}

    Returns: 118600.49917378588

  49. {79615330, 248605238, 2253}

    Returns: 1.26742045268018E8

  50. {291753, 957624612, 1610431, 363, 726, 26198, 30816}

    Returns: 4.788126897610862E8

  51. {148920230, 31, 1, 15686, 122929, 794529, 616}

    Returns: 7.446017375499015E7

  52. {10, 13707, 60686, 195, 1071, 944163389}

    Returns: 4.720816953484355E8

  53. {712507, 3678464, 72852875, 43, 606006, 59704, 2, 22148, 964105375}

    Returns: 4.826871373735851E8

  54. {670134, 9609758}

    Returns: 4809464.2061603395

  55. {4102, 8186, 16024318, 1831233, 10443553, 118028, 9, 61759649, 9900, 181148554}

    Returns: 9.297234898230572E7

  56. {61554, 622565, 6778, 11413, 1837, 154240309, 31, 1238, 504}

    Returns: 7.712032521086182E7

  57. {2169, 4762, 759419}

    Returns: 379714.2189732143

  58. {1490618, 99310, 6766033, 80443, 603924608, 693, 48582, 7979, 1, 770967}

    Returns: 3.0196261465508604E8

  59. {2485, 1155, 38, 174, 5, 87575, 11163723, 4, 28, 227717151}

    Returns: 1.1393979122447214E8

  60. {13023, 188624, 3552225}

    Returns: 1777618.0128540318

  61. {1707407, 8, 81}

    Returns: 853704.0002906399

  62. {634467029, 109968450, 31170965, 111693, 62109238, 1969481, 14960}

    Returns: 3.196087324646653E8

  63. {1, 1124, 973630, 322719420, 20448, 13, 9158, 1407, 975788804}

    Returns: 4.996186876185496E8

  64. {16357587, 5196925, 783229648, 67, 260459, 1314, 2784262, 26476952, 4}

    Returns: 3.9174352314426315E8

  65. {2, 432, 371635412, 187448, 3566, 22}

    Returns: 1.858177194880494E8

  66. {560504, 53795077, 838425, 10007, 15045, 4086, 279, 16622762, 197}

    Returns: 2.7322156966098003E7

  67. {2, 5658, 30779660, 2411, 3436, 18604, 303576315, 50253}

    Returns: 1.518644937791684E8

  68. {45, 236, 45708}

    Returns: 22854.661619249484

  69. {1, 536727, 365, 228765, 46809, 1844}

    Returns: 270903.60616137524

  70. {3836615, 1729}

    Returns: 1918308.1017102436

  71. {8, 561}

    Returns: 281.00623885918003

  72. {67559935, 2, 7897, 75, 458}

    Returns: 3.377996802796303E7

  73. {2202, 303475331, 830, 3, 29712, 13968955, 9897411, 471, 2450, 7360097}

    Returns: 1.5177216668807426E8

  74. {50, 1, 362486, 23, 4, 15198, 15123, 329032}

    Returns: 223189.50173065442

  75. {29383994, 251679, 331, 4}

    Returns: 1.469209026432199E7

  76. {84324595, 4, 19, 82219, 830593}

    Returns: 4.216348737161922E7

  77. {1000000000 }

    Returns: 5.000000005E8

  78. {1000000000, 999999999, 999999998, 999999997, 999999996 }

    Returns: 5.368698600088887E8

  79. {1, 1, 1, 1, 1 }

    Returns: 1.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: