Statistics

Problem Statement for "Marriage"

Problem Statement

Here is one way in which marriages might be arranged:

Once a year, all the unmarried people are collected in one place and are given time to get acquainted with each other. Each person then evaluates every person of the opposite sex on a scale of -100 to 100 (inclusive) based on how satisfactory that person would be as a prospective spouse. Then they are married to maximize the sum of values each partner in each marriage gave to his/her spouse.

Your task is, given a String[] malePoints describing evaluations for every male by each female and a String[] femalePoints describing evaluations for every female by each male, return the maximum possible satisfaction score (the sum of all satisfaction points) for a marriage arrangement. Not everyone must be married, and if someone remains unmarried then his or her satisfaction score is 0.

Each element of malePoints and femalePoints is a single-space delimited list of integers. Element i of malePoints contains a list of evaluations given to the ith male by every female. The jth integer of that list represents the evaluation given by the jth female (where the jth female is the female represented by element j of femalePoints). The elements of femalePoints are formatted in the same way (but substituting males for females and vice versa). For example:

malePoints = {"0 5 10", "50 100 30"}
femalePoints = {"100 50", "50 75", "10 20"}

In this scenario, there are 2 males and 3 females. Here's how the evaluations were given:
1st male: Given a 0 by the 1st female, 5 by the 2nd female, and 10 by the 3rd female
2nd male: Given a 50 by the 1st female, 100 by the 2nd female, and 30 by the 3rd female
1st female: Given a 100 by the 1st male, 50 by the 2nd male
2nd female: Given a 50 by the 1st male, 75 by the 2nd male
3rd female: Given a 10 by the 1st male, 20 by the 2nd male"

Definition

Class:
Marriage
Method:
best
Parameters:
String[], String[]
Returns:
int
Method signature:
int best(String[] malePoints, String[] femalePoints)
(be sure your method is public)

Notes

  • It is not necessary for everyone to marry. See example 5.

Constraints

  • malePoints has between 1 and 9 elements inclusive
  • femalePoints has between 1 and 9 elements inclusive
  • each element of malePoints and femalePoints will not contain leading/trailing spaces
  • each element of malePoints and femalePoints will be a list of integers without leading zeroes, separated by exactly one space. Integers will be between -100 and 100 inclusive. Zero will be represented as 0, never as -0.
  • the number of integers in each element of malePoints will equal to the number of elements in femalePoints
  • the number of integers in each element of femalePoints will equal to the number of elements in malePoints

Examples

  1. {"-100 100","-10 50"}

    {"100 50","10 90"}

    Returns: 150

    If the first female marries the first male their combined satisfaction is -100 + 100 = 0. If the first female marries the second male their satisfaction is -10 + 50 = 40. If the second female marries the first male their satisfaction is 100 + 10 = 110. If the second female marries the second male their satisfaction is 50 + 90 = 140. Hence, the best arrangement would be to marry the second female with the first male and the first female with the second male for the total of 150 points.

  2. {"10 10 10 10 10 10 10 10 10","10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10","10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10","10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10","10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10"}

    {"100 100 100 100 100 100 100 100 100","100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100","100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100","100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100","100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100"}

    Returns: 990

  3. {"25"}

    {"75"}

    Returns: 100

  4. {"1 10","20 100"}

    {"80 2", "20 5"}

    Returns: 186

  5. {"-100 -100 -100 -100", "-100 -100 -100 -100"}

    {"100 100","100 100","100 100","100 100"}

    Returns: 0

  6. {"-10"}

    {"0"}

    Returns: 0

    If these two people marry, the sum is -10; and if they don't marry, the sum is 0.

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

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

    Returns: 33

  8. {"10 3"}

    {"4","5"}

    Returns: 14

  9. {"4","5"}

    {"10 3"}

    Returns: 14

  10. {"-2 1","-2 1"}

    {"-2 1","-2 1"}

    Returns: 2

  11. {"-2 1","-2 1"}

    {"-2 1","-2 1"}

    Returns: 2

  12. {"1 1 1 1 1 1 1 99 98", "1 1 1 1 1 1 1 71 73"}

    {"10 10","9 9","8 8","7 17","6 16","5 15","4 14","3 13","2 12"}

    Returns: 187

  13. {"10 10","9 9","8 8","7 17","6 16","5 15","4 14","3 13","2 12"}

    {"1 1 1 1 1 1 1 99 98", "1 1 1 1 1 1 1 71 73"}

    Returns: 187

  14. {"1 90"}

    {"3","2"}

    Returns: 92

  15. {"3","2"}

    {"1 90"}

    Returns: 92

  16. {"72 47 -35 7 -3 83 -30 -93 56", "-95 -94 16 -3 -84 73 97 -51 93", "56 -9 100 -82 -70 -29 -79 66 -12", "-4 61 -20 84 -79 -13 -36 -85 -33", "42 12 57 -14 74 -79 -84 83 -13", "-74 11 -63 90 91 -79 -64 16 3", "32 -14 14 -10 -13 -76 58 68 -13", "-71 -40 4 -64 -69 64 -61 -46 -38", "72 25 -55 95 -2 -10 -27 57 96"}

    {"72 47 -35 7 -3 83 -30 -93 56", "-95 -94 16 -3 -84 73 97 -51 93", "56 -9 100 -82 -70 -29 -79 66 -12", "-4 61 -20 84 -79 -13 -36 -85 -33", "42 12 57 -14 74 -79 -84 83 -13", "-74 11 -63 90 91 -79 -64 16 3", "32 -14 14 -10 -13 -76 58 68 -13", "-71 -40 4 -64 -69 64 -61 -46 -38", "72 25 -55 95 -2 -10 -27 57 96"}

    Returns: 1178

  17. {"72 47 -35 7 -3 83 -30 -93 56", "-95 -94 16 -3 -84 73 97 -51 93", "56 -9 100 -82 -70 -29 -79 66 -12", "-4 61 -20 84 -79 -13 -36 -85 -33", "42 12 57 -14 74 -79 -84 83 -13", "-74 11 -63 90 91 -79 -64 16 3", "32 -14 14 -10 -13 -76 58 68 -13", "-71 -40 4 -64 -69 64 -61 -46 -38", "72 25 -55 95 -2 -10 -27 57 96"}

    {"-58 71 -68 -45 80 88 -90 12 -10", "42 81 89 76 -40 91 -80 55 -77", "10 -48 -88 -60 66 -33 -100 94 -69", "-89 -43 79 50 40 80 -94 45 22", "-31 -16 47 -21 41 -5 -55 -42 -95", "-56 58 38 -67 62 1 54 99 -33", "-71 -46 -89 65 83 4 91 55 -4", "-18 97 30 -16 98 -98 -43 8 -93", "11 15 -38 -100 22 94 81 66 39"}

    Returns: 1045

  18. {"-58 71 -68 -45 80 88 -90 12 -10", "42 81 89 76 -40 91 -80 55 -77", "10 -48 -88 -60 66 -33 -100 94 -69", "-89 -43 79 50 40 80 -94 45 22", "-31 -16 47 -21 41 -5 -55 -42 -95", "-56 58 38 -67 62 1 54 99 -33", "-71 -46 -89 65 83 4 91 55 -4", "-18 97 30 -16 98 -98 -43 8 -93", "11 15 -38 -100 22 94 81 66 39"}

    {"-3 -72 -63 -50 -67 -19 -70 -49 -81", "-48 -46 -54 -61 -68 -60 -100 -86 -17", "-83 -60 -27 -14 -76 -55 -98 -47 0", "-70 -44 -90 -19 -26 -72 -28 -94 -65", "0 -15 -63 -40 -30 -54 -47 -76 -98", "-57 -40 -62 -88 -86 -56 -57 -45 -60", "-58 -30 -51 -20 -34 -32 -33 -32 -56", "-47 -46 -16 -1 -49 -22 -23 -87 -57", "-73 -93 -88 -24 -9 -21 -64 -29 -18"}

    Returns: 365

  19. {"-1 -1 3", "-1 -1 3", "-1 -1 3"}

    {"-1 -1 3", "-1 -1 3", "-1 -1 3"}

    Returns: 6

  20. {"-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10"}

    {"-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10", "-1 -2 -3 -4 -5 -6 -7 -8 10"}

    Returns: 20

  21. {"1 2 3 4 5 6 7 8 9"}

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

    Returns: 18

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

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

    Returns: 18

  23. { "1 2 3", "3 4 5", "7 8 9" }

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

    Returns: 32

  24. { "10" }

    { "5" }

    Returns: 15

  25. { "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100" }

    { "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10" }

    Returns: 990

  26. { "-10 77 7 10 10 10 10 10 10", "7 7 -13 27 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 100 -10 10 10 10 10", "10 10 10 100 20 50 -10 10 -10" }

    { "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "-100 -100 -100 -100 -100 -100 -100 -100 -100", "-34 -3 76 12 13 15 100 16 -9", "100 100 100 100 100 100 100 100 100", "10 18 100 100 100 100 100 100 100", "100 100 100 -13 16 100 100 1 100", "100 100 100 100 100 21 21 100 100", "100 13 17 100 100 -15 -100 100 100" }

    Returns: 993

  27. { "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10", "10 10 10 10 10 10 10 10 10" }

    { "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100", "100 100 100 100 100 100 100 100 100" }

    Returns: 990

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: