Necessary and Sufficient

Round 1A of Google Code Jam 2008 has a problem called Minimum Scalar Product which, as the name suggests, asks that you find the minimum scalar product of 2 equally-sized vectors. When I read this problem my thoughts immediately went to the golf course. Why? Because if you're a member of a golf club you'll invariable come upon a competition format called 4-Ball Stableford multipler. Simply put, 2 players play as a team and each get a stableford (points) score for each hole, but the team score for each hole is recorded as the product of each players score on that hole with the team with the most point winning. i.e if PlayerA gets 4 points and PlayerB gets 2 points on a given hole, the team score for that hole is 8 points (= 4 x 2). Why am I telling you this? Well the secret to getting the best team score in a 4-Ball Stableford multiplier is to co-ordinate your good holes and your poor holes with your partners' good and bad scoring holes. In order words, to maximise the team score, each player should not only play well but play well on the same holes that their team-mate plays well on. The Google challenge posed here is effectively the same problem with the difference that they ask for the minimum product, rather than the maximum product that you seek on the golf course in the competition format described above.

Once you figure this out it's a simple problem to code. Get 2 vectors/lists and order one in ascending order, and order the other in descending order. There's no great need to procrastinate over which sort algorithm to use, and whether or not to replace the one provided by the .Net framework with your own - you'll be able to solve both the small and large problem with the code shown below:

using System;
using System.IO;
using System.Collections.Generic;

namespace GoogleCodeJam.ScalarProduct
{
    class Program
    {
        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader(basePath + "large.txt");
            StreamWriter outfile = new System.IO.StreamWriter(basePath + "output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read in the input data
                int vectorSize = Int32.Parse(infile.ReadLine());

                List<long> vector1 = new List<long>();
                List<long> vector2 = new List<long>();

                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                foreach (string s in data) { vector1.Add(Int64.Parse(s)); }

                data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                foreach (string s in data) { vector2.Add(Int64.Parse(s)); }

                vector1.Sort();
                vector2.Sort();
                vector2.Reverse();

                long minProduct=0;
                for(int i=0; i< vector1.Count; i++ )
                {
                    minProduct += vector1[i] * vector2[i];
                }

                // write out the results
                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, minProduct));
            }

            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}