Statistics

Problem Statement for "Consensus"

Problem Statement

We have a population of people. There are D distinct opinions on a controversial topic, numbered 0 through D-1. Initially, opinions[i] people hold opinion i.

We will model the change of opinion as follows: In each step, person A (chosen uniformly at random) talks to person B (chosen uniformly at random from people other than A) and convinces them to change their opinion to the opinion currently held by person A.

For example, suppose initially person A holds opinion 0, person B holds opinion 1, and person C holds opinion 2. Next, suppose A talked to B and then C talked to A. In the resulting state B now holds opinion 0, while A and C both hold opinion 2.

Perhaps quite surprisingly, under this model for any initial distribution of opinions the people will eventually reach a consensus with probability 1.

Given the initial distribution of opinions, calculate the expected number of steps until a consensus is reached.

Definition

Class:
Consensus
Method:
expectedTime
Parameters:
int[]
Returns:
double
Method signature:
double expectedTime(int[] opinions)
(be sure your method is public)

Notes

  • All random choices are mutually independent.
  • Your answer must have an absolute or a relative error at most 1e-9.

Constraints

  • opinions will have between 1 and 50 elements, inclusive.
  • Each element of opinions will be between 1 and 50, inclusive.

Examples

  1. {47}

    Returns: 0.0

    The simplest case: we already have a consensus.

  2. {1, 1}

    Returns: 1.0

    In the very first step one of the people will convince the other to their opinion, thereby producing a consensus.

  3. {1, 1, 1}

    Returns: 4.0

    Regardless of who is chosen in the first step, after the first step one of the opinions vanishes and another one will now be held by two people. From that state, with probability 1/3 nothing happens (the two chosen people share the majority opinion), with probability 1/3 the minority opinion becomes the new majority opinion and vice versa, and with probability 1/3 the consensus will be reached. From these probabilities we can show that the expected number of additional steps to reach the consensus is 3, and thus for the initial configuration the answer is 4.

  4. {4, 1}

    Returns: 8.333333333333334

    In the beginning we have one dissenting person and four people who agree on a different opinion. From this situation we will often reach the consensus quite quickly, but it is also possible that they will "argue" for a long time and afterwards the opinion that was initially only held by one person will be the one reached in the consensus.

  5. {3, 2, 5, 1}

    Returns: 84.62698412698413

  6. {5, 28, 36, 30, 37, 22, 17, 33, 25, 26, 40, 3, 27, 43, 2, 7, 1, 17, 31, 47, 35, 1, 21, 37}

    Returns: 315873.1723919995

  7. {15, 16, 34, 33, 23, 29, 16, 3, 36, 24, 46, 45, 23, 39, 22, 36, 37, 49, 13, 16, 47, 3, 9, 22, 7, 24, 38, 25, 33}

    Returns: 568354.9117491597

  8. {17, 7, 42, 15, 45, 22, 14, 31, 48, 8, 50, 27, 39, 23, 44, 19, 50, 16, 36, 17, 23, 35, 37, 3, 31, 20, 37, 50, 26, 17, 47, 34, 15, 39, 8, 41}

    Returns: 1047091.3869041028

  9. {25, 32, 17, 39, 36, 10, 29, 1, 11, 36, 41, 49, 6, 5, 18}

    Returns: 119508.04814223226

  10. {40, 35, 31, 28, 24, 49, 3, 39, 17, 42, 39, 34, 44, 31, 46, 41, 21, 2, 37, 16, 14, 23, 28, 45, 12, 12, 31, 13, 9, 7, 9, 47, 37, 23}

    Returns: 845524.2421179237

  11. {26, 7, 18, 29, 1, 42, 8, 27, 5, 24, 2, 17, 3, 9, 12, 48, 33, 32, 13, 50, 32, 34, 30, 37, 37, 1, 45, 5, 12, 10, 35, 22, 41, 3, 40}

    Returns: 609839.4369296624

  12. {46, 4, 25, 8, 2, 6, 20, 4, 36, 20, 16, 40, 47, 35, 10, 36, 38}

    Returns: 147105.16886415024

  13. {18, 40, 37, 6, 37, 32, 22, 36, 4, 8, 27, 27, 23, 20, 37, 49, 32, 39, 9, 5, 33, 8, 30, 42, 30, 2, 28, 37, 34, 49, 5, 19, 46, 32, 33, 8, 49, 16, 23, 22, 11, 30, 2, 38, 7, 43, 30, 30, 18, 41}

    Returns: 1676600.5645847693

  14. {44, 45, 45, 2, 36, 13, 44, 19, 3, 50, 17, 35, 31, 25, 5, 47, 7, 34, 46, 38, 39, 31, 35, 48, 24, 38, 20, 27, 50, 44, 14, 47, 41, 6, 7, 33}

    Returns: 1165614.2590306737

  15. {26, 22, 35, 24, 7, 6, 40, 48, 28, 24, 4, 23, 38, 4, 26, 41, 18, 17, 14, 19, 14}

    Returns: 220592.25726747542

  16. {43, 20, 29, 50, 29, 21, 44, 4, 10, 38, 31, 1, 2, 28, 30, 34, 29, 40, 17, 19, 7, 20, 8, 11, 28, 22, 32, 28, 16, 33, 37}

    Returns: 565967.815024623

  17. {17, 21, 36, 2, 39, 44, 25, 39, 38, 45, 39, 45, 40, 30, 40, 36, 12, 44, 45, 25, 3, 12, 40, 12, 40, 5, 32, 27, 4, 15, 30, 12, 39, 26}

    Returns: 901270.9010654204

  18. {40, 9}

    Returns: 1098.17403527868

  19. {5, 36, 25, 1, 25, 32, 48, 30, 41, 24, 47, 8, 33, 26, 7, 6, 27, 27, 36, 7, 40, 12, 43, 32, 31, 29, 39, 6, 26, 34, 33, 21, 28, 48, 13, 21, 26, 5, 9, 46, 32, 22, 42, 42, 7, 17, 32, 6, 23}

    Returns: 1555030.812777526

  20. {26, 40, 6}

    Returns: 3678.1562982117134

  21. {15, 34, 42, 14, 33, 17, 46, 49, 20, 33, 39, 8, 36, 4, 19, 47, 12, 32, 45, 16, 26, 40, 31, 1, 38, 26, 39, 16, 41, 36, 24, 7, 22, 5, 11, 38, 7, 16, 12, 6}

    Returns: 987847.0837584321

  22. {33, 11, 47, 11, 5, 6, 9, 38, 26, 23, 8}

    Returns: 43388.84667246467

  23. {19, 36, 41, 15, 44, 23, 50, 6, 42, 21, 7, 3, 13, 36, 9, 22, 6, 21, 50, 46, 43, 28, 33, 35, 37, 49, 50, 44}

    Returns: 670200.8732766793

  24. {34, 34, 28, 41, 29, 28, 44, 27, 47, 32, 2, 13, 21, 4, 39, 28, 7, 29, 50, 38, 8, 7, 22, 28}

    Returns: 397721.02056607633

  25. {4, 22, 49, 12, 43, 27, 31, 48, 34, 31, 45, 34, 8, 15, 13, 41, 2, 35, 32, 21, 10, 44, 11, 50, 19, 5, 4, 48, 39, 20, 3, 42, 40, 43, 1, 17, 23, 13, 36, 14, 24, 24, 9, 13, 29, 40, 3, 48, 20}

    Returns: 1511774.2351710591

  26. {43, 20, 27, 8, 28, 27, 23, 49, 32, 17, 3, 47, 37, 47, 45, 32, 15, 18, 26, 4, 2, 26, 13, 50, 27, 24, 34, 6, 23, 47, 40, 41, 22, 29, 5, 5, 31, 18, 5, 11}

    Returns: 995564.8511733959

  27. {15, 28, 31, 13, 19, 1, 8, 39, 37, 1, 17, 35, 14, 35, 24}

    Returns: 95388.76396860891

  28. {14, 22, 26, 3, 44, 42, 38, 27, 21, 35, 23, 1, 7, 2, 20, 4, 39, 14, 34, 40, 1, 3, 36, 38, 4, 25, 49, 30, 13, 6, 18, 44}

    Returns: 509691.90865748934

  29. {26, 33, 23, 3, 5, 20, 39, 46, 20, 4, 40, 29, 30, 27, 47, 47, 22, 47, 6, 17, 27, 24, 7, 46, 25, 25, 12, 19, 2, 2, 37, 44, 37, 13, 9, 36, 15, 6, 1, 28, 28, 27}

    Returns: 984167.4239547413

  30. {28, 38, 47, 9, 10, 50, 47, 48, 48, 25, 35, 42, 30, 17, 41, 42, 10, 5, 3, 38, 16, 47, 38, 9, 5, 2, 9, 8, 34, 50, 9, 40, 19, 37, 39, 27, 36, 48, 32, 40, 38, 2, 11, 39, 35, 38, 41}

    Returns: 1827311.1777288928

  31. {10, 15, 8, 10, 19, 40, 31, 42, 32, 30, 39, 20, 27, 49, 29, 39, 12, 1, 28, 32, 32, 47, 27, 22, 24, 36, 20, 20, 26, 25, 3, 40, 49, 34, 18, 10, 30, 26, 7, 50, 43, 7, 38, 3, 24, 41, 22, 43}

    Returns: 1615020.191494635

  32. {37, 49, 10, 1, 17, 23, 11, 40, 3, 27, 31, 46, 21, 10, 18, 17, 22, 27, 43, 8, 14, 43, 12, 40, 15, 19, 43, 16, 30, 45, 50, 34, 22, 10, 34, 24, 8, 10, 12, 37, 15, 35, 37, 34, 50}

    Returns: 1301563.8131317005

  33. {41, 41, 35, 14, 41, 16, 3, 24, 25, 49, 12, 32, 39, 47, 47, 11, 13, 26, 47, 43, 4, 31}

    Returns: 397966.77065030806

  34. {36, 35, 5, 17, 7, 9, 43, 33, 48, 38, 43, 14, 18, 39, 25, 8, 17, 36, 23, 8, 25, 24}

    Returns: 293788.3254498

  35. {35, 15, 19, 17, 39, 44, 45, 42, 21, 37, 3, 49, 40, 14, 19, 29, 50, 21, 49, 8, 10, 38, 12, 17, 22, 18, 7, 19, 14, 3, 49, 18, 40, 42, 14, 13, 44, 32, 32, 5, 25, 42, 2}

    Returns: 1220002.567208753

  36. {50, 38, 10, 7, 27, 20, 15, 27, 49, 13, 6, 14, 42, 41, 43, 15, 36, 6, 36, 27, 20, 21, 24, 8, 6, 45, 21, 30, 14, 50, 8, 42, 6, 35, 43, 22, 49, 37, 45, 31, 15, 4, 21}

    Returns: 1231127.746572113

  37. {47, 48, 43, 25, 17, 50, 38, 4, 5, 17, 30, 33, 15, 33, 33, 32, 19, 21, 28, 34, 16}

    Returns: 334677.2738520098

  38. {44, 45, 42, 22, 37, 41, 14, 37, 12, 13, 16, 49, 3, 2, 45, 39, 33, 39, 17, 48, 39, 19, 13, 22, 38, 39, 41, 36, 22, 33, 12, 48, 50, 21, 24, 12, 11, 43, 47, 32, 5}

    Returns: 1428017.9209537427

  39. {26, 30, 45, 29}

    Returns: 14261.433950289176

  40. {40, 7, 41, 45, 32, 41, 18, 22, 19, 45, 14, 45, 28, 5, 17, 40, 25, 21, 30, 19}

    Returns: 296639.3031969628

  41. {16, 12, 24, 15, 20, 3, 14, 45, 37, 31, 2, 23}

    Returns: 54706.99151745204

  42. {41, 19}

    Returns: 2180.929495003991

  43. {36, 27, 49, 34, 16, 30, 30, 4, 6, 47, 9, 47, 26, 29, 12, 16, 3, 26, 44}

    Returns: 231772.14692433464

  44. {35, 34, 7, 36, 2, 35, 29, 35, 32, 38, 11, 11, 49, 16, 18, 43, 21, 13, 36, 44, 32, 33, 48, 18, 30, 17, 22, 34, 8, 15}

    Returns: 628684.8031142451

  45. {17, 15, 3, 9, 16, 45, 48, 46, 29, 48, 46, 50, 6, 21, 47, 36, 48, 42, 42, 14, 21, 41, 7, 17, 34, 11, 18, 24, 9, 48, 11, 6, 12, 4, 50, 33, 12, 39, 42, 36, 40, 40, 7, 19, 3, 21, 12, 6, 29, 18}

    Returns: 1659564.6231153223

  46. {20, 13, 38, 49, 49, 32, 40, 47}

    Returns: 76395.31562870508

  47. {50, 9, 16, 46, 35, 16, 39, 20, 17, 44, 48}

    Returns: 108383.89762839764

  48. {2, 20, 13, 48, 2, 28, 12, 18, 45, 32, 13, 29, 1, 24, 41, 16, 26, 33, 12, 12, 12, 39, 4, 14, 21, 40, 26, 42, 20, 47, 18}

    Returns: 491835.4891164477

  49. {6, 20, 15, 3, 36, 31, 20, 16, 19, 30, 12, 12, 36, 20, 30, 19, 19, 40, 48, 4, 20, 3, 43, 5, 40, 39, 26, 37, 33, 28, 10, 25, 25, 43, 35, 15, 34, 36, 27, 45, 29, 35}

    Returns: 1124182.4688297221

  50. {17, 26, 21, 22, 8, 25, 28, 9, 6, 48, 28, 16, 16}

    Returns: 68822.07730917276

  51. {17, 35}

    Returns: 1650.7956871750007

  52. {22, 26, 35}

    Returns: 5411.608076828634

  53. {46, 13, 17, 5, 44, 4, 16, 12, 40, 23, 23, 6, 44, 32, 17, 18, 50, 39, 24, 14, 4}

    Returns: 232130.7742571106

  54. {32, 15, 43, 7, 34, 20, 12, 26, 18, 48, 38, 46, 13, 34, 18, 49, 11, 11}

    Returns: 216701.78691489057

  55. {10, 18, 31, 7, 19, 45, 17, 10, 26, 44, 15, 15, 49, 12, 6, 19, 34, 10, 30, 50, 19, 3}

    Returns: 230579.4547295608

  56. {7, 7, 7, 7, 7, 7, 7, 7, 7 }

    Returns: 3649.658560731479

  57. {1, 1, 1 }

    Returns: 4.0

  58. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    Returns: 287514.76260084944

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: