Internet Problem Solving Contest

IPSC 2001

Solution to Problem C – Candies

One possible solution to this problem is using Microsoft Excel (or a Unix awk and sort command, which can be even faster).

The idea is that for each type of candy, we only need to consider at most three candidate bags, namely three bags with maximum number of candies of that type.

Thus I found a solution to both inputs like this:

  1. Import the input file into Excel; you get a nice three column table.
  2. Attach bag numbers to each record, for example using a macro like this:
    Sub my_simple_macro()
        For i = 1 To 500 Step 1
          Cells(i, 4).Value = i
        Next i
    End Sub
  3. Sort the rows by the first, second and third column in descending order. Always record the first three lines. For the easy input you will get something like this:

    Chocola Strawbe Banana  Bag#
    10771   7194    4593    388    (Sorted by Chocolate)
    10734   10472   9841    180
    10732   5926    9957    372
    4712    10749   10748   411    (Sorted by Strawberry)
    4531    10745   10352   458
    8063    10700   6794    253
    4712    10749   10748   411    (Sorted by Banana)
    7792    2500    10696   59
    3313    4136    10682   424
  4. Now look at what you've got. Bag 388 contains most Chocolate candies and is not in the first three places for Strawberry nor Banana candies. Thus we can safely assign bag 388 to Chocolate. Bag 411 is the most popular for both Strawberry and Banana. Since the difference between the first and second option (bag 411 vs. 458) for Strawberry is smaller than the difference between the first and second option (411 vs. 59) for Banana, we assign bag 411 to Banana and bag 458 to Strawberry.

In fact, what we've done in the previous step is called minimum-cost (or rather maximum-cost) matching. As you see, small instances like this can be solved pretty efficiently just by common sense.

P.S. Something for those more Unix inclined: the same output as shown above can be achieved by this (rather lengthy) command:

awk 'BEGIN{i=0} {if (i>0) printf "%5d %5d %5d %4d\n",\
$1,$2,$3,i; i++}' c1.in | sort -k1 -nr -g | head -3

This prints the first three, i.e. Chocolate rows, if you want the Strawberry and Banana rows, you need to change the -k1 parameter of sort to -k2 and -k3 respectively.