Calculating total number of mismatched socks combinations

Question

This is one of the problems from the 2015 ICPC NorthWest Programming Contest and I was wondering if there is any easier or more efficient way of doing it.

Here's the problem:

"Fred likes to wear mismatched socks. This sometimes means he has to plan ahead. Suppose his sock drawer has one red, one blue, and two green socks. If he wears the red with the blue, he's stuck with matching green socks. He put together two mismatched pairs if he pairs red with green and then blue with green. Given the contents of his sock drawer, how many pairs of mismatched socks can he put together?"

Here's a sample input:

Color 1 -> 4 socks

Color 2 -> 3 socks

Color 3 -> 7 socks

Color 4 -> 11 socks

Color 5 -> 4 socks

The way I'm doing is I first read the input into an array and sort it increasingly. That way I'll have the highest number of socks at the end of the array. From here I basically compare arr[i] and arr[i-1] and get the min between them. Add that to the total, save the remainder and just repeat the process going down the array. For example, using the sample input it looks something like this:

Sorted array: [3,4,4,7,11]

1:3 socks ---> 1:3 socks ---> 1:0 socks ---> 1:0 socks

2:4 socks ---> 2:4 socks ---> 2:1 socks ---> 2:1 socks

3:4 socks ---> 3:4 socks ---> 3:0 socks ---> 3:0 socks

4:7 socks ---> 4:0 socks ---> 4:0 socks ---> 4:0 socks

5:11 socks ---> 5:4 socks ---> 5:0 socks ---> 5:0 socks

------> total = 14 possible combinations of mismatched socks. This seems way too naive an approach. Does anyone have any ideas on how to optimize it ? I can post my code for this if necessary.

I think this method is incorrect because you're not subtracting the lowest count from the highest count. Consider 1, 20, 80, 81 - after 1st iteration you'd get 1, 20, 0, 1 and be unable to do much with the 20, and get the answer 82 with 18 socks left over (where the correct answer should've been 91 with no socks left over). — Brendan
@Brendan, that's not correct. In the example you gave the answer would be 82, and the remaining 18 socks would all be of the same color so they wouldn't count as part of the total. Or did I understand you wrong ? — A curious one
D'oh. My method is incorrect too. For a correct answer; after 1st iteration it might be 0, 20, 80, 80, after 2nd iteration it might be 0, 10, 70, 80, and after 3rd iteration it might be 0, 0, 70, 70. — Brendan

RaffleBuffle RaffleBuffle · Accepted Answer · 2017-11-01T04:02:30

I think the optimal solution can be found by examining all possible groupings of the different sock colors into 2 piles. For each such grouping p odd pairs of socks can be made, where p is the number of socks in the smallest pile. You want the grouping that gives the maximum p. You can generate all possible groupings of socks into 2 piles recursively.

Here's some Java code to illustrate:

public static void main(String[] args)
{
    int[] socks = {3,4,4,7,11};
    System.out.println(count(0, 0, socks, 0));
}

static int count(int a, int b, int[] socks, int i)
{
    if(i == socks.length)
    {
        return Math.min(a, b);
    }

    return Math.max(count(a+socks[i], b,          socks, i+1), 
                    count(a,          b+socks[i], socks, i+1));
}

Output:

Calculating total number of mismatched socks combinations

3 Answers