Statistics

Problem Statement for "Ethernet"

Problem Statement

You have N computers numbered 0 through N-1. They are connected into a single network. The topology of the network is a tree. You are given its description as int[]s parent and dist. Each of the int[]s contains exactly N-1 elements. For each i between 0 and N-2, inclusive, there is a cable connecting computers i+1 and parent[i], and the length of that cable is dist[i].

You are also given an int maxDist with the following meaning: The distance between any two computers in the same network must not exceed maxDist. (The distance between two computers is defined as the total length of cable between them.) If this is currently not the case for your network, you have to divide it into several smaller networks.

Formally, it means that you need to choose the number K of smaller networks you will have. Then you need to assign each of your computers into exactly one of the K networks. The following properties must be satisfied:
  • Each of the K new networks must form a connected subtree of the original tree.
  • The diameter of each new network must be at most maxDist.
Return the smallest value of K for which it is possible to divide the original network into K new networks with the above properties.

Definition

Class:
Ethernet
Method:
connect
Parameters:
int[], int[], int
Returns:
int
Method signature:
int connect(int[] parent, int[] dist, int maxDist)
(be sure your method is public)

Constraints

  • parent will contain between 1 and 50 elements, inclusive.
  • dist will contain the same number of elements as parent.
  • For each valid i, the i-th element of parent will be between 0 and i, inclusive.
  • Each element of dist will be between 1 and 500, inclusive.
  • maxDist will be between 1 and 500, inclusive.

Examples

  1. {0,0,0}

    {1,1,1}

    2

    Returns: 1

    The diameter of this network is 2, which is small enough.

  2. {0,0,0,0,0,0,0}

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

    8

    Returns: 4

    One optimal solution: the new networks will be formed by computers {4}, {6}, {7}, and {0,1,2,3,5}.

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

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

    6

    Returns: 3

    One optimal solution is to put computers {0,1,2,3} into the first new network, {4,5} into the second one, and {6} will be the third network.

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

    {1,1,1,1,1}

    2

    Returns: 2

    The two new networks can be {0,2,3} and {1,4,5}.

  5. {0}

    {1}

    1

    Returns: 1

  6. {0}

    {2}

    1

    Returns: 2

  7. {0,1,1,2,3,4,6,1,2,1,8,1,10,13,2,11,13,9,12,2,6,6,8,21,16,10,23,15,5,11,6,13,13,31,14,7,15,13,21,2,34,33,20,5}

    {12,254,219,348,345,113,208,88,260,324,292,230,79,67,236,141,93,289,7,291,193,15,249,147,6,141,80,221,301,307,302,244,49,30,24,285,5,207,291,67,27,282,59,145}

    468

    Returns: 13

  8. {0,0,2,2,4,5,3,3,4,8,0,6,2,10,8,2,6,17,1,12,12,21,5,21,22,2,10,18,26,6,4,31,27,2,6,28,7,10,15,4,26,28}

    {28,72,8,58,98,48,34,64,66,30,50,39,102,109,63,107,27,71,94,9,61,72,43,96,11,120,25,18,69,4,116,82,3,111,92,117,15,101,37,22,109,40}

    127

    Returns: 21

  9. {0,1,1,2,3,0,1,7,8,8,10,0,6,13,6,6,4,7,14,9,14,15,17,8,24,9,20,6,27,14,3,20,5,29,12,27,24,15,30}

    {60,92,75,120,105,41,131,91,45,77,111,50,6,127,130,94,73,95,43,53,55,108,103,10,71,72,96,41,117,88,19,51,65,64,65,71,115,127,108}

    485

    Returns: 6

  10. {0,0,2,2,2,3,4,3,2,6,7,5,5,2,5,14,8,13,1,8}

    {40,96,60,180,25,106,79,68,103,249,60,178,139,17,240,59,46,160,65,152}

    370

    Returns: 7

  11. {0,0,1,1,2,1,0,6,0,9,4,7,9,13,4,5,12,12,10}

    {92,42,34,17,33,92,9,65,12,31,61,74,3,68,75,24,30,80,76}

    193

    Returns: 5

  12. {0,1,2,0,1,4,0,6,4,4,8,2,5,5,0,2,4,8,17,19,0,17,3,8,4,0,20,13,20,3,10,22,23,10,27,5,13,19,23,25}

    {128,165,135,155,95,35,63,100,104,21,8,78,39,18,94,141,64,119,23,46,43,151,144,148,43,20,98,76,14,55,144,53,142,72,64,63,166,54,116,112}

    413

    Returns: 8

  13. {0,0,1,3,0,3,6,6,1,5,0,7,7,10,2,5,4,14,14,15,15,13,9,8,19,12,4,11,20,28,25,11,8,32,9,23,27,26,30,20,40,22,27,6,20,8,6}

    {56,79,37,88,107,77,82,86,94,57,34,32,122,15,152,9,99,59,124,135,12,140,152,126,131,161,47,17,9,77,14,154,94,114,94,137,145,21,57,56,81,116,33,60,121,56,5}

    143

    Returns: 22

  14. {0,0,0,3,3,4,2,4,6,8,4,7,2}

    {279,205,154,223,61,101,7,224,193,65,281,133,245}

    366

    Returns: 7

  15. {0,0,0,2,2,3,3,5,3,6}

    {91,94,109,30,153,118,130,24,218,74}

    486

    Returns: 2

  16. {0,1,2,2,4,4,4,4}

    {26,82,37,76,24,52,152,84}

    60

    Returns: 6

  17. {0,1,2,2,1,1,1,3,5,1,6,6,6,1,13,10,7,13,15,13,8,9,15,12,18,10,1,18,21,11,21,13,9,33,5,2,29,23}

    {176,195,73,87,118,213,60,45,32,162,81,205,135,66,177,29,232,80,32,49,71,126,51,220,210,49,152,76,37,88,85,149,73,98,192,7,228,37}

    349

    Returns: 13

  18. {0,0,0,1,4,0,4,3,5,1,4,4,6,12,6,13,2,7,5,12,15,13,1,15,20,12,1,24,12,6,29,10,17,13,19,35,20,15,12,3}

    {22,53,18,61,45,91,45,7,17,39,4,42,44,57,27,25,1,10,91,37,51,14,43,89,88,67,33,29,74,95,53,12,36,48,10,88,38,58,16,57}

    4

    Returns: 39

  19. {0,0,1,0,2,4,6,5,3,3,7,8,7,1,0,12,4,3,17,3,16,13,13,9,6,2,2,20,15,11,22,2,32,2,25,29,4,36,36,28,7,0,14,39,6,5,35,13,2}

    {149,413,328,378,308,59,259,46,315,351,278,152,334,330,398,125,267,144,73,339,408,22,381,99,223,365,405,123,188,148,29,316,179,419,206,274,378,275,253,174,143,31,163,263,81,167,35,78,142}

    371

    Returns: 25

  20. {0,1,0,2,0,0,6,2,3,3,10,0,7,10,3,14,0,2,7,16,1,14,12,13,9,4,13,24,3,28}

    {27,132,100,19,46,135,76,114,119,20,154,1,51,102,29,65,13,148,136,120,29,86,67,136,102,128,78,80,17,73}

    231

    Returns: 11

  21. {0,0,1,1,0,3,4,4,7,9,3,3,10,3,9,10,12,3,6,17,3,3,18,18,14,0,20,26,11,5,2,4,24,16,30,31,29,27,2,30,27,15,14,41,42,10,19,1}

    {13,90,83,92,148,29,93,95,61,176,50,147,52,114,20,42,16,141,18,89,126,91,151,46,2,199,93,121,10,148,101,160,113,46,42,55,85,173,187,107,120,142,177,117,179,106,35,34}

    314

    Returns: 12

  22. {0,1,0,1,0,4,3,3,0,8,1,10,5,3,6,4,5,8,3}

    {165,70,197,246,124,67,318,325,161,109,249,192,208,22,185,15,294,268,140}

    310

    Returns: 10

  23. {0,0,2,2,1,1,4,6,1,2,2,2,10,12,2,13,15,9,8,2,0,6,0,12,0,24,9,12,3,22,13,27,21,24,12,16,8,30}

    {17,26,34,27,120,79,6,95,89,128,84,92,61,65,105,90,88,84,30,43,23,114,16,39,112,38,28,130,123,101,53,106,84,122,22,60,18,100}

    53

    Returns: 28

  24. {0,1,0,3,0,5,0,6,0,6,0,6,4,6,9,4,5,5,2,5,2}

    {93,42,104,105,59,73,161,130,30,81,62,93,131,133,139,5,13,34,25,111,4}

    162

    Returns: 11

  25. {0,1,0,1,0,4,6,7,8,4,3,9,6,13,0,15,2,1,13,12,13,12,18,12,1,14,0,2,21,10,23,22,14,25}

    {11,53,132,107,34,77,64,123,107,93,66,69,63,124,56,58,5,41,70,16,54,28,13,3,22,36,77,23,32,128,99,115,131,136}

    112

    Returns: 16

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

    {197,184,9,283,147,25,180,415,31,263,148,145,217,32,86,358,11}

    320

    Returns: 8

  27. {0,0,0,3,1,1,0,7,5,1,5,8,9,9,8,9,5,3,9,17,4,17,7,18,3,5,25,9,27,14,28,9,9,3,3,29,23,12,29,30,14,8,17,17,30,12,29,37,28,23}

    {3,4,5,1,5,3,3,1,3,4,2,3,1,4,2,4,4,1,4,2,3,1,3,4,5,2,4,4,3,1,4,2,3,1,5,4,4,2,4,2,3,4,5,1,1,1,2,2,4,1}

    5

    Returns: 25

  28. {0,0,0,0,3,2,4,7,1,9,1,4,2,6,12,9,15,14,15,12,13,8,13,8,14,13,23,13,4,21,3,4,12,14,3,15,17,19,17,0,10,36,26,35,5,38,6,0,8,37}

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

    6

    Returns: 22

  29. {0,1,2,1,1,2,6,3,0,2,9,5,1,9,12,12,7,5,17,19,18,16,21,8,12,6,4,17,12,0,24,2,4,21,13,9,21,33,3,36,16,14,34,22,37,8,1,17,22,45}

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

    7

    Returns: 28

  30. {0,1,2,2,3,4,5,3,6,0,0,1,11,3,3,9,12,2,8,12,13,21,2,10,10,13,22,3,6,29,28,10,1,33,23,34,2,33,3,22,32,2,15,4,4,30,19,17,37,3}

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

    8

    Returns: 24

  31. {0,1,2,1,1,0,1,5,3,0,6,9,2,2,14,8,11,5,6,13,7,2,20,22,21,18,21,9,19,24,29,4,13,32,34,34,9,25,12,4,25,14,42,41,38,10,18,25,31,49}

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

    9

    Returns: 23

  32. {0,0,1,3,4,1,1,6,1,5,6,8,1,3,13,1,1,10,16,12}

    {83,335,29,61,176,145,147,52,114,20,42,16,141,18,89,126,91,2,266,46}

    314

    Returns: 6

  33. {0,1,1}

    {1,1,1}

    2

    Returns: 1

  34. {0, 1, 2, 0, 0, 2, 6, 0, 1, 1, 10, 10, 8, 0, 9, 13, 3, 12, 7, 19, 17, 21, 1, 21, 24, 9, 26, 8, 5, 26, 8, 19, 4, 18, 32, 11, 32, 22, 18, 22, 40, 1, 33, 34, 12, 2, 22, 30, 33 }

    {58, 4, 15, 84, 22, 82, 87, 4, 18, 99, 76, 73, 17, 25, 44, 65, 42, 78, 63, 75, 63, 76, 94, 14, 12, 50, 5, 35, 86, 70, 47, 10, 14, 98, 13, 24, 93, 60, 99, 50, 92, 58, 6, 70, 83, 85, 89, 95, 28 }

    500

    Returns: 4

  35. {0, 1, 0, 3, 0, 5, 0, 6, 0, 6, 0, 6, 4, 6, 9, 4, 5, 5, 2, 5, 2 }

    {93, 42, 104, 105, 59, 73, 161, 130, 30, 81, 62, 93, 131, 133, 139, 5, 13, 34, 25, 111, 4 }

    162

    Returns: 11

  36. {0, 1, 1, 3, 4, 0, 2, 5, 7, 9, 2, 8, 6, 10, 0, 9, 3, 17, 6, 6, 17, 1, 4, 17, 10, 12, 19, 27, 16, 22, 11, 26, 11, 15, 6, 27, 8, 13, 18, 1, 20, 13, 21, 28, 24, 15, 21, 19, 15, 39 }

    {52, 247, 443, 240, 93, 469, 370, 16, 443, 7, 25, 299, 412, 163, 199, 71, 476, 455, 217, 90, 343, 427, 220, 342, 84, 239, 496, 375, 101, 258, 449, 377, 40, 428, 238, 455, 17, 153, 433, 268, 457, 307, 456, 378, 477, 368, 499, 382, 41, 326 }

    264

    Returns: 36

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

    {253, 104, 359, 161, 478, 194, 397, 73, 114, 293, 113, 461, 494, 112, 371, 172, 382 }

    289

    Returns: 12

  38. {0, 1, 1, 3, 1, 1, 1, 6, 5, 8, 9, 10, 1, 10, 3, 1, 7, 11, 10, 1, 15, 4, 4, 12, 10, 5 }

    {461, 68, 403, 276, 258, 272, 266, 259, 224, 336, 241, 54, 18, 325, 395, 449, 425, 56, 350, 378, 211, 83, 184, 290, 59, 445 }

    345

    Returns: 16

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: