Necessary and Sufficient

Round 1C began with the "Text Messaging Outrage" problem which basically asks that we identify the most efficient letter-to-key assignment on a phone to minimize the number of key presses needed by users. Google quite helpfully provide a frequency distribution for each letter. Given the frequency distribution it's obvious what the optimal assignment is - for the letters that are most frequently used assign them key press combinations that require the fewest key presses. Technically speaking this is a greedy approach and it should be intuitively obvious why it produces the optimal assignment.

This was one of the easiest problems encountered so far! Here's the code in C#:

using System;
using System.IO;

namespace GoogleCodeJam.TextMessage
{
    class Program
    {
        static void Main()
        {
            string basePath = "";
            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
            {
                long minKeyPressCount = 0;

                // read in the input data
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                int P = Int32.Parse(data[0]); // max number of letters to place on a key
                int K = Int32.Parse(data[1]); // number of keys available
                int L = Int32.Parse(data[2]); // number of letters in the alphabet

                // read in the letter frequencies
                int[] frequencies = new int[L];
                int[] indexes = new int[L];

                string[] freqData = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                int i = 0;
                foreach (string s in freqData)
                {
                    indexes[i] = i;
                    frequencies[i] = Int32.Parse(s);
                    i++;
                }

                int nextKfree = 0;      // the one-based index of the key with the next lowest key press combo
                int nextPfree = 1;      // the one-based index of the letter on the "low key" with the next lowest key press combo

                // map the most used letters to the shortest key press routines available
                Array.Sort(frequencies,indexes);    // ~ O(n log n) on average since it uses an unstable QuickSort internally
                Array.Reverse(frequencies);         // ~ O(n)
                Array.Reverse(indexes);             // ~ O(n)
                int ii = 0;
                foreach (int x in indexes)  // from greatest- to least-used index
                {
                    // find the next available key press combo walking through from cheapest to dearest
                    nextKfree++;
                    if (nextKfree > K)
                    {
                        nextKfree = 1;
                        nextPfree++;
                    }
                    checked
                    {
                        minKeyPressCount += (frequencies[ii] * nextPfree);
                    }
                    ii++;
                }

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