Statistics

Problem Statement for "DiameterOfRandomTree"

Problem Statement

Given a tree, let d(u,v) be the distance between nodes u and v in the tree. In other words, d(u,v) is the length of the only simple path that connects u and v. The diameter of the tree is the maximum of all d(u,v).

You are given int[]s a and b, each containing n-1 elements. These describe a tree with n nodes, labeled 0 through n-1. For each valid i, the nodes a[i] and b[i] are connected by an edge.

The length of each edge is generated randomly. More precisely, the length of each edge is either 1 or 2 with equal probability. The lengths of edges are mutually independent.

Return the expected value of the diameter of the given tree.

Definition

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

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • a and b will contain the same number of elements.
  • Each element in a will be between 0 and |a|, inclusive.
  • Each element in b will be between 0 and |a|, inclusive.
  • The graph will be a tree.

Examples

  1. {0,1,2,3}

    {1,2,3,4}

    Returns: 6.0

    This graph is a single path: 0-1-2-3-4. In this case, the diameter will always be the distance between nodes 0 and 4. The expected length of each edge is 1.5, thus the expected distance between 0 and 4 equals 4 * 1.5 = 6.

  2. {0,0,0}

    {1,2,3}

    Returns: 3.375

    This tree has three edges: 0-1, 0-2, and 0-3. There are four possible cases: With probability 1/8 all three edges have length 1. In this case, the diameter is 2. With probability 3/8 the edges have lengths (1,1,2). In this case, the diameter is 3. With probability 3/8 the edges have lengths (1,2,2). In this case, the diameter is 4. With probability 1/8 all three edges have length 2. In this case, the diameter is also 4. Thus, the expected diameter is (1/8)*2 + (3/8)*3 + (3/8)*4 + (1/8)*4 = 27/8 = 3.375.

  3. {0,0,0,1,4}

    {1,2,3,4,5}

    Returns: 6.25

  4. {0,0,0,0,0,0,0,0}

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

    Returns: 3.9609375

  5. {0,0,0,1,2,3,5,6,8}

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

    Returns: 10.53125

  6. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,1,1,5,5,7,8,10,6,9,8,4,4,9,14,9,0,4,0,14,2,2,3,18,27,2,22,13,31,27,18,32,16,14,19,34,39,20,38,34,17,0,36,7,10,37}

    Returns: 19.064013742958196

  7. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,1,5,5,3,6,8,10,10,10,12,14,13,13,13,18,16,19,19,21,20,21,25,24,27,28,28,26,29,32,29,32,35,35,37,37,39,39,37,38,39,40,43,46,44,46}

    Returns: 31.85546875

  8. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,3,3,5,7,4,7,8,8,9,12,12,15,13,14,18,18,17,19,20,19,22,21,26,23,25,25,29,30,28,30,31,34,36,33,37,36,39,41,41,40,43,41,42,43,45}

    Returns: 39.03125

  9. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,0,3,4,3,6,3,7,7,8,11,9,11,13,14,12,14,14,17,18,18,20,23,22,23,26,25,24,29,27,28,29,33,34,35,33,35,38,35,40,37,38,39,42,42,44,47,46}

    Returns: 31.694534301757812

  10. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,1,2,4,6,7,8,7,8,9,11,11,14,15,12,16,14,15,20,21,18,20,21,23,22,24,27,25,29,30,32,33,34,34,35,36,35,39,39,37,40,40,44,42,44,46,47}

    Returns: 34.861328125

  11. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,1,2,5,5,6,6,6,8,11,9,13,13,13,15,14,14,15,16,18,22,19,20,24,25,25,24,25,28,31,31,31,31,31,35,36,38,37,39,39,38,39,40,43,43,43,48}

    Returns: 24.5585880279541

  12. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,3,5,3,7,4,8,10,10,8,11,12,15,13,16,17,17,18,18,22,19,22,23,25,25,25,29,29,30,32,29,30,31,35,36,34,39,40,40,38,42,41,44,42,43,47}

    Returns: 29.115081787109375

  13. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,1,2,5,4,6,8,8,10,10,9,12,10,15,14,16,17,17,19,21,19,21,24,25,25,25,26,25,30,29,28,29,31,31,36,36,36,35,38,37,41,40,42,45,42,43,44}

    Returns: 33.5819091796875

  14. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,3,4,2,3,5,8,6,6,11,11,13,10,14,15,14,15,16,18,21,21,20,23,22,22,24,27,26,30,29,29,33,34,33,34,34,35,35,36,39,40,43,43,44,46,45,44}

    Returns: 33.03125

  15. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,4,2,3,3,7,7,8,7,12,9,11,11,16,14,16,19,17,20,18,19,24,22,22,26,28,29,29,30,29,29,34,33,36,33,37,37,39,40,41,39,40,45,44,43,47}

    Returns: 32.1005859375

  16. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,3,0,2,4,6,6,6,9,7,11,13,13,12,14,17,14,19,16,20,18,21,22,21,26,27,26,29,26,30,28,31,34,34,33,35,35,37,39,38,38,39,44,43,45,47,45}

    Returns: 36.07591247558594

  17. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,2,3,4,2,5,8,8,10,9,8,9,10,14,13,15,15,17,19,21,22,21,24,21,24,26,27,25,30,29,29,31,32,32,33,34,38,37,38,37,39,42,43,42,42,44,48}

    Returns: 28.17037173639983

  18. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,1,4,5,6,3,6,9,7,11,11,13,14,14,13,14,15,19,16,17,19,23,24,24,23,27,26,26,30,31,32,29,30,34,36,36,37,37,38,37,42,43,41,42,46,43,47}

    Returns: 33.04931640625

  19. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,2,4,5,6,3,8,7,6,7,8,13,12,15,12,16,15,17,20,21,21,22,24,22,26,23,24,27,26,27,28,32,31,35,34,34,34,38,37,38,38,41,40,41,43,44,44}

    Returns: 33.3193359375

  20. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,0,2,3,2,7,6,8,9,11,11,12,12,14,12,17,15,16,20,21,20,21,22,25,24,25,27,26,29,31,29,29,33,33,34,37,34,35,38,39,39,42,44,43,42,47,48}

    Returns: 34.5341796875

  21. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,0,3,3,5,3,7,8,5,7,8,9,9,13,13,15,13,15,17,20,19,21,23,20,24,22,27,27,26,26,28,31,32,34,34,35,35,34,38,36,41,41,39,43,41,45,44,45}

    Returns: 29.553840675427637

  22. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,1,4,2,6,7,5,8,9,10,10,12,10,14,13,14,14,17,17,20,21,23,23,23,25,26,28,27,30,29,31,32,32,32,32,35,36,36,36,41,42,43,43,45,45,45,44}

    Returns: 35.0625

  23. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,2,3,5,4,6,8,6,8,11,11,9,11,15,16,16,16,16,17,21,19,21,20,22,24,27,24,26,30,30,29,30,34,34,34,36,35,38,37,41,40,42,43,44,42,45,48}

    Returns: 33.397705078125

  24. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,2,3,3,5,3,7,8,8,9,11,11,10,14,12,14,17,16,20,17,20,21,21,23,26,23,27,27,26,29,32,33,34,34,34,34,36,36,39,39,42,42,41,41,46,46,46}

    Returns: 35.13671875

  25. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,0,3,2,5,5,7,6,5,10,11,10,11,10,12,14,16,16,19,20,20,21,20,20,21,26,25,28,27,30,30,31,31,32,31,36,36,36,35,39,41,40,43,42,44,45,46,46}

    Returns: 32.358154296875

  26. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,0,2,4,4,3,5,4,9,10,9,11,10,13,12,16,16,17,15,20,18,22,21,23,22,24,24,25,28,30,31,31,29,34,33,35,36,34,39,37,37,38,39,42,42,44,43,45}

    Returns: 42.00390625

  27. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,3,4,3,6,6,7,8,9,8,12,13,11,13,12,15,15,19,16,19,18,20,23,25,23,26,25,28,29,28,28,32,32,33,32,37,34,38,38,41,40,41,44,45,44,47,48}

    Returns: 33.14306640625

  28. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,3,1,3,2,4,7,9,8,9,10,12,10,12,12,15,16,15,17,20,21,19,24,24,26,25,25,29,27,31,29,33,34,34,36,36,34,36,37,37,38,43,41,41,42,44,48}

    Returns: 31.5087890625

  29. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,1,1,3,6,6,6,8,6,10,9,9,13,14,13,13,15,15,17,21,19,23,20,24,26,27,27,25,30,31,32,29,34,32,33,33,35,37,39,41,41,43,43,44,46,46,44}

    Returns: 33.48735046386719

  30. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,0,3,2,0,5,7,0,6,10,9,10,2,2,12,12,9,12,14,1,15,9,1,12,22,0,3,14,22,25,5,20,6,34,10,34,6,31,16,12,1,17,40,44,4,5,18,25}

    Returns: 17.353615403175354

  31. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,0,1,4,6,4,9,1,10,6,12,6,10,7,12,2,14,12,7,16,15,21,9,2,19,28,9,2,11,7,14,34,35,25,2,33,17,33,35,4,26,29,38,8,9,24}

    Returns: 19.9248046875

  32. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,1,0,5,3,7,4,9,0,7,1,7,1,2,7,16,12,6,16,2,19,5,2,1,3,0,15,8,23,26,2,1,5,24,5,26,7,16,1,5,24,32,30,26,40,25,39}

    Returns: 15.890603065490723

  33. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,1,0,4,5,7,1,8,9,10,10,0,12,4,9,12,16,12,19,4,17,12,23,1,15,19,23,29,18,22,0,16,30,12,18,5,9,31,40,14,0,41,11,19,42,39,34}

    Returns: 25.524169921875

  34. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,0,3,2,3,5,9,6,5,5,2,5,5,2,17,2,19,1,15,13,14,3,5,16,26,7,13,21,4,2,21,25,25,15,18,2,36,3,0,23,12,43,23,18,29,8}

    Returns: 15.390166115015745

  35. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,0,1,3,5,5,0,6,3,7,3,11,3,11,11,3,9,0,7,12,5,2,18,16,3,5,23,23,5,19,30,13,16,15,19,30,11,36,5,39,5,3,32,44,45,36,31,42}

    Returns: 17.44786513224244

  36. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,0,0,2,4,2,0,5,0,6,10,11,4,10,8,11,7,5,14,8,8,19,7,6,9,17,8,3,27,16,27,1,6,27,17,23,1,2,18,19,3,0,0,12,23,2,3,40}

    Returns: 17.54998779296875

  37. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,0,1,2,0,5,3,8,9,9,1,2,2,13,6,13,1,12,19,17,2,15,0,13,1,22,2,14,20,9,4,4,28,19,11,31,9,0,15,24,40,30,42,10,10,24,19,27}

    Returns: 18.463939487934113

  38. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,3,1,1,4,1,1,8,8,11,0,5,13,0,14,2,3,15,6,0,15,11,6,3,2,17,23,28,26,12,29,1,13,15,4,6,33,16,19,22,39,33,16,3,16,27,0}

    Returns: 19.626541063189507

  39. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,0,3,2,6,4,2,8,4,1,12,6,13,9,1,7,12,2,11,3,5,12,4,4,23,19,7,21,23,22,2,30,15,33,34,34,7,9,11,14,38,42,25,25,6,5,29}

    Returns: 20.062194347381592

  40. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,1,0,5,4,6,3,3,1,3,7,9,7,11,0,2,11,7,14,3,4,17,13,6,7,2,25,10,6,30,7,29,24,4,19,26,14,3,29,30,36,19,21,4,28,41,32}

    Returns: 21.548828125

  41. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,3,1,1,0,1,6,8,10,11,11,3,11,5,15,1,5,17,16,18,17,9,13,9,15,11,18,3,7,10,29,8,27,15,10,13,30,32,17,36,38,24,22,37,25,40,39}

    Returns: 17.55424104630947

  42. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,4,2,3,6,7,8,1,10,4,4,13,7,1,12,18,5,0,6,16,20,2,6,22,17,4,10,21,8,3,25,14,23,20,15,31,35,32,27,12,10,43,11,45,9,47}

    Returns: 23.479507446289062

  43. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,2,2,0,5,0,9,7,0,2,13,14,7,0,17,18,6,5,11,20,13,3,6,3,11,18,5,4,3,14,18,23,30,31,0,20,10,13,18,40,7,35,5,17,9,47}

    Returns: 16.63067626953125

  44. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,2,2,1,3,6,4,3,7,9,10,1,11,15,16,10,5,7,10,6,1,1,23,10,14,3,17,3,9,15,15,24,18,35,7,15,3,35,19,28,39,2,24,26,45,31,29}

    Returns: 21.07140827178955

  45. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,2,1,0,2,1,7,5,1,0,11,9,3,5,8,2,13,13,4,4,6,1,9,20,22,3,9,18,17,14,22,2,21,13,30,31,35,5,28,31,33,0,43,22,15,7,22,40}

    Returns: 16.157472576829605

  46. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,0,2,3,0,0,3,5,8,1,11,6,10,10,9,14,13,17,14,5,9,0,22,1,4,11,7,29,17,8,11,25,31,23,30,21,25,19,7,38,8,41,35,21,4,8,32}

    Returns: 19.380965096643195

  47. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,0,1,4,3,1,0,0,9,3,5,0,5,0,1,15,9,17,4,2,7,12,8,8,17,10,22,2,15,24,29,28,19,0,28,30,9,4,26,1,28,0,28,0,7,25,31,48}

    Returns: 15.9572750069201

  48. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,0,1,2,3,6,2,5,0,5,3,5,8,9,9,9,9,4,17,15,6,15,20,23,3,8,9,9,6,19,14,2,9,17,0,25,33,30,23,39,6,42,41,0,20,31,32,2}

    Returns: 19.76411247253418

  49. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,0,2,2,0,5,3,2,4,9,11,1,9,8,10,8,11,4,6,20,2,7,11,10,6,16,25,2,29,7,7,13,7,18,7,20,19,20,26,8,7,0,25,16,45,2,4,28}

    Returns: 15.113700901070843

  50. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  51. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  52. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  53. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  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,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  55. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  56. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  57. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  58. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  59. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  60. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  61. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  62. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  63. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  64. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  65. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  66. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  67. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  68. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  69. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,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,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: 73.50000000000007

  70. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,2,4,5,6,6,7,8,9,10,11,12,13,15,16,16,17,19,20,20,22,23,23,25,26,26,28,29,30,30,31,33,33,35,35,37,37,39,40,40,41,43,43,44,46,46,47}

    Returns: 49.8251953125

  71. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,3,3,5,5,7,7,9,10,11,11,12,14,14,16,16,18,18,20,21,21,22,24,25,26,26,28,29,30,30,32,32,34,34,35,37,37,38,40,41,41,42,43,45,46,47,48}

    Returns: 51.0

  72. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,2,4,4,6,6,7,9,9,10,12,12,13,14,15,16,17,19,20,21,21,23,23,25,26,26,28,28,30,30,31,32,34,35,36,37,38,39,40,41,42,42,44,45,45,47,48}

    Returns: 51.25

  73. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,3,5,6,6,8,8,9,11,12,12,13,15,15,17,18,18,20,20,21,22,24,24,25,27,27,28,29,31,31,32,33,35,35,37,38,38,40,41,41,43,43,45,45,46,48}

    Returns: 46.5

  74. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,3,4,5,5,6,8,9,10,11,11,13,13,15,15,17,18,18,20,21,22,23,24,24,26,27,28,28,29,31,31,33,34,34,36,36,37,38,39,40,42,42,43,44,46,47,48}

    Returns: 51.25

  75. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,3,3,5,6,7,8,8,9,10,11,13,14,14,16,17,17,18,20,20,21,22,24,25,25,26,28,29,30,30,31,32,33,35,35,36,37,38,40,41,42,42,44,44,45,47,47}

    Returns: 50.0

  76. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,3,3,5,6,6,7,9,10,10,11,13,14,15,16,17,18,18,19,21,21,23,23,24,25,26,27,28,30,31,31,32,34,34,36,37,37,38,39,41,42,42,43,45,45,47,47}

    Returns: 51.25

  77. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,4,5,6,7,7,9,10,11,11,13,13,14,15,16,18,19,19,20,21,22,24,24,26,26,27,28,29,31,32,33,34,35,36,37,38,39,39,41,41,43,44,44,46,46,48}

    Returns: 52.5

  78. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,3,4,4,5,7,8,8,10,11,11,13,14,15,16,16,18,18,20,21,22,22,23,25,26,27,27,29,29,30,31,33,33,34,36,37,38,38,40,40,42,42,43,44,46,46,47}

    Returns: 51.0

  79. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,4,5,5,7,7,9,9,11,11,12,14,15,15,16,17,19,20,20,21,22,24,25,26,26,28,29,30,30,32,33,33,34,36,37,38,38,40,41,41,43,44,45,45,47,48}

    Returns: 51.0

  80. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,2,3,5,6,7,8,9,10,11,12,13,14,14,16,16,18,18,20,20,21,23,24,24,26,27,27,28,30,30,31,33,33,35,35,36,38,39,40,41,41,43,43,45,46,46,48}

    Returns: 55.5

  81. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,4,4,5,7,8,8,9,10,11,13,13,14,15,17,18,19,19,20,21,22,24,25,25,26,27,28,29,31,32,32,33,35,35,36,37,39,40,41,41,43,43,45,46,47,47}

    Returns: 49.75

  82. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,3,4,6,7,7,8,9,10,12,13,14,15,16,17,18,18,20,20,21,23,23,24,26,26,27,29,29,30,32,32,34,34,36,37,38,38,39,41,42,42,43,45,45,46,47}

    Returns: 51.75

  83. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,2,4,4,6,7,8,8,10,11,12,13,13,14,15,16,18,19,20,20,22,23,24,25,26,27,27,28,30,31,31,33,33,34,36,36,37,39,40,41,41,42,43,44,46,47,48}

    Returns: 55.5

  84. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,3,3,4,5,7,7,9,9,11,11,12,13,14,15,16,17,18,20,21,21,22,24,24,26,26,27,29,29,31,32,33,34,34,36,37,37,38,40,40,42,43,43,44,46,46,47}

    Returns: 48.0316162109375

  85. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,2,3,4,5,6,6,7,9,9,10,12,13,13,14,16,16,18,18,20,21,21,23,24,24,25,26,27,28,30,31,32,33,34,34,36,36,37,39,40,41,42,42,44,45,46,47,48}

    Returns: 55.5

  86. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,0,1,3,4,4,5,6,7,8,9,11,12,13,14,15,15,16,18,18,20,21,21,22,23,25,25,26,28,29,29,30,31,33,34,35,36,36,37,39,40,40,41,42,44,45,46,46,48}

    Returns: 52.5703125

  87. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,2,3,5,6,7,7,9,9,11,11,13,14,15,16,17,18,18,19,20,21,22,24,24,25,26,27,28,29,30,31,32,33,35,36,37,38,39,39,40,42,43,43,44,46,46,47}

    Returns: 51.0

  88. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,3,4,5,5,7,8,8,9,10,11,13,13,15,15,17,18,18,20,20,22,22,24,24,25,26,28,28,30,31,31,33,33,34,36,36,38,38,40,41,41,43,44,44,45,47,48}

    Returns: 46.75

  89. {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,37,38,39,40,41,42,43,44,45,46,47,48,49}

    {0,1,1,2,3,5,6,7,8,8,10,11,11,13,14,14,15,16,17,18,19,21,22,23,23,25,26,26,27,28,30,30,31,33,33,34,35,36,38,38,40,40,42,42,44,44,45,46,48}

    Returns: 48.03125

  90. {0, 2, 1, 3, 5, 7, 8, 6, 9, 4, 10, 12, 14, 13, 15, 17, 19, 20, 18, 21, 16, 22, 11, 23, 25, 27, 26, 28, 30, 32, 33, 31, 34, 29, 35, 37, 39, 38, 40, 42, 44, 45, 43, 46, 41, 47, 36, 48, 24, 49 }

    {1, 3, 4, 4, 6, 9, 9, 10, 10, 11, 11, 13, 15, 16, 16, 18, 21, 21, 22, 22, 23, 23, 24, 24, 26, 28, 29, 29, 31, 34, 34, 35, 35, 36, 36, 38, 40, 41, 41, 43, 46, 46, 47, 47, 48, 48, 49, 49, 50, 50 }

    Returns: 17.546173395027957

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: