Uncategorized

GCJ Africa 2010 - Reverse Words

The Reverse Words problem in the qualification round of Google Code Jam Africa 2010 is trivial. You are given a bunch of space separated words that you need to re-order (just the words, not the characters within the words). The number of words is, at most, 1000 so doing everything in memory is entirely feasible on a modern computer. Just be sure to watch out for the separating spaces in the result. You don't want any leading/training spaces.

Here's some simple C# code that solves it [running time is O(n) for n words. Space required is solely to hold the input values plus a small constant overhead to build the result]:

using System;

using System.IO;

using System.Text;

 

namespace GoogleCodeJam.Africa2010.ReverseWords

{

    class Program

    {

        static void Main()

        {

            const string basePath = @"C:\";

            var infile = new StreamReader(basePath + "B-large-practice.in");

            var outfile = new StreamWriter(basePath + "output.txt");

 

            int n = Int32.Parse(infile.ReadLine());

            for (int caseNo = 1; caseNo <= n; caseNo++)

            {

                var words = infile.ReadLine().Trim().Split(new []{' '});

                var answer = new StringBuilder();

                for (int i = words.Length-1; i >= 0; i--)

                    answer.Append(" " + words[i]);

 

                outfile.WriteLine("Case #{0}: {1}",

                                    caseNo, answer.ToString().Trim());

            }

            infile.Close();

            outfile.Close();

        }

    }

}

Uncategorized

GCJ Africa 2010 - T9 Spelling

The T9 Spelling problem in the qualification round of Google Code Jam Africa 2010 is, like the other problems in this round, fairly trivial. For some given text sequences you need to map them to key presses on a numeric key pad provided. You just need to look through each character provided and replace it with the appropriate key press sequence. Here I'm making use of a dictionary to ensure constant time lookup operations for mapping characters to key press sequences, and I track the last key pressed so I know when to insert a "pause" (denoted by a 0).

Here's some simple C# code that solves it [running time is O(n) for strings of size n]:

using System;

using System.Collections.Generic;

using System.IO;

using System.Text;

 

namespace GoogleCodeJam.Africa2010.T9Spelling

{

    class Program

    {

        static void Main()

        {

            const string basePath = @"C:\";

            var infile = new StreamReader(basePath + "large.txt");

            var outfile = new StreamWriter(basePath + "output.txt");

 

            var map = new Dictionary<string, string>

                          {

                              {"a", "2"},

                              {"b", "22"},

                              {"c", "222"},

                              {"d", "3"},

                              {"e", "33"},

                              {"f", "333"},

                              {"g", "4"},

                              {"h", "44"},

                              {"i", "444"},

                              {"j", "5"},

                              {"k", "55"},

                              {"l", "555"},

                              {"m", "6"},

                              {"n", "66"},

                              {"o", "666"},

                              {"p", "7"},

                              {"q", "77"},

                              {"r", "777"},

                              {"s", "7777"},

                              {"t", "8"},

                              {"u", "88"},

                              {"v", "888"},

                              {"w", "9"},

                              {"x", "99"},

                              {"y", "999"},

                              {"z", "9999"},

                              {" ", "0"}

                          };

 

            int n = Int32.Parse(infile.ReadLine());

            for (int caseNo = 1; caseNo <= n; caseNo++)

            {

                var msg = infile.ReadLine();

                var answer = new StringBuilder();

                int last = -1;

                for (int i = 0; i < msg.Length; i++)

                {

                    string mapped = map[msg[i].ToString()];

                    if (mapped[0] == last)

                        answer.Append(" ");

 

                    answer.Append(mapped);

                    last = mapped[0];

                }

                outfile.WriteLine("Case #{0}: {1}",caseNo, answer);

            }

            infile.Close();

            outfile.Close();

        }

    }

}

Uncategorized

GCJ Africa 2010 - Store Credit

The Store Credit problem in the qualification round of Google Code Jam Africa 2010 is relatively straight forward. You are given a collection of priced items and a credit limit. You are also told that 2 items will exactly add up to given credit limit thus you must find which two items can be purchased. To solve it, just keep a Dictionary (hash table) of prices with the index of the item that carries that price as you traverse the price listing. By doing this you can work out - in constant time - if the "complementary price", that is the price that takes you up to the credit limit, is in the list and if so what it's index is. Furthermore the program bails out as soon as it has found the item pair that satisfies the credit limit. We know this approach must terminate with a feasible solution because the problem states that there is guaranteed to be exactly one pair that solves the problem. Just be careful with your indexes here. Collections in C# and Java are zero-based, but this item list is a 1-based list [you can tell that from the examples given in the problem definition] so you need to be a bit careful with your indexes.

Here's some simple C# code that solves it [running time is O(n) for a list of n items]:

using System;

using System.Collections.Generic;

using System.IO;

 

namespace GoogleCodeJam.Africa2010.StoreCredit

{

    class Program

    {

        static void Main()

        {

            const string basePath = @"C:\";

            var infile = new StreamReader(basePath + "large.txt");

            var outfile = new StreamWriter(basePath + "output.txt");

 

            int n = Int32.Parse(infile.ReadLine());

            for (int caseNo = 1; caseNo <= n; caseNo++)

            {

                int C = Int32.Parse(infile.ReadLine()); // credit

                int I = Int32.Parse(infile.ReadLine()); // item count

                var P = infile.ReadLine().Split(new[] { ' ' }); // prices

                var priceIndexMap = new Dictionary<int, int>();

                int k = -1;

                int j = 0;

                for (; j < P.Length; j++ )

                {

                    int currentPrice = Int32.Parse(P[j]);

                    if (priceIndexMap.ContainsKey(C - currentPrice))

                    {

                        k = priceIndexMap[C - currentPrice];

                        break;

                    }

                    if (!priceIndexMap.ContainsKey(currentPrice))

                        priceIndexMap.Add(currentPrice, j + 1);

                }

                j++;

                if (j < k)

                    outfile.WriteLine("Case #{0}: {1} {2}", caseNo, j, k);

                else

                    outfile.WriteLine("Case #{0}: {1} {2}", caseNo, k, j);

            }

            infile.Close();

            outfile.Close();

        }

    }

}

Next »