Statistics

Problem Statement for "CentaurCompany"

Problem Statement

The Centaur company has N servers, numbered 1 through N. These servers are currently connected into a network. The topology of the network is a tree. In other words, there are exactly N-1 bidirectional cables, each connecting some two servers in such a way that the entire network is connected.


The Centaur company is about to split into two new companies: the Human company and the Horse company. When this happens, the companies will divide the servers randomly. More precisely, for each of the N servers the two companies will flip a fair coin, and the winner of the coin flip gets the server. Once they divide the servers, each company will configure their own servers not to use the cables that lead to the servers of the other company.


Of course, it may then happen that some pairs of servers that belong to the same company will not be able to communicate any more. Therefore, each of the new companies will then use new, additional cables to connect all of its servers to the same network. New cables can be added for free. However, each of the servers currently only has one empty slot into which an end of a cable can be inserted. Adding one additional empty slot to a server costs 1. If desired, it is possible to add multiple slots to the same server. Each of the companies will connect their servers using a way with the smallest possible cost.


You are given two int[]s a and b, each containing N-1 elements. These two arrays describe the original cables: for each i, there is a cable that connects the servers a[i] and b[i].


Compute and return the expected value of the total cost paid by the two companies to connect their networks. (The expectation is taken over all possible ways in which they can divide the N servers.)

Definition

Class:
CentaurCompany
Method:
getvalue
Parameters:
int[], int[]
Returns:
double
Method signature:
double getvalue(int[] a, int[] b)
(be sure your method is public)

Notes

  • N can be determined as (1 + the length of a).
  • The expected value of a variable can be seen as the average value of the variable, where the average is taken over many rounds of the experiment. See http://en.wikipedia.org/wiki/Expected_value for a formal definition.
  • Your return value must have a relative or absolute error of at most 1e-9.

Constraints

  • N will be between 2 and 36, inclusive.
  • a and b will contain exactly N-1 elements.
  • Each element of a and b will be between 1 and N, inclusive.
  • The network defined by a and b will be a tree (as explained in the problem statement).

Examples

  1. {1}

    {2}

    Returns: 0.0

    Regardless of the result of the coin flips, the companies don't need additional cables to connect their own servers. Therefore, the expected cost is zero.

  2. {1,1,1}

    {2,3,4}

    Returns: 0.125

    If the Horse company gets only the server 1 and the Human company gets the other servers, the Human company must add one empty slot. For example, the Human company can add one empty slot to the server 2 and add new cables to connect the server 2 with the servers 3 and 4. Similarly, if the Human company gets only the server 1 and the Horse company gets the other servers, the cost will also be 1. In all other cases the cost will be 0. The expected cost is 1/(2^4) + 1/(2^4) = 1/8.

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

    {2,3,4,5,6}

    Returns: 0.375

    For example, if the Horse company gets only the server 2 and the Human company gets the other servers, the Human company must add one empty slot. In the picture below, initially each server has one empty slot (blue). The Human company adds one extra slot (yellow) to the server 5. The Human company also adds cables that connect the servers 1 and 5, 3 and 5, and 4 and 6.

  4. {1,2,3,4,5,6,7,8,9}

    {2,3,4,5,6,7,8,9,10}

    Returns: 0.41796875

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

    {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36}

    Returns: 15.500000001076842

  6. {2}

    {1}

    Returns: 0.0

  7. {1, 1}

    {2, 3}

    Returns: 0.0

  8. {1, 1, 4}

    {3, 2, 1}

    Returns: 0.125

  9. {1, 4, 1, 5}

    {4, 3, 2, 4}

    Returns: 0.125

  10. {6, 2, 2, 5, 4}

    {5, 1, 5, 3, 2}

    Returns: 0.25

  11. {3, 7, 5, 3, 3, 5}

    {2, 1, 7, 4, 7, 6}

    Returns: 0.3125

  12. {6, 8, 6, 8, 7, 1, 8}

    {8, 3, 4, 2, 8, 3, 5}

    Returns: 0.7265625

  13. {1, 5, 1, 3, 1, 2, 2, 9}

    {8, 2, 5, 1, 6, 7, 4, 3}

    Returns: 0.66015625

  14. {10, 7, 2, 5, 6, 2, 4, 9, 7}

    {8, 10, 10, 4, 1, 6, 2, 2, 3}

    Returns: 0.646484375

  15. {1, 1, 1, 10, 6, 2, 7, 3, 4, 11}

    {5, 8, 9, 5, 3, 8, 1, 5, 5, 5}

    Returns: 1.078125

  16. {5, 11, 8, 5, 9, 2, 6, 10, 11, 6, 11}

    {12, 1, 6, 11, 12, 3, 7, 1, 6, 4, 3}

    Returns: 0.9169921875

  17. {6, 6, 12, 4, 10, 8, 1, 3, 7, 9, 13, 6}

    {1, 8, 2, 6, 4, 5, 11, 10, 8, 10, 10, 12}

    Returns: 1.101318359375

  18. {9, 10, 3, 11, 9, 6, 4, 3, 5, 12, 5, 3, 12}

    {2, 2, 1, 2, 7, 2, 6, 6, 10, 14, 13, 8, 2}

    Returns: 1.1785888671875

  19. {5, 7, 6, 1, 12, 2, 6, 5, 7, 6, 1, 1, 9, 10}

    {8, 14, 2, 2, 3, 15, 13, 12, 2, 11, 4, 12, 1, 1}

    Returns: 1.4061279296875

  20. {10, 3, 15, 15, 10, 4, 13, 11, 4, 16, 14, 14, 8, 2, 14}

    {4, 8, 8, 1, 6, 5, 3, 10, 8, 9, 7, 9, 12, 9, 11}

    Returns: 1.26507568359375

  21. {16, 6, 6, 10, 9, 3, 1, 8, 4, 14, 2, 2, 13, 7, 15, 4}

    {13, 1, 5, 3, 2, 11, 17, 2, 1, 3, 1, 12, 1, 14, 13, 3}

    Returns: 1.6319732666015625

  22. {12, 11, 14, 17, 6, 6, 5, 8, 17, 8, 18, 2, 2, 1, 15, 11, 10}

    {7, 18, 15, 16, 7, 10, 4, 5, 2, 10, 14, 1, 18, 13, 9, 3, 18}

    Returns: 1.21539306640625

  23. {11, 15, 13, 6, 1, 19, 15, 15, 7, 6, 12, 17, 16, 5, 15, 17, 12, 17}

    {12, 18, 14, 1, 9, 3, 10, 14, 2, 12, 8, 12, 19, 17, 2, 2, 19, 4}

    Returns: 1.784912109375

  24. {1, 8, 5, 12, 19, 11, 14, 13, 5, 17, 2, 8, 18, 2, 18, 19, 16, 13, 8}

    {13, 13, 1, 4, 9, 12, 13, 18, 7, 19, 5, 11, 10, 20, 16, 6, 15, 3, 6}

    Returns: 1.6330623626708984

  25. {12, 2, 17, 12, 18, 19, 13, 16, 3, 2, 12, 5, 7, 12, 5, 14, 19, 11, 13, 9}

    {11, 14, 15, 1, 7, 8, 20, 12, 6, 8, 18, 6, 10, 4, 12, 1, 21, 17, 12, 11}

    Returns: 2.009258270263672

  26. {12, 20, 20, 3, 16, 21, 6, 9, 14, 22, 2, 7, 1, 2, 4, 4, 14, 8, 15, 5, 21}

    {18, 11, 16, 4, 4, 4, 18, 10, 13, 17, 21, 16, 18, 19, 9, 22, 16, 2, 21, 4, 6}

    Returns: 2.0896859169006348

  27. {2, 8, 16, 16, 1, 7, 15, 23, 13, 13, 12, 18, 9, 3, 18, 5, 1, 8, 7, 3, 3, 2}

    {15, 21, 19, 1, 2, 10, 22, 4, 6, 16, 17, 20, 3, 23, 8, 2, 12, 9, 14, 11, 14, 14}

    Returns: 1.7677412033081055

  28. {6, 5, 12, 1, 9, 14, 19, 22, 12, 17, 19, 17, 21, 13, 23, 2, 23, 11, 9, 5, 17, 11, 8}

    {17, 18, 20, 19, 17, 23, 15, 7, 23, 11, 11, 18, 24, 12, 3, 23, 16, 23, 4, 10, 21, 22, 2}

    Returns: 2.3211158514022827

  29. {7, 5, 20, 15, 21, 5, 10, 6, 13, 9, 14, 19, 17, 15, 5, 5, 3, 11, 15, 1, 3, 5, 13, 3}

    {18, 25, 22, 2, 23, 7, 8, 5, 24, 24, 22, 3, 2, 21, 22, 4, 12, 7, 8, 6, 21, 15, 7, 16}

    Returns: 2.349271595478058

  30. {18, 13, 18, 8, 4, 12, 20, 5, 21, 9, 26, 3, 19, 2, 2, 15, 24, 16, 19, 1, 8, 21, 8, 18, 5}

    {1, 25, 3, 14, 5, 26, 16, 11, 6, 26, 4, 17, 7, 26, 10, 16, 8, 18, 23, 23, 22, 8, 18, 4, 25}

    Returns: 2.258626252412796

  31. {7, 22, 11, 1, 27, 16, 23, 5, 17, 21, 9, 24, 20, 2, 3, 10, 14, 27, 5, 3, 25, 26, 7, 11, 8, 24}

    {20, 5, 17, 17, 23, 3, 25, 21, 20, 19, 21, 22, 19, 10, 15, 14, 18, 20, 14, 17, 13, 24, 12, 6, 20, 4}

    Returns: 2.1443023681640625

  32. {9, 5, 19, 22, 16, 28, 17, 2, 6, 12, 25, 8, 9, 14, 15, 19, 8, 17, 26, 20, 22, 26, 27, 12, 20, 17, 13}

    {15, 27, 7, 24, 17, 2, 11, 11, 11, 1, 2, 21, 19, 6, 6, 23, 4, 10, 9, 6, 18, 18, 17, 3, 4, 12, 18}

    Returns: 2.2372300401329994

  33. {11, 20, 18, 7, 11, 10, 22, 10, 27, 6, 19, 24, 14, 28, 19, 20, 27, 10, 28, 28, 17, 29, 26, 25, 7, 20, 4, 19}

    {24, 2, 8, 5, 20, 27, 19, 11, 21, 26, 9, 13, 12, 6, 14, 16, 14, 8, 23, 11, 16, 13, 1, 27, 10, 15, 29, 3}

    Returns: 2.345605120062828

  34. {29, 16, 12, 20, 15, 15, 24, 28, 23, 24, 13, 10, 15, 6, 15, 11, 11, 18, 2, 11, 4, 25, 12, 24, 16, 2, 14, 17, 18}

    {24, 30, 10, 3, 22, 13, 11, 26, 21, 7, 27, 16, 14, 4, 17, 14, 5, 11, 12, 8, 3, 27, 6, 9, 15, 19, 23, 28, 1}

    Returns: 2.445721225813031

  35. {24, 31, 11, 16, 8, 19, 3, 1, 15, 2, 31, 9, 19, 16, 17, 30, 11, 5, 22, 3, 28, 16, 10, 17, 18, 29, 14, 5, 8, 9}

    {21, 1, 27, 9, 6, 11, 28, 4, 11, 18, 22, 23, 21, 12, 25, 20, 28, 14, 15, 29, 13, 7, 15, 12, 9, 26, 20, 15, 21, 14}

    Returns: 2.2745766155421734

  36. {11, 6, 25, 24, 10, 18, 5, 10, 23, 22, 13, 31, 28, 10, 16, 28, 1, 3, 25, 19, 12, 29, 22, 27, 10, 22, 18, 2, 24, 30, 16}

    {24, 9, 7, 21, 22, 16, 28, 32, 7, 24, 15, 22, 16, 14, 9, 20, 10, 9, 10, 3, 18, 14, 15, 18, 4, 8, 17, 18, 26, 24, 25}

    Returns: 3.120025954209268

  37. {30, 6, 25, 17, 21, 10, 22, 8, 4, 25, 22, 14, 22, 31, 10, 5, 30, 18, 4, 33, 15, 33, 28, 17, 2, 31, 12, 12, 33, 14, 30, 21}

    {7, 24, 23, 1, 4, 20, 2, 10, 3, 10, 15, 32, 29, 19, 9, 19, 15, 26, 30, 16, 33, 18, 17, 14, 11, 13, 15, 10, 31, 31, 27, 6}

    Returns: 2.7142070105765015

  38. {6, 1, 5, 26, 13, 27, 17, 31, 30, 17, 7, 11, 4, 33, 25, 18, 12, 32, 12, 11, 18, 25, 20, 21, 27, 27, 24, 9, 29, 12, 12, 10, 24}

    {8, 9, 9, 10, 1, 34, 19, 20, 16, 22, 34, 12, 2, 12, 2, 8, 20, 8, 9, 3, 19, 8, 30, 20, 28, 15, 15, 14, 19, 25, 15, 9, 23}

    Returns: 2.8793265767162666

  39. {34, 24, 28, 24, 20, 30, 5, 31, 30, 30, 14, 16, 30, 3, 8, 1, 22, 23, 3, 26, 13, 10, 34, 31, 8, 35, 1, 28, 12, 22, 2, 9, 25, 25}

    {8, 11, 4, 26, 3, 21, 8, 34, 12, 15, 12, 31, 5, 12, 29, 7, 17, 2, 33, 21, 30, 3, 6, 32, 27, 5, 13, 29, 19, 20, 34, 20, 18, 3}

    Returns: 2.861948890320491

  40. {24, 13, 35, 30, 13, 6, 28, 19, 11, 11, 13, 12, 7, 36, 11, 11, 13, 14, 8, 14, 15, 28, 34, 11, 25, 11, 31, 22, 21, 15, 25, 9, 32, 25, 12}

    {6, 15, 11, 24, 2, 18, 13, 1, 33, 4, 27, 5, 25, 20, 8, 24, 16, 26, 23, 12, 19, 3, 15, 22, 9, 25, 12, 17, 2, 29, 31, 10, 30, 15, 20}

    Returns: 3.363306969840778

  41. {30, 26, 36, 25, 29, 10, 15, 35, 36, 5, 20, 6, 16, 18, 23, 19, 15, 13, 35, 25, 33, 15, 5, 2, 24, 26, 29, 12, 7, 33, 30, 30, 9, 10, 21}

    {29, 31, 6, 35, 14, 15, 1, 32, 26, 34, 26, 22, 2, 3, 17, 30, 29, 10, 4, 21, 27, 3, 28, 23, 2, 2, 25, 33, 15, 30, 23, 34, 14, 8, 11}

    Returns: 2.9625992805231363

  42. {23, 18, 5, 4, 8, 16, 25, 17, 31, 12, 24, 13, 22, 27, 36, 11, 8, 30, 31, 13, 3, 33, 9, 29, 3, 28, 16, 26, 24, 24, 2, 2, 32, 20, 10}

    {19, 3, 10, 28, 16, 15, 16, 28, 36, 8, 35, 21, 21, 18, 6, 20, 19, 20, 14, 3, 34, 9, 35, 2, 26, 36, 28, 7, 3, 19, 13, 1, 8, 26, 25}

    Returns: 2.820357299351599

  43. {36, 7, 26, 8, 7, 11, 10, 11, 8, 12, 2, 21, 13, 10, 6, 11, 3, 19, 12, 5, 11, 33, 16, 13, 22, 34, 11, 18, 29, 30, 30, 22, 31, 25, 27}

    {27, 36, 23, 15, 26, 4, 13, 31, 7, 27, 30, 32, 35, 36, 30, 9, 12, 10, 1, 36, 17, 9, 10, 31, 14, 2, 28, 12, 23, 24, 31, 27, 20, 28, 32}

    Returns: 2.9668708746612538

  44. {1, 29, 34, 17, 13, 22, 18, 5, 35, 14, 10, 33, 23, 27, 13, 14, 32, 32, 18, 15, 33, 2, 9, 35, 8, 21, 12, 22, 33, 1, 24, 17, 7, 29, 23}

    {31, 3, 8, 32, 31, 11, 8, 34, 36, 29, 2, 2, 28, 10, 30, 31, 31, 4, 36, 13, 25, 26, 32, 19, 33, 7, 21, 14, 7, 23, 7, 16, 20, 6, 33}

    Returns: 2.7784599020669702

  45. {27, 26, 9, 18, 29, 7, 20, 8, 3, 31, 17, 28, 13, 1, 10, 25, 26, 26, 32, 2, 21, 18, 31, 6, 32, 28, 17, 16, 33, 9, 14, 33, 24, 20, 33}

    {17, 33, 12, 14, 14, 11, 8, 33, 22, 26, 35, 14, 30, 11, 32, 26, 9, 14, 23, 13, 4, 11, 15, 25, 35, 19, 34, 30, 36, 30, 32, 3, 25, 5, 4}

    Returns: 2.946867458493216

  46. {31, 28, 26, 34, 18, 9, 3, 32, 16, 5, 8, 23, 26, 19, 36, 14, 29, 20, 4, 27, 13, 1, 22, 20, 3, 33, 20, 10, 25, 30, 6, 2, 11, 24, 12}

    {15, 7, 20, 17, 3, 4, 35, 28, 31, 20, 29, 35, 14, 24, 31, 31, 27, 25, 20, 26, 26, 31, 15, 21, 26, 13, 17, 4, 32, 20, 13, 35, 33, 3, 16}

    Returns: 3.2242215727455914

  47. {25, 22, 11, 8, 32, 21, 10, 13, 3, 7, 2, 29, 26, 36, 26, 23, 11, 5, 20, 28, 29, 33, 28, 14, 14, 32, 1, 10, 10, 29, 20, 11, 25, 25, 1}

    {19, 2, 14, 14, 16, 15, 15, 19, 30, 25, 34, 24, 12, 27, 17, 15, 34, 31, 25, 18, 31, 30, 6, 12, 4, 3, 27, 30, 35, 11, 18, 10, 27, 30, 9}

    Returns: 2.773805324686691

  48. {7, 34, 29, 13, 7, 29, 7, 1, 16, 19, 7, 22, 30, 34, 11, 7, 34, 33, 36, 1, 29, 7, 31, 19, 17, 29, 19, 10, 15, 2, 10, 9, 16, 29, 18}

    {17, 22, 26, 10, 14, 12, 23, 22, 32, 10, 22, 25, 23, 27, 10, 29, 24, 10, 20, 18, 19, 16, 1, 21, 8, 35, 36, 6, 29, 7, 28, 26, 4, 3, 5}

    Returns: 3.7409877743630204

  49. {34, 6, 18, 5, 35, 1, 16, 10, 26, 14, 3, 1, 22, 35, 7, 6, 7, 27, 35, 17, 30, 23, 24, 31, 2, 20, 18, 6, 17, 8, 17, 30, 15, 29, 6}

    {25, 36, 13, 18, 32, 28, 8, 31, 27, 7, 31, 34, 6, 1, 24, 12, 21, 18, 17, 7, 16, 9, 19, 36, 17, 17, 8, 9, 4, 7, 33, 11, 17, 30, 7}

    Returns: 3.4246289428847376

  50. {23, 25, 34, 5, 7, 10, 8, 2, 21, 26, 35, 27, 14, 14, 17, 28, 5, 3, 30, 1, 32, 20, 3, 36, 9, 6, 26, 35, 30, 21, 18, 1, 13, 6, 2}

    {25, 13, 10, 16, 20, 36, 25, 29, 5, 10, 18, 25, 9, 11, 18, 21, 3, 19, 35, 26, 14, 1, 24, 33, 22, 26, 31, 25, 12, 32, 11, 15, 4, 18, 18}

    Returns: 2.834601258073235

  51. {27, 16, 29, 31, 36, 25, 21, 30, 22, 28, 11, 23, 32, 14, 23, 36, 18, 20, 9, 28, 2, 30, 27, 12, 4, 34, 33, 13, 13, 21, 7, 6, 25, 3, 10}

    {6, 15, 19, 1, 8, 18, 24, 10, 15, 9, 35, 4, 26, 19, 14, 5, 24, 5, 2, 1, 17, 35, 33, 32, 8, 12, 3, 20, 22, 7, 16, 26, 34, 17, 29}

    Returns: 1.941243119246792

  52. {6, 6, 6, 6, 6, 7, 4, 14, 18, 23, 6, 6, 6, 5, 10, 32, 35, 33, 27, 9, 13, 6, 28, 11, 6, 6, 6, 8, 19, 26, 1, 6, 31, 17}

    {34, 25, 20, 22, 24, 6, 6, 6, 6, 6, 15, 3, 16, 6, 6, 6, 6, 6, 6, 6, 6, 2, 6, 6, 30, 21, 12, 6, 6, 6, 6, 29, 6, 6}

    Returns: 15.000000002095476

  53. {10, 7, 2, 5, 6, 2, 4, 9, 7 }

    {8, 10, 10, 4, 1, 6, 2, 2, 3 }

    Returns: 0.646484375

  54. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 }

    Returns: 1.941243119246792

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: