Statistics

Problem Statement for "TheTournamentDivTwo"

Problem Statement

John and Brus have an interest in team sports tournaments. They are currently investigating the intermediate standings of a tournament. They don't know which games have been played so far. They only know that the tournament is played using the following rules:

Each game is played between two teams and results in either a victory for one team or a draw. If a team wins a game, it gains two points and its opponent gains no points. In case of a draw, each team gains one point. The score of a team is the sum of all the points it has gained from all its games. There are no restrictions on which teams can play against each other, and each pair of teams can play against each other any number of times (possibly zero).

You are given a int[] points representing the intermediate standings of the tournament. The i-th element of points is the score of the i-th team. Return the minimum number of games that could have been played to achieve those standings. If points doesn't represent a valid state, return -1 instead.

Definition

Class:
TheTournamentDivTwo
Method:
find
Parameters:
int[]
Returns:
int
Method signature:
int find(int[] points)
(be sure your method is public)

Constraints

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

Examples

  1. {10, 1, 1}

    Returns: 6

    Here the first team has five wins or four wins and two draws. The second and the third team each has one draw.

  2. {1, 1, 1}

    Returns: -1

    These standings are impossible. For each of the three teams to have one point, each one must have played in a game that resulted in a draw. There is no way for three teams to have each played in exactly one game.

  3. {0, 0, 0, 0, 0, 0, 0}

    Returns: 0

    There are no points, which means no games have been played yet.

  4. {13, 8, 7}

    Returns: 14

  5. {0, 0}

    Returns: 0

  6. {4, 6, 2, 0, 2}

    Returns: 7

  7. {4, 3, 8}

    Returns: -1

  8. {970788, 567065, 850833, 413055, 597709}

    Returns: 1699725

  9. {239546, 37691, 615541, 597006}

    Returns: 744892

  10. {914426, 80793, 564501}

    Returns: 779860

  11. {858666, 807397, 617554, 74573}

    Returns: 1179095

  12. {379023, 655526, 970659, 417541}

    Returns: -1

  13. {258516, 596387}

    Returns: -1

  14. {776620, 546278, 79126, 701140}

    Returns: 1051582

  15. {754954, 762307}

    Returns: -1

  16. {378645, 557643, 255787, 268210}

    Returns: -1

  17. {37865, 581321, 929607, 399994}

    Returns: -1

  18. {773622, 724226}

    Returns: 748924

  19. {621871, 482131, 778732}

    Returns: 941367

  20. {648794, 770, 173780, 235834}

    Returns: 529589

  21. {351377, 544122, 597006, 923704, 597709, 970788, 752135, 413055, 615541, 839920, 835600, 41410, 289218, 670520, 766255, 341404, 51110, 268210, 89276, 748996, 629180, 908065, 378645, 890847, 239546, 427628, 290636, 546278, 571656, 557643, 15758, 37691, 850833, 70818, 567065, 873940, 79126, 446450, 970659, 417541, 220562, 701140, 379023, 215491, 645867, 426790, 496382, 255787, 776620, 655526}

    Returns: -1

  22. {251174, 605684, 198304, 647870, 360042, 644476, 277476, 471731, 82297, 521272, 953471, 660841, 778274, 813522, 141261, 898207, 56375, 482786, 135690, 530834, 925652, 555668, 412969, 665008, 708145, 809530, 330688, 775813, 751802, 250902, 208816, 740975, 354381, 861177, 490241, 585600, 790952, 772008}

    Returns: 10250957

  23. {853390, 363346, 266637, 289031, 342106, 946118, 711622, 123120, 182258, 109622, 525994, 329043, 532615, 257308}

    Returns: 2916105

  24. {499155, 403096, 233815, 486399, 794819, 145210, 792108, 569607, 378846, 516139, 428150, 473839, 226688}

    Returns: -1

  25. {159880, 459329, 725993, 868211, 736634, 162494, 381427, 151611, 124128, 873813, 457859, 192325, 329676, 402907, 891954, 277442, 487622, 979030, 111955, 707173, 520459, 600498, 355903, 24810, 961124, 468006, 52378, 751636, 541209}

    Returns: 6878743

  26. {281190, 829003, 915161, 840325, 80159, 38149, 147085, 748656, 999062, 120973, 536246, 760474, 395151, 23397, 676997, 844844, 823440, 781659, 52533, 704733, 95843, 995074, 756999, 39823, 865105, 525262, 825536, 32537, 130615, 802719, 228469, 942687, 134896, 905294, 882251, 272684, 353243, 473944, 542161, 315673, 509113, 994213, 891586, 111559, 195760, 254239, 269569, 269098}

    Returns: -1

  27. {755074, 662140, 185829, 543995, 799217, 818973, 633454, 435103, 485090, 436115, 414805, 559213, 931576, 315325, 599475, 573819, 762250, 846494, 924633, 818990, 10586, 73097, 830126, 562983, 260032, 596103, 764296, 312104, 941886, 502427, 506293, 896978, 473175, 495532, 265507, 594850, 221617}

    Returns: 10404581

  28. {11078, 656518, 268761, 394247, 288969, 8774, 692578, 760731, 984674, 39365, 924484, 141787, 928852, 117047, 306481, 88905, 335988, 161543, 492461, 599422, 634346, 743483, 840088, 998452, 925940, 634160, 603204, 460863, 328060, 221871, 462154, 678527, 640080, 398859, 993398, 932868, 138096, 73891, 890014, 483265, 903732, 562690, 869871, 761222, 723861, 760511, 396292, 931043, 190654, 399796}

    Returns: 13391978

  29. {422258, 435428, 687211, 719627, 949877, 14171, 486415, 449228, 523665, 616899, 210103, 967560, 618110, 342291, 916474, 791704, 524198, 382991, 222113, 455885, 997518, 983305, 632942, 658927, 109886, 434495, 623285, 475297, 924365}

    Returns: 8288114

  30. {235372, 155108, 596774, 605913, 991377, 676131, 770403, 32491, 792722, 63133, 468965, 543957, 132423, 727662, 313110, 598164, 156442, 841101, 770424, 814177, 728292, 544741, 643757, 366513, 502499, 511164, 158927, 674401, 8528, 40053, 182456, 373495, 729599, 490097, 288976, 248807, 751734, 313854, 947262, 430059, 161649, 765472, 513399, 229005, 464794, 893858, 420949, 206143, 137631}

    Returns: -1

  31. {626781, 807946, 697006, 348952, 689171, 473935, 550814, 470750, 817539, 427609, 752122, 579019, 490846, 913022, 415487, 355497, 351074, 835591, 470649, 246268, 446374, 839889, 770794, 720484, 344103, 790588, 637639, 679085, 601088, 541391, 889175, 897636, 641389, 729176, 951305, 971603, 115683, 467047, 670519, 115540, 823692, 745806, 766251, 296341, 239543, 376592}

    Returns: -1

  32. {347864, 260821, 841224, 678266, 849663, 463914, 730785, 544472, 882257, 412889, 182774, 351779, 308800, 798187, 605663, 365000, 175758, 251171, 530681, 925579, 271986, 485572, 490201, 661153, 473763, 709524, 335675, 113518, 753454, 854337, 350902, 721267, 408135, 672004, 900733, 255666, 977426, 471663, 490903, 940975, 648256, 256343, 460035}

    Returns: 11605519

  33. {902274, 574038, 638922, 466186, 278802, 826645, 551710, 903058, 916108, 840973, 617472, 125417, 790261, 973831, 824118, 867955, 355365, 476803, 262478, 733793, 567083, 931030, 733670, 799155, 578565, 306676, 100234, 347755, 951170, 959328, 388316, 686335, 316843, 945159, 602973, 909832, 228109, 599771, 435685, 994771, 345830, 369600, 392085, 486990}

    Returns: 13451587

  34. {987535, 656453, 145747, 405863, 697023, 883377, 776616, 229853, 254796, 304931, 343544, 180989, 240309, 639104, 419491, 418209, 973352, 722513, 767610, 770801, 232824, 425305, 346545, 607304, 705486, 653431, 714929, 817836, 663155, 706894, 156302, 303142, 250054, 593041, 133286, 660523, 217158, 276320, 671703, 129146, 521494, 626649, 700836, 555438, 368729, 489937, 574290}

    Returns: -1

  35. {801913, 615291, 799166, 373096, 488799, 959207, 141839, 673790, 336110, 721612, 955018, 914466, 631526, 273174, 959979, 635095, 786772, 327566, 546467, 905263, 395477, 531563, 799474, 950853, 106250, 256768, 364295, 600569, 565490, 184923, 262242, 614731, 646341, 242759, 113002, 466538, 343900, 433437, 581656, 724627, 285083, 716931, 610561, 862123, 514676, 309152}

    Returns: 12664785

  36. {210610, 434794, 634742, 781089, 176295, 394736, 566317, 477155, 513155, 682219, 714935, 970116, 817378, 571114, 304282, 618447, 545105, 741346, 723993, 148163, 749815, 511539, 874152, 906725, 450407, 313400, 779079, 621226, 257942, 379573, 516834, 107635, 486216, 780193, 746255, 996734, 363006, 776484, 844978, 812907, 842475, 690607, 861822, 120971, 468720, 546419, 779510, 255820, 675932}

    Returns: -1

  37. {382941, 435407, 512899, 597473, 616821, 596437, 419602, 806859, 918108, 910091, 622249, 455867, 314156, 606234, 724114, 391657, 697177, 986410, 858901, 889992, 392427, 409886, 534450, 167547, 782414, 583301, 120103, 749777, 521984, 749217, 223616, 922096, 816464, 924336, 882645, 823215, 887191, 442290, 932935, 675294}

    Returns: -1

  38. {857950, 397856, 203423, 951424, 507016, 414288, 138163, 815052, 234128, 965943, 559943, 347131, 438614, 301402, 658825, 645303, 519232, 462746, 122870, 732618, 329120, 285852, 906730, 783231, 762588, 710747, 999379, 116824, 842571, 126036, 645535, 456720, 649423, 281504, 805152, 588385, 512744, 654724, 565229, 268045, 908409, 150481}

    Returns: 11311678

  39. {627936, 317117, 158682, 645251, 638237, 687243, 117087, 431214, 999146, 209148, 730427, 488275, 436638, 223691, 631844, 635167, 728004, 464764, 852900, 837002, 183660, 795455, 709893, 330431, 194020, 675838, 315074, 867251, 586106, 528391, 296304, 202824, 419262, 601514, 836835, 799151, 386041, 346946, 181500, 990084, 616045, 458821}

    Returns: -1

  40. {985045, 307368, 490379, 761201, 392135, 132939, 230890, 855543, 749790, 313081, 640493, 221664, 504741, 637598, 979705, 722609, 284732, 537993, 437061, 544974, 348057, 704031, 717019, 725994, 716294, 853829, 355307, 981602, 743102, 561448, 142116, 264646, 772057, 537607, 245433, 810770, 414038, 795805, 891512, 286248, 161493}

    Returns: -1

  41. {948176, 917348, 940920, 939310, 949322, 975760, 953207, 934872, 910342, 998436, 939664, 969894, 973572, 993084, 986710, 937410, 965933, 957341, 915156, 990803, 996940, 922741, 942605, 933434, 926048, 985688, 909683, 974390, 928850, 914206, 945497, 968820, 997001, 915508, 980726, 951084, 940339, 945499, 926094, 991773, 978687, 970442, 945470, 954714, 967755, 967331, 965620, 940299}

    Returns: 22892252

  42. {973370, 959252, 966228, 909054, 950938, 959260, 934465, 987006, 919739, 944164, 913262, 949977, 950900, 952112, 950778, 957815, 978994, 953774, 907518, 903986, 946155, 996597, 907364, 964390, 906494, 940959, 926851, 983345, 970943, 970273, 955537, 947414}

    Returns: 15169457

  43. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    Returns: 25000000

  44. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 0

  45. {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}

    Returns: -1

  46. {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999}

    Returns: -1

  47. {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999}

    Returns: 24999975

  48. {2, 2, 2 }

    Returns: 3

  49. {10, 1, 1 }

    Returns: 6

  50. {13, 8, 7 }

    Returns: 14

  51. {1, 1, 1 }

    Returns: -1

  52. {2, 1, 1 }

    Returns: 2

  53. {1, 1 }

    Returns: 1

  54. {1, 2, 1 }

    Returns: 2

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: