Statistics

Problem Statement for "FanFailure"

Problem Statement

In a robust computer system, one of the most important pieces is the cooling. Without proper cooling, processors can heat up to over 400 degrees C. The reliability of a system can be measured by determining how many fans can fail without risking the system processor. Each fan can be assigned a value indicating how much capacity it has to cool the system, and we can define a minimum cooling capacity, which the sum of the fan capacities must exceed or equal to properly cool the system. We define a Failure Set as a set of fans which are not necessary to cool the system. In other words, if the fans in a Failure Set break, the system can still be properly cooled by the remaining fans. The count of a Failure Set is the number of fans in the set.

To measure the reliability, we will define two values, the Maximum Failure Set (MFS) and the Maximum Failure Count (MFC). A MFS is a Failure Set of fans with the largest count possible. A set of fans may have more than one MFS (see below). A Failure Set is an MFS if and only if there are no Failure Sets with a higher count. The MFC is the largest value such that all fan sets with count <= MFC are Failure Sets. In other words, any set of fans of size MFC or less can fail, and the system will still be properly cooled by the remaining fans.

Consider the fan set with capacities 1, 2, 3, and a cooling requirement of 2. Two MFSs with a count of 2 exist: fans 1 and 3, or fans 1 and 2. However, the MFC is not 2 because fans 2 and 3 is not a Failure set (fan 1 could not cool the system properly by itself). Thus, the MFC is 1, because if any single fan fails, the system can still be cooled.

You will be given a int[] capacities, which designates how many units of cooling each fan provides, and an int minCooling, which designates the minimum units of cooling required to cool the system. Your method should return a int[], where the first value should be the number of fans in the Maximum Failure Set (MFS), and the second value should be the Maximum Failure Count (MFC).

Definition

Class:
FanFailure
Method:
getRange
Parameters:
int[], int
Returns:
int[]
Method signature:
int[] getRange(int[] capacities, int minCooling)
(be sure your method is public)

Constraints

  • capacities has between 1 and 50 elements, inclusive.
  • each element of capacities is between 1 and 1000, inclusive.
  • minCooling is between 1 and 49999, inclusive.
  • The sum of all elements in capacities will be greater than minCooling.
  • Due to a contradiction in the original problem statement, it was not clear whether having enough fans to equal exactly minCooling was enough to cool the system. For this reason, test cases where this anomaly changes the answer will be rejected.

Examples

  1. {1,2,3}

    2

    Returns: { 2, 1 }

    Example from the problem statement.

  2. {8,5,6,7}

    22

    Returns: { 0, 0 }

    No fans can fail in this system.

  3. {676, 11, 223, 413, 823, 122, 547, 187, 28}

    1000

    Returns: { 7, 2 }

    If you eliminate fans with 676, 11, 413, 122, 547, 187, and 28, you are left with 223 + 823 = 1046 units of cooling, which is sufficient, yielding an MFS size of 7. If you eliminate 676, 823, and 547, you are left with only 984 units of cooling. All combinations of 2 or less fans breaking leaves sufficient cooling, so the MFC is 2.

  4. {1000,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,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    50

    Returns: { 49, 0 }

  5. {460, 191, 332, 693, 617, 837, 468, 983, 909, 214, 112, 586}

    2278

    Returns: { 9, 5 }

  6. {521, 16, 655, 906, 653, 957, 625, 842, 792, 15, 739}

    6313

    Returns: { 2, 0 }

  7. {516}

    241

    Returns: { 0, 0 }

  8. {89, 886, 545, 819, 567, 586, 340, 824, 148, 384, 845, 523, 259, 727, 520, 980, 426, 494, 533, 736}

    7586

    Returns: { 9, 4 }

  9. {229, 102, 817, 103, 486, 65, 543, 360, 289, 397, 995, 896, 347, 201, 733, 90, 966, 39, 843, 49, 851, 668, 904, 741, 500, 287, 463, 45, 639, 753}

    8219

    Returns: { 20, 6 }

  10. {120, 33, 225, 827, 144, 542, 592, 152, 998, 428, 235, 281, 192, 822, 733, 559, 705, 709, 78, 213, 614, 660, 504, 524, 880, 286, 304, 467, 546, 803, 939, 339, 369}

    5123

    Returns: { 27, 14 }

  11. {736, 678, 982, 498, 809, 32, 89, 324, 642, 354, 531, 624, 859}

    5733

    Returns: { 5, 1 }

  12. {177, 749, 10, 86, 993, 461, 952, 518, 823, 608, 160, 255, 914, 798, 33, 736, 264, 481, 446, 842, 194, 365}

    1410

    Returns: { 20, 13 }

  13. {192}

    45

    Returns: { 0, 0 }

  14. {328, 973, 135, 66, 802}

    719

    Returns: { 4, 1 }

  15. {450, 53, 454, 971, 270, 835, 320, 436, 319, 739, 19, 809, 625, 345, 107, 960, 647, 922, 136, 655, 651, 275, 80, 994, 353, 675, 637, 843, 206, 294, 729, 486, 452, 86, 586, 165, 121, 997, 734, 260, 553, 183, 492, 947, 204, 334, 611, 755, 962}

    12193

    Returns: { 35, 14 }

  16. {460, 425, 524, 776, 94, 392, 15, 513, 40, 757, 996, 662, 984, 192, 250, 140, 380, 753, 159, 916, 644, 706}

    3630

    Returns: { 18, 8 }

  17. {452, 367, 916, 53, 433, 219, 29, 730}

    1937

    Returns: { 5, 1 }

  18. {947, 965, 650, 863, 156, 507, 740, 895, 823, 55, 550, 986, 505, 326, 135, 779, 238, 46, 375, 264, 190, 857, 611, 17, 474, 929, 725, 679, 355, 52, 487, 676, 121, 342, 570, 62, 894, 921, 648, 532, 484}

    20675

    Returns: { 8, 0 }

  19. {959, 460, 721, 446, 808, 705, 464, 258, 343, 534, 982, 588, 695, 762, 559, 967, 256, 802, 270, 780, 608, 930, 82, 207, 678, 554, 810, 746, 340, 968, 423, 97, 870, 158, 566}

    2677

    Returns: { 32, 24 }

  20. {217, 518, 774, 447, 926, 352, 927, 173}

    378

    Returns: { 7, 6 }

  21. {325, 886, 304, 268, 370, 361, 948, 255, 239, 486, 215, 547, 967, 222, 742, 692, 79, 748, 680, 359, 718, 309, 378, 288, 971, 525, 63, 634, 258, 784, 236, 895, 305, 754, 376}

    12252

    Returns: { 18, 5 }

  22. {468, 768, 877, 394, 883, 16, 743, 380, 774, 880, 608, 704, 745, 677, 988, 442, 413, 555, 372, 427, 423, 299, 284, 347, 868, 492, 965, 171, 696, 496, 367, 144, 390, 524, 906, 865, 534, 497, 813, 409}

    3000

    Returns: { 36, 29 }

  23. {253, 959, 619, 780, 232, 494, 395, 102, 742, 565, 423, 75, 643, 914, 234, 32, 803, 790, 499, 319, 216, 936, 263, 530, 836, 853, 295, 162, 999, 730, 886, 811, 224, 590}

    15953

    Returns: { 11, 2 }

  24. {549, 440, 161, 964, 135, 92, 322, 859, 13, 576, 82, 636, 780, 871, 408, 685, 980}

    4775

    Returns: { 11, 4 }

  25. {670, 624, 589, 897, 343, 763, 730, 43, 104, 801, 226, 975, 393, 260, 315, 406, 24, 216, 957, 149, 736, 331, 672, 852, 599, 497, 221, 129, 881, 800, 788, 953, 286, 31, 733, 991, 106, 748, 282}

    7926

    Returns: { 30, 14 }

  26. {736, 746, 606, 778, 175, 124, 54, 343, 212, 304, 151, 508, 844, 394, 940, 863, 847, 980, 3, 744, 942, 361, 493, 374, 384, 397, 975, 738, 28, 534, 311, 934, 748, 628, 611, 49, 367, 155, 150, 137, 590, 555, 729, 505, 380}

    4071

    Returns: { 40, 25 }

  27. {122, 160, 238, 220, 856, 425, 442, 143, 579, 115, 469, 566, 484, 133, 165, 13, 503, 380, 984, 342, 411, 936, 387, 597, 423, 650, 312, 752, 871, 111, 179, 487, 71, 976, 456, 813, 51, 235, 540, 145, 177, 86, 660, 618}

    8275

    Returns: { 33, 13 }

  28. {710, 802, 948, 866, 943, 129, 369, 759, 168, 728, 930, 583, 740, 944, 278, 766, 339, 915, 393, 152, 807, 80, 922, 306}

    5995

    Returns: { 17, 9 }

  29. {603, 874, 198, 502, 142, 650, 65, 180, 518, 476, 973, 529, 15, 779, 102, 562, 387, 643, 842, 323, 257, 805, 470, 309, 713, 138, 204, 296, 770, 259, 334, 797, 43, 719, 405, 341}

    6804

    Returns: { 27, 12 }

  30. {674, 415, 799, 675, 61, 881, 259, 561, 543, 84, 745, 163, 560, 861, 646, 238, 463, 330}

    8362

    Returns: { 4, 0 }

  31. {580, 635, 543, 167, 994, 386, 608, 298, 984, 276, 659, 485, 297, 946, 154, 426, 420, 906, 707, 786, 238, 959, 288, 807, 651, 943, 112, 827, 794}

    625

    Returns: { 28, 25 }

  32. {11, 106, 522, 987, 535, 452, 90, 944, 878, 305, 247, 826, 394, 929, 619, 111, 472, 961, 322}

    313

    Returns: { 18, 15 }

  33. {304, 706, 398, 697, 73, 679, 826, 117, 232, 40, 222, 745, 681, 94, 895, 747, 720, 516, 917, 116, 77, 609, 30, 283, 150, 600, 854, 26, 684, 627}

    1793

    Returns: { 28, 16 }

  34. {221, 386, 146, 708, 540, 86, 505, 653, 726, 603, 740, 737, 240}

    3925

    Returns: { 7, 3 }

  35. {855, 156, 869, 623, 538, 913, 386, 795, 392, 62, 346, 185, 541, 231, 373, 751, 271, 949, 885, 507, 792, 138, 493, 789, 821, 34, 948, 370, 61, 914, 329, 38, 858, 532, 814}

    2994

    Returns: { 31, 20 }

  36. {542, 273, 6, 20, 71, 198, 417}

    635

    Returns: { 5, 1 }

  37. {194, 549, 740, 519, 874, 582}

    2381

    Returns: { 2, 1 }

  38. {135, 860, 780, 741, 151, 778, 482, 650, 626, 69, 484, 897, 544, 821, 389, 83, 356, 116, 979, 813, 987, 718, 292, 365, 448, 214, 402, 393, 139, 344, 153, 655, 818, 668, 82, 851, 776, 735, 455, 125, 437, 578, 377, 348, 555, 439, 939, 321}

    22891

    Returns: { 10, 1 }

  39. {847, 877, 269}

    1020

    Returns: { 1, 1 }

  40. {349, 735, 687, 160, 84, 478, 405, 396, 841, 479, 301, 13, 152, 246, 949, 849, 657, 318, 264, 552, 491, 730, 259, 844, 972, 427, 340, 736, 655, 944, 935, 700, 932, 748, 430, 767, 808, 753, 752, 30, 504, 876, 447, 793, 417}

    10722

    Returns: { 32, 17 }

  41. {881, 581, 768, 151, 706, 164, 261, 312, 789, 410, 576, 712, 590, 59, 823, 867, 51, 246, 393, 661}

    4233

    Returns: { 14, 7 }

  42. {219, 585, 301, 793, 864, 687, 259, 436}

    1458

    Returns: { 6, 3 }

  43. {549, 35, 233, 569, 558, 885, 994, 991, 516, 696, 22, 692, 749, 659, 307, 63, 122, 435, 910}

    1792

    Returns: { 17, 10 }

  44. {736, 480, 235, 134, 713, 421, 286, 780, 429, 425, 837, 76, 349, 775, 339, 766, 830, 707, 40, 490, 25, 919, 825, 358, 483, 782, 280, 301, 907, 972, 450, 13, 327, 302, 47, 500, 187, 298, 178, 401, 866, 179, 192, 874, 22, 42}

    11710

    Returns: { 31, 10 }

  45. {269}

    88

    Returns: { 0, 0 }

  46. {546, 790, 728, 560, 415, 847, 393, 500, 752, 289, 974, 114, 355, 352, 602, 729, 127, 834, 536, 54, 523, 502, 521, 439, 11, 963, 600, 208, 87, 708, 389, 737, 9}

    11549

    Returns: { 16, 5 }

  47. {311, 50, 706, 527, 636, 366, 80, 485, 238, 302, 99, 861, 312, 806, 812, 848, 488, 295, 610, 817, 765, 694, 854, 35, 753, 304, 152, 16}

    11675

    Returns: { 9, 1 }

  48. {39, 338, 527, 254, 869, 457, 548, 856, 998, 37, 910, 242, 526, 573, 42, 57, 673, 960, 748, 771}

    10091

    Returns: { 4, 0 }

  49. {273, 405, 691, 916, 917, 813, 285, 665, 616, 827, 118, 714, 942, 93, 444, 780, 762}

    4373

    Returns: { 12, 6 }

  50. {527, 311, 180, 573, 922, 513, 724, 282, 886, 415, 151, 692}

    601

    Returns: { 11, 9 }

  51. {649, 908, 976, 281, 487, 269, 428, 984, 402, 663, 716, 183, 528, 979, 703, 231, 778}

    6066

    Returns: { 9, 4 }

  52. {637, 161, 135, 520, 349, 702, 880, 429, 717, 607, 480, 479, 275, 993, 501, 515, 116, 291, 199, 810, 555, 260, 489, 206, 634, 955, 322, 770, 529, 268, 518, 224, 692, 129, 39, 188, 517, 265, 44, 254, 152}

    17415

    Returns: { 4, 0 }

  53. {48, 306, 331, 100, 316, 142, 805, 899}

    2287

    Returns: { 4, 0 }

  54. {955, 96, 161, 259, 642, 242, 772, 369, 311, 785, 92, 991, 620, 394, 128, 774, 973, 94, 681, 771, 916, 373, 523, 100, 220, 993, 472, 798, 132, 361, 33, 362, 573, 624, 722, 520, 451, 231, 37, 921, 408, 170, 303, 559, 866, 412, 339, 757, 822, 192}

    3619

    Returns: { 46, 30 }

  55. {1000}

    1

    Returns: { 0, 0 }

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

    45

    Returns: { 15, 7 }

  57. { 676, 11, 223, 413, 823, 122, 547, 187, 28 }

    1000

    Returns: { 7, 2 }

  58. { 2, 4, 6, 8 }

    1

    Returns: { 3, 3 }

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: