Necessary and Sufficient

Code Jam 2010 started with a qualification round that was harder than previous years. The first problem, Snapper Chain, involves a series of N switches arranged in sequence, that toggle when you snap your fingers if they are receiving power. The problem asks that you indicate if a light plugged into the end of the chain of N switches will be on after K toggles. A brute force evaluation of the state of the light would have a run time ~ O(NK). This isn't feasible since the upper limits on N and K are 30 and 10⁸ respectively. That would take far too long to evaluate. Intuitively you know there must be some sort of pattern so in an effort to get clarity on it it's best to list the states for some toggles. So let's start with N=5 and see what we find...

Now it becomes clear how things work. The first switch toggles with every snap so it's immediately obvious that after an even number of snaps the light cannot be on. Conversely, if N=1 then the light would be on for all odd values of K. If N=2, then we can see that the light would be on when K=3, 7, 11, 15, 19, 23 27,31. That seems to be a pattern with common increments of 4. If N=3, the light would be on when K=7,15, 23,31 - common increments of 8. And for N=4, the light is on when K=15,31 - an increment of 16. It seems that the increments are powers of two. In other words, for a given N and K we can hypothesize that the light is only on when K satisfies the following formula:

Here c is any non-negative integer. In other words, the light is on after a certain number of snaps and it comes back on after a cycle of 2^N more snaps. Since N << K the summation term here is not a major concern. It is in fact the sum of a geometric progression so the summation could be replaced with a simpler term but since N is fairly small (<30) I didn't bother to optimise it further. I did add memoization to remember the sum of N items so we only ever need to calculate the sum of 30 items once. Here's some C# code to solve the problem:

   1:  using System;

   2:  using System.Collections.Generic;

   3:  using System.IO;

   4:   

   5:  namespace GoogleCodeJam2010.Qualificiation.SnapperChain

   6:  {

   7:      class Program

   8:      {

   9:          static void Main()

  10:          {

  11:              const string basePath = @"";

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

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

  14:   

  15:              var termSum = new Dictionary<int, ulong>();

  16:              var cycle = new ulong[31];

  17:              ulong sum = 0;

  18:              ulong current = 1;

  19:              for (int i = 0; i < 31; i++)

  20:              {

  21:                  sum = sum + current;

  22:                  termSum[i] = sum;

  23:                  current = current * 2;

  24:                  cycle[i] = current;

  25:              }

  26:              

  27:              int t = Int32.Parse(infile.ReadLine());

  28:              for (int caseNo = 1; caseNo <= t; caseNo++)

  29:              {

  30:                  var data = infile.ReadLine().Split(' ');

  31:                  int n = Int32.Parse(data[0]);

  32:                  ulong k = UInt64.Parse(data[1]);

  33:   

  34:                  string answer = "OFF";

  35:   

  36:                  if ((k - termSum[n-1]) % cycle[n-1] == 0)

  37:                      answer = "ON";

  38:   

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

  40:              }

  41:              infile.Close();

  42:              outfile.Close();

  43:          }

  44:      }

  45:  }

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]:

The Burrows-Wheeler Transform is a well-known text transformation that is used to pre-condition strings prior to compression. It's used by the popular bzip2 utility in Linux. To be more specific, it is a lossless block-sorting algorithm. It was invented by Mike Burrows (now at Google) and David Wheeler who advise that the size of the input block must be a few KBs to achieve good compression. It is a surprising simple algorithm to describe and has the remarkable property of being easily reversible. Let's look at some code in C#...

The Encode() method in lines 6-21 takes a given string and creates every cyclic permutation of the string in lines 9-12. It then does a lexicographical sort of this new list of strings. I chose an ordinal search to achieve the same interim results published on Wikipedia using "^BANANA@" as the string to transform (here "@" is an EOF marker). If you use the default Array.Sort() parameters in .NET the sort will be culture-sensitive which means the caret sign "^" will be ordered before alpha characters for most English-speaking cultures. See this article for a review of linguistic and ordinal string operations. But in reality you can use any sort variant here as long as you use the same approach in the Decode() method.

Lines 16-20 then create a new string of the same length by concatenating the last character in each string in the sorted list. The resulting text contains all of the characters that were in the original string differing only in their ordering. It is in fact a collection of prefix characters to the first characters of each word in the sorted list.

To decode the string we perform a series of Add+Sort operations as follows: take the given (transformed) string and make a list of new strings making the first character of each respective string in the list equal to the characters of the given string, then sort them. We then start the process again adding the characters of the given string as their new first character, sort them, etc until you have strings of the same length as the original. At that point you can identify the original by looking for the string with the EOF marker in it's rightful place - at the end.

Since the BWT is designed to work on files in memory we need to optimize this naive implementation to be more memory efficient. If the text block is large, as the authors recommend, then the list of all permutations created in the Encode() method is going to be wasteful with memory. This issue, and a few others will be something I'll explore in Part 2 of this series...