Statistics

Problem Statement for "YetAnotherTwoTeamsProblem"

Problem Statement

Manao is the coach of a soccer team. There are N boys numbered from 0 to N-1 on the team. Each of them has some level of soccer skill. Manao would like to divide the boys into two teams for today's training. The division should satisfy the following conditions:
  • Each boy is assigned to a team.
  • The total skill of first team is strictly greater than the total skill of the second team.
  • For each player P in the first team: if we were to move P into the second team, the total skill of the first team would become strictly smaller than the total skill of the second team.
The total skill of a team is the sum of skills of the boys on that team.

You are given a int[] skill containing N elements. The i-th element in skill is the skill of boy i. Manao is interested in the number of ways to perform such a division into teams. Please compute and return this number.

Definition

Class:
YetAnotherTwoTeamsProblem
Method:
count
Parameters:
int[]
Returns:
long
Method signature:
long count(int[] skill)
(be sure your method is public)

Constraints

  • skill will contain between 2 and 50 elements, inclusive.
  • Each element of skill will be between 1 and 60,000, inclusive.

Examples

  1. {5, 4, 7, 6}

    Returns: 2

    The two possible divisions are: Boys 0 and 2 against boys 1 and 3. Boys 2 and 3 against boys 0 and 1.

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

    Returns: 10

    Manao can put any three boys on the first team.

  3. {1, 2, 3, 5, 10}

    Returns: 5

    The possible choices of the first team are: Boys 0 and 4. Boys 1 and 4. Boys 2 and 4. Boys 3 and 4. Boys 0, 1, 2 and 3.

  4. {1, 2, 3, 4, 10}

    Returns: 0

  5. {999, 999, 999, 1000, 1000, 1001, 999, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 999, 1000, 512, 511, 1001, 1001, 1001, 1001, 1001, 1000}

    Returns: 17672631900

  6. {37028,40264,36021,11759,54810,36480,22783,55223,45133,23918,54450,54364,10595,8328,42950,19565,18444,56534,41131,7653,34266,15834,33087,22241,49900,15112,36363,9825,19477,55105,45751,58312,25223,3537,5900}

    Returns: 686851469

  7. {16866,8438,21770,26399,25027,50024,42244,4607,59888,27857,2770,12298,31714,25795,7917,46608,9493,32358,14075,28300,27986,18672,56246,42404,1907,30013,11015,38156,28737,30251,214,21415,58849}

    Returns: 67317634

  8. {56709,32581,23159,40328,14924,22231,14457,53622,14346,55254,58820,57260,14223,12245,28234,56764,32034,34198,54543,27911,37030,33276,48299,54512,53249,8496,23860,35884,33915,599,24252,54549,20933,35243,25862,31680,39485,37801,43943,4239,58292,36666,15207,33481,51105,24892,3437}

    Returns: 1327342507775

  9. {44344,42325,18121,12218,29525,52085,54487,8840,57246,36330,56163,9591,31934,6674,28796,55523,53475,14483,34562,32723,23014,15424,13374,44377,45881,31275,6917,4117,4516,59900,6284,4078,18681,31655,43060,583,38928,37164,17073,59280,32432,57500,21884}

    Returns: 76195638636

  10. {57762,53240,11190,17702,27022,53692,45922,8256,20019,31795,12679,53489,45742,13752,29481,39036,41376,15440,34452,43029,58480,19915,27126,43449,9641,32079,438,44387,17068,47610,4315,54863,17020}

    Returns: 122393807

  11. {18894,46533,10862,19224,46971,58585,14753,10238,1194,9540,45566,7114,41801,36421,50651,35288,35376,31909,3370,20750,34150,9575,5095,17176,58754,16220,57446,27944,25191,28573,36034,21719,28881,19248,28836,35059,25247,13881,18534,9754,7179}

    Returns: 27078443106

  12. {28797,6143,55039,25879,59422,6626,4509,16018,4636,15894,41659,57882,42578,56116,52996,16573,22088,26386,51073,20857,15411,46194,23401,9835,12280,12475,53931,3531,2073,49054,42328,54276,6336,35803,56503,6542,3964,32831,38583}

    Returns: 6108404521

  13. {35660,2335,3521,44315,3057,37426,22954,48205,30950,53336,14738,23338,38611,1864,20736,9026,7984,34714,31984,20501,22799,5613,31280,55036,3241,44658,8534,40174,55816,21268,43875,10482,17373,54487}

    Returns: 178616648

  14. {23696,36001,31037,34244,1070,59614,32627,31562,59949,15522,54451,969,19273,41134,36651,39281,40685,7178,9707,56131,39347,421,53291,42393,59279,2859,6083,59464,38237,18704,41352,28269,46581,19207,59830,40320,13547,38493,47445,30912,32539,1035,40975,26742,44732,53264}

    Returns: 215725275242

  15. {46755,37263,28044,13455,15946,38699,11341,17722,7147,50203,25388,5998,55495,15985,52028,18697,54301,31114,53624,6176,59486,8673,27029,1247,2527,1478,48617,25056,19020,36240,35204,40290,1526,10056,56919,34867,21270,40482,53719,7823,53555,11240,47185}

    Returns: 54304293557

  16. {46440,35708,3620,36210,11249,9881,13178,13480,6907,25371,42890,13677,17908,1262,18888,27200,27847,31299,55031,36918,47041,29881,31336,56880,23642,56710,16224,40741,32957,45739,1599,20642,39361,59170,59096}

    Returns: 349448830

  17. {59213,31771,9594,2728,21623,24680,26170,51487,26706,51118,3189,10097,38117,9053,1018,7428,38212,57910,57168,1410,103,27757,20177,49310,51159,50210,52611,5823,57170,50393,3870,28157,5450,18823,32221,44021}

    Returns: 236242743

  18. {10989,58592,54452,28105,613,42163,58911,30327,271,59581,24880,31549,20018,25949,18385,32713,41082,16248,45476,17321,17426,50917,7592,56892,3136,38600,46122,12010,58092,22857,23128,35527,48264,57702,16290,17210,50256,39326,36574}

    Returns: 3661066480

  19. {32325,8230,26970,10301,16147,27197,9797,43055,24965,56160,58709,47842,54531,24997,39439,42925,43381,49635,30658,58374,48493,25575,43023,25264,51279,26069,20577,6436,27103,49642,34079,30163,29174,23518,20706,44591,4655,55742,8737,21755,57233,39381,29423,45248,56147,27192,41184,15304,6809}

    Returns: 10305036506229

  20. {33611,19089,22668,51543,427,42416,11848,15488,51670,1892,55365,43096,55772,13674,26341,3990,2070,46550,41676,34047,33445,32988,28995,14831,17394,12078,52476,54776,21773,52961,51281,2187,38767,56407,3830,18849,17357,55563,54,46177,620,54769}

    Returns: 7918588646

  21. {43270,19648,37419,40897,48133,10690,20459,55472,29535,16347,53994,43366,17574,5179,19770,32407,46031,37069,51989,24319,8913,54012,7919,57628,7329,47662,14231,481,40972,46094,27727,17380,40915,12637,56354,16436,47324,19504,27880,55790,6909,48104,9583,49205}

    Returns: 199952086067

  22. {16533,12553,21622,11322,2649,18900,45589,28264,38505,49196,58998,48389,38572,40896,3443,14536,30289,36279,10773,42528,20908,40613,23062,13779,19432,47798,58218,15481,36649,1655,29839,21133,9826,46324,55701,59171,1591,18889,24376,16794,24844,51419,14019,49826}

    Returns: 151280025550

  23. {38007,51214,37548,49854,5183,1072,13924,35151,21269,52366,3505,59043,31753,23540,31494,41233,13707,26798,23111,26463,2544,48227,17330,7274,19097,32069,54449,16233,34024,36766,35659,12268,29988,59262,35908,41803,19823,2340,18812,50877,31095,7404,54245,59219,33983,52090}

    Returns: 492415023325

  24. {21469,50345,58543,13102,54301,37120,33892,28857,41162,46869,29641,20008,18653,32330,41173,40946,20289,40253,12473,24935,44439,32600,44426,12367,23707,326,7683,18431,2830,56551,53110,44412,21372,51796,54196,12397,26066,24292,6604,23188,45607,3021,30128,1542,28028,40183,47880,21614,47471}

    Returns: 2978716299179

  25. {56389,58567,53267,4315,48569,9805,19667,27421,49139,11131,19396,29493,29103,39375,8406,3420,42274,23630,12772,35521,12589,42214,11635,30096,36108,1854,32391,27589,26092,19279,16077,51324,3433,13558,11916,561,18009,29960,20483,4824,39116,32999,4758,45946,15193}

    Returns: 236155836796

  26. {27521,224,54415,32475,12141,53375,18498,41353,1740,55629,52187,18934,29057,33353,50435,41074,46009,37016,54143,48679,58052,3102,3588,53853,43867,39727,26347,28223,35743,12288,33472,59679}

    Returns: 31465307

  27. {26367,44112,24349,52014,415,34515,5625,7680,10408,52472,21409,56786,32710,52813,14470,1345,49794,33398,58916,4300,36269,24355,58271,38819,49830,25937,17478,19838,33275,2365,22419,18510,49679}

    Returns: 54383282

  28. {16109,8780,23084,12458,20727,3267,1738,23059,58987,2953,59971,9259,57101,11887,48199,21653,44672,34163,8338,3175,4339,35912,34105,39340,5869,19849,32179,20979,45600,24122}

    Returns: 13104309

  29. {16794,42752,40783,10591,58888,59105,12160,21696,19507,27909,25718,46152,21792,41590,49701,46836,41169,15961,32933,47924,17331,21093,12590,58554,29343,25887,53579,45920,8462,24587,2378,9544,14606}

    Returns: 202865898

  30. {16746,28801,3213,21030,10661,30403,59324,51401,31189,31613,55276,15372,660,38380,57240,31614,13619,15360,24132,4059,13460,16977,30043,15353,28488,55208,18356,57591,41324,20701,22089,36561,39189,49116,793,30674,25505,54274,29442,35117,5596,33697,49272}

    Returns: 55112260959

  31. {50991,50593,54427,13472,17855,49093,21517,8821,45584,6726,31830,10370,51363,9677,27953,17997,45749,52261,47959,14712,22845,52370,11048,27178,6653,59291,28703,17596,2454,49363,44893,18557,8812,38330,7785,55588,31827,47061,43661,59599,48770,59473}

    Returns: 68570292198

  32. {53270,32991,48022,42652,41688,56236,13072,30170,8110,8077,27707,10560,30734,15086,19256,5335,55704,24734,12827,26661,25305,20678,30556,49099,28428,37182,3089,51580,32823,871}

    Returns: 14281134

  33. {36563,55567,27818,13136,35314,9369,43200,17718,39643,47939,9300,46474,41180,3654,5600,59057,9433,5086,42029,8193,19364,20688,43125,52353,48109,38067,16955,58268,18737,35705,38073,21801}

    Returns: 84831298

  34. {35902,48626,2246,20616,3890,15933,46032,18996,58715,58395,51105,33135,26446,44593,12929,40445,35617,22722,17095,19909,8562,49211,1936,48743,388,36480,27346,31648,19818,50186,33168,46756,12995,16194,32052,24407,2571,26645,37613,16274,9990,23129,19009,3129,8886,2866,17716,29644,21849}

    Returns: 2827943511564

  35. {41332,4176,1542,10061,22661,346,10286,39310,20114,45485,9663,10946,57628,18671,33592,23970,18860,8064,4527,9510,1329,13681,23048,40574,21456,27456,16098,43407,41132,17614,28461,39802,503,8878,5824,11406,50041,43912,5861,18138,57792,14686,46250,23298}

    Returns: 64899504349

  36. {45048,35416,17737,13722,47850,52991,54704,19838,11310,12607,5520,57462,50097,9621,44193,25022,46729,30708,26424,4647,48413,21011,25131,33752,33316,47622,20711,4416,38554,25669,19694}

    Returns: 48615350

  37. {9774,25118,30282,32572,49262,32641,37456,29090,5872,3517,33900,22679,5831,23489,55976,43627,8635,9871,46248,41876,46721,54932,55815,54650,31540,12683,50748,53224,41870,32665,17386,51605,32872,31220,11065,21361,16396,21918,42081,32848,44428,42457,41203}

    Returns: 152313911416

  38. {18340,55300,55080,56840,46726,3703,49132,41016,24139,33475,2274,36780,41906,23964,43863,28046,10492,29211,28717,57966,10481,12071,30884,16196,36295,358,21031,32193,53121,4637,55892,44846,13311,32297,11191,38475,13631,51885,11733,9237,59256,25404,14106,14389,54308,54392,38476,19686}

    Returns: 1932351972428

  39. {38083,46416,57337,9837,18792,21545,18475,38308,50910,8934,30040,40902,15497,7826,26251,6546,32434,30153,59523,23688,36467,14673,4700,25770,2184,23231,53935,46439,26094,1735}

    Returns: 14414272

  40. {51121,41436,43889,36461,19251,13228,10529,5025,48443,37264,51640,50645,18264,47405,11673,8553,47063,40457,31759,26415,428,17323,34710,4182,4342,32811,10435,11105,25,44603,30435,34839,30693,14374,50515,44775}

    Returns: 379554406

  41. {893,10663,13236,38729,16174,30259,54124,50972,11358,5333,28877,55207,18976,42544,34285,19057,42599,51904,25723,49450,13628,46916,22817,52051,48054,26934,12323,6912,33530,1934,45175,31779,58926,44781}

    Returns: 180285858

  42. {31560,4780,40209,45956,28793,43679,3349,29301,35749,54537,23580,15231,3932,34160,51785,26254,31249,13154,50823,54242,999,11383,50068,32341,10117,40635,25345,19776,36727,19032}

    Returns: 13292320

  43. {22859,39063,2938,5257,21502,49226,27717,5334,50747,5996,38699,13265,1577,41046,48041,42523,54242,32423,31910,38800,807,28068,45529,21077,11379,361,41094,19797,30675,20368,5440}

    Returns: 11128612

  44. {58110,17443,30537,26559,45512,36232,30547,39382,21863,58896,24109,45121,44134,45503,9899,27092,57321,40041,17238,32529,45215,53415,31627,44514,6220,28011,17562,31481,55713,11106,27843,47620,37975}

    Returns: 288421563

  45. {59828,26711,46640,33969,34670,40486,42914,21143,55572,20581,25463,44005,5455,50443,4928,12413,13128,40276,9448,7377,50215,24170,55331,49362,38514,44023,19237,33308,9355,9658,4723,43213,22748,8781,46954}

    Returns: 702930058

  46. {20000,10000}

    Returns: 1

  47. {10000,10000}

    Returns: 0

  48. {60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000}

    Returns: 0

  49. {60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,59999}

    Returns: 63205303218876

  50. {60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000}

    Returns: 63205303218876

  51. {60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,60000,59997,59998,59999}

    Returns: 47081501377326

  52. {59999,59998,59996,59992,59984,59968,59936,59872,59744,59488,58976,57952,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904,55904}

    Returns: 116631352893006

  53. {59999,59998,59996,59992,59984,59968,59936,59872,59744,59488,58976,57952,55904,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808,51808}

    Returns: 115814877299226

  54. {59999,59998,59996,59992,59984,59968,59936,59872,59744,59488,58976,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952,57952}

    Returns: 116631352893006

  55. {60000,59999,59998,59997,59996,59995,59994,59993,59992,59991,59990,59989,59988,59987,59986,59985,59984,59983,59982,59981,59980,59979,59978,59977,59976,59975,59974,59973,59972,59971,59970,59969,59968,59967,59966,59965,59964,59963,59962,59961,59960,59959,59958,59957,59956,59955,59954,59953,59952,59951}

    Returns: 102480093753509

  56. {5, 4, 7, 6 }

    Returns: 2

  57. {1, 1, 1, 1, 1 }

    Returns: 10

  58. {999, 999, 999, 1000, 1000, 1001, 999, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 999, 1000, 512, 511, 1001, 1001, 1001, 1001, 1001, 1000, 998, 998, 998, 998, 995, 998, 998, 6998, 995, 997 }

    Returns: 9698406844234

  59. {123, 34, 546, 567, 2359, 3434, 3443, 876, 456, 879, 435, 675, 3451, 452, 1234, 890, 45, 345, 645, 1567, 2341, 908, 567, 2315, 780, 563, 245, 453, 789, 2434, 6743 }

    Returns: 12421761

  60. {951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999, 1000 }

    Returns: 102480093753509

  61. {999, 999, 999, 1000, 1000, 1001, 999, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 999, 1000, 512, 511, 1001, 1001, 1001, 1001, 1001, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 276548905350

  62. {60000, 59999, 59998, 59997, 59996, 59995, 59994, 59993, 59992, 59991, 59990, 59989, 59988, 59987, 59986, 59985, 59984, 59983, 59982, 59981, 59980, 59979, 59978, 59977, 59976, 59975, 59974, 59973, 59972, 59971, 59970, 59969, 59968, 59967, 59966, 59965, 59964, 59963, 59962, 59961, 59960, 59959, 59958, 59957, 59956, 59955, 59954, 59953, 59952 }

    Returns: 63205303218876

  63. {60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000, 60000 }

    Returns: 0

  64. {59950, 59951, 59952, 59953, 59954, 59955, 59956, 59957, 59958, 59959, 59960, 59961, 59962, 59963, 59964, 59965, 59966, 59967, 59968, 59969, 59970, 59971, 59972, 59973, 59974, 59975, 59976, 59977, 59978, 59979, 59980, 59981, 59982, 59983, 59984, 59985, 59986, 59987, 59988, 59989, 59990, 59991, 59992, 59993, 59994, 59995, 59996, 59997, 59998, 59999 }

    Returns: 102480093753509

  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, 50 }

    Returns: 8587288106241

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: