Necessary and Sufficient

Round 2 kicked off with a simple sorting problem. We are given a matrix of zeros and ones and we need to find the least cost sort of the rows such that there are no ones to the right of the main diagonal with the constraint that only adjacent rows can be swapped.

Since we are only concerned with ones to the right of the main diagonal we only care about the last one in each row, thus when we read in the input we only store the index of the rightmost one. The problem then reduces to sorting this array using only adjacent cell swaps.

I employed a simple greedy algorithm to do this. Starting at row 1, check if it is ok, if not find the first "unallocated" row that could be placed in row 1, then shift this up counting the swaps as we go. The process then moves onto the next row and repeats the process until there are no more rows to sort.

Here's my C# code to solve it:

using System;
using System.IO;

namespace GoogleCodeJam.CrazyRows
{
    class Program
    {
        static void Main()
        {
            const string basePath = "";
            var infile = new StreamReader(basePath + "large.txt");
            var outfile = new StreamWriter(basePath + "output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++)
            {
                int N = Int32.Parse(infile.ReadLine());
                var values = new int[N];
                for (int i = 0; i < N; i++)
                    values[i] = infile.ReadLine().LastIndexOf('1');

                int ans = 0;
                for (int i = 0; i < N; i++)
                {
                    int k = 0;
                    while (values[i+k] > i)
                        k++;

                    for (int j = k; j >0; j--)
                    {
                        int temp = values[i+j];
                        values[i+j] = values[i+j-1];
                        values[i+j-1] = temp;
                        ans++;
                    }
                }
                outfile.WriteLine("Case #{0}: {1}", caseNo, ans);
            }
            infile.Close();
            outfile.Close();
        }
    }
}

And here's my C++ code to solve it:

#include <string>
#include <iostream>

using namespace std;

static void main()
{
    string basePath = "";
    string inFile = basePath + "large.txt";
    string outFile = basePath + "output.txt";

    freopen(inFile.c_str(),"r",stdin);
    freopen(outFile.c_str(),"w",stdout);

    int testCases; cin >> testCases;
    for (int caseNo = 1; caseNo <= testCases; caseNo++)
    {
        int N; cin >> N;
        int values[41];
        for (int i = 0; i < N; i++)
        {
            string M; cin >> M;
            int z = M.find_last_of('1');
            values[i] = z;
        }
        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            int k = 0;
            while (values[i+k] > i)
                k++;

            for (int j = k; j >0; j--)
            {
                int temp = values[i+j];
                values[i+j] = values[i+j-1];
                values[i+j-1] = temp;
                ans++;
            }
        }
        cout << "Case #" << caseNo << ": " << ans << endl;
    }
}

The last puzzle in Round 1C was the Bribe the Prisoners puzzle. In this puzzle we have P consecutive prison cells each of which has exactly 1 prisoner in it, and a list of q prisoners to be released. When a prisoner from this list is released all other prisoners in the block bounded by empty cells, or the end of the section, riot and therefore need to be bribed.

Since this is a combinatorial optimisation problem we could enumerate through all possible combinations of prisoner release schedules but this results in q! run time which is not feasible when q=100. It is, of course, feasible for small problems (q=5) but going that route is only painting yourself into a corner IMHO.

So let's consider what happens when we release a prisoner. Say we initially start with a release list {q₁, q₂, q₃,...,q_Q} where 1 <= q_i <=P for all i; and we choose q_j to be released first. The block of P previously consecutive cells now has a break in it at position j resulting in 2 blocks: [1, (j-1)], and [(j+1), P]. Furthermore it's obvious that the list of prisoners to be released can be partitioned into 2 lists: those less than j, and those greater than j, since only those prisoners in the containing, unbroken cell block need to be considered when evaluating the optimal release plan for the newly created block. The 2 sub-problems created are in fact the same sort of problem we initially had, and thus a recursive approach can be used to find the minimum-cost solution. In essence we have overlapping sub-problems and an optimal substructure. This implies that dynamic programming can be used.

With that in mind let's define c_i,j to be the minimum cost of releasing all prisoners in the release list given that prisoner q_i and q_j have been released. Since the list of Q prisoners to be released is given to us in increasing order we can augment this list with 2 dummy prisoners, located before the first cell, and after the last cell and mark them as already released to make dealing with boundary conditions easier. [This is what lines 30 and 31 below perform.] Our problem now reduces to finding c_1,Q, but we still need to define a strategy for calculating c_i,j.

Assume that you have multiple prisoners to be released between q_i and q_j, and, as per the above definition of c_i,j, q_i and q_j have already been released. The cost of releasing the first prisoners in this block is going to be (q_j-q_i -2) regardless of which prisoner is released first. However, the cost of releasing subsequent prisoners is going to be affected by this decision. Thus the optimal (minimum) release cost can be calculated by :

where z is one of the values provided in set Q.

As well, because we have overlapping sub-problems it's sensible to use function memoisation and since C# supports nullable data types we need not initialize the cache - it will be auto-initialized to null and we use the null value to indicate the function value hasn't yet been assigned.

The astute reader will note that the problem is now stated in terms of Q rather than P. This is highly desirable since P >> Q and you'll find, as I did, that you run into memory problems if you leave the problem in terms of P.

The C# code is shown below:

   1:  using System;

   2:  using System.IO;

   3:   

   4:  namespace GoogleCodeJam.BribeThePrisoners

   5:  {

   6:      class Program

   7:      {

   8:          private static int?[,] answers;

   9:          private static int[] pardoned;

  10:   

  11:          static void Main()

  12:          {

  13:              var basePath = "";

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

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

  16:   

  17:              int testCases = Int32.Parse(infile.ReadLine());

  18:              for (int caseNo = 1; caseNo <= testCases; caseNo++)

  19:              {

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

  21:                  int P = Int32.Parse(data[0]), Q = Int32.Parse(data[1]);

  22:                  answers = new int?[Q + 1,Q + 1];

  23:                  pardoned = new int[Q + 2];

  24:                  int i = 1;

  25:                  foreach (var item in (infile.ReadLine()).Split(' '))

  26:                  {

  27:                      pardoned[i] = Int32.Parse(item);

  28:                      i++;

  29:                  }

  30:                  pardoned[0] = 0;

  31:                  pardoned[Q+1] = P+1;

  32:                  outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, MinCost(1,Q)));

  33:              }

  34:              infile.Close();

  35:              outfile.Close();

  36:          }

  37:   

  38:          static int MinCost(int start, int finish)

  39:          {

  40:              if (finish - start < 0)

  41:                  return 0;

  42:   

  43:              if (answers[start,finish].HasValue)

  44:                  return answers[start,finish].Value;

  45:              

  46:              int min = Int32.MaxValue;

  47:              for (int k = start; k <= finish; k++)

  48:                  min = Math.Min(min, pardoned[finish+1]-pardoned[start-1]-2 + 

  49:                                       MinCost(start, k - 1) + MinCost(k + 1, finish));

  50:              

  51:              answers[start, finish] = min;

  52:              return min;

  53:          }

  54:      }

  55:  }

And for good measure, here's my C++ code:

#include <algorithm>
#include <string>

using namespace std;

int answers[101][101];
int pardoned[102];

int minCost(int start, int finish)
{
    if (finish - start < 0)
        return 0;

    if (answers[start][finish] != -1)
        return answers[start][finish];

    int minimum = 1<<30;
    for (int k = start; k <= finish; k++)
        minimum = min(minimum, pardoned[finish+1]-pardoned[start-1]-2 
                 + minCost(start, k - 1) + minCost(k + 1, finish));

    answers[start][finish] = minimum;
    return minimum;
}

void main()
{
    string basePath = "";
    string inFile = basePath + "large.txt";
    string outFile = basePath + "output.txt";

    freopen(inFile.c_str(),"r",stdin);
    freopen(outFile.c_str(),"w",stdout);

    int testCases;
    scanf("%d", &testCases);
    for (int caseNo = 1; caseNo <= testCases; caseNo++)
    {
        int P, Q;
        scanf("%d %d", &P, &Q);

        for(int i=0; i<Q+1; i++)
            for(int j=0; j<Q+1; j++)
                answers[i][j] = -1;

        pardoned[0] = 0;
        pardoned[Q+1] = P+1;
        int i;
        for (i = 1; i <= Q; i++)
            scanf("%d", &pardoned[i]);

        printf("Case #%d: %d\n", caseNo, minCost(1, Q));
    }
}

The first puzzle in Round 1C was the All Your Bases puzzle. This puzzle requires you to examine a given string literal and return the lowest possible numeric value that can be made from it. The string is a character pattern that represents a number but we don't know what base it is in. The obvious way to solve this puzzle is to:

1. Count the number of distinct characters in the string. This must be the base to use that produces the lowest possible number. To see this consider a 4 digit number "wxyz". If this is in base b, then the value of wxyz is: w.b³+x.b²+y.b¹+z.b⁰. Since we have 4 distinct digits the base, b >= 4. If we go with b=4 then the value resulting from the above expression is clearly going to be less than the value resulting from any higher value of b. One gotcha: if the count=1 then you need to bump it up to 2 since we are explicitly told that unary (base-1) is not used.

2. For the baseToUse found above, create a sequence of digits from that base in increasing order. Since all bases have a 0, but we are told no numbers in the test data include leading zeros, we must start this sequence with 1, then 0, then 2, 3, 4... up to (baseToUse-1).

3. Starting at the left of the string (the problem doesn't specify if the aliens use left-right or right-left notation but the sample problem implies left-right is used. Given the nature of the problem - finding out the earliest possible start time for the war - this is a rather dangerous assumption and so I pointed it out to Google. See the comment at the bottom) we assign the first unused digit from the list constructed above for each character represented by the char in the position being examined.

4. Since you know the baseToUse, and the digits in each position it is easy to calculate the base10 equivalent of the number created. One gotcha here: the numbers are going to get very large so don't get caught out using floating point functions that silently lose precision when they get too big (that issue has bitten me more often than I care to admit). Use an integer type all the way.

UPDATE: the official analysis from the first round of CodeJam is out and the problem creator, Bartholomew Furrow of Google, acknowledged my observation that perhaps this problem makes a somewhat dangerous assumption. That said, I am envious of his terse solution in Python. Make my C# code look really verbose. Note to self: go learn Python TOMORROW.

The C# code is shown below:

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

namespace GoogleCodeJam.AllYourBases
{
    class Program
    {
        static void Main()
        {
            string basePath = @"D:\";
            var infile = new StreamReader(basePath + "large.txt");
            var outfile = new StreamWriter(basePath + "output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++)
            {
                string message = infile.ReadLine().Trim();
                ulong minSeconds = UInt64.MaxValue;
                int startBase = CountDistinct(message);
                if (startBase == 1)
                    startBase++;

                minSeconds = message.Length ==1 ? 1 : FindMinimum(startBase, message);

                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, minSeconds));
            }
            infile.Close();
            outfile.Close();
        }

        //returns a base10 number
        static ulong FindMinimum(int baseUsed, string message)
        {
            message = message.Trim();
            var digits = new List<int> {1, 0};
            for (int d = 2; d < baseUsed; d++)
                digits.Add(d);

            ulong ans = 0;
            foreach (var c in GetDistinctInOrder(message))
            {
                int index = message.IndexOf(c);
                while (index >=0)
                {
                    ans += (ulong)digits[0] * Power( baseUsed, message.Length - (index + 1));
                    index = message.IndexOf(c,index+1);
                }
                digits.RemoveAt(0);
            }
            return ans;
        }

        static ulong Power(int baseUsed, int exponent)
        {
            ulong answer = 1;
            for(int i=0; i<exponent; i++)
                answer *= (ulong)baseUsed;

            return answer;
        }

        static List<char> GetDistinctInOrder(string input)
        {
            input = input.Trim();
            var seen = new List<char>();
            for (int i = 0; i < input.Length; i++)
            {
                if (!seen.Contains(input[i]))
                    seen.Add(input[i]);
            }
            return seen;
        }

        static int CountDistinct(string input)
        {
            return GetDistinctInOrder(input).Count;
        }
    }
}

And here's my unpolished C++ code to do the same:

#include <string>
#include <iostream>

using namespace std;

char seen[256];
char seenOrder[256];

long long Power(int baseUsed, int exponent)
{
    long long answer = 1;
    for(int i=0; i<exponent; i++)
        answer *= baseUsed;
    return answer;
}

//returns a base10 number
long long findMinimum(int baseUsed, string* msg)
{
    int digits[36];
    memset(digits,0,sizeof(digits));
    digits[0]=1;
    digits[1]=0;
    for (int d = 2; d < baseUsed; d++)
        digits[d]=d;

    long long ans = 0;
    for(int i=0; i < baseUsed; i++)
    {
        char c = seenOrder[i];
        int index = msg->find(c);
        while (index != string::npos)
        {
            ans += digits[i] * Power( baseUsed, msg->length() - (index + 1));
            index = msg->find(c,index+1);
        }
    }
    return ans;
}

void main()
{
    string basePath = "";
    string inFile = basePath + "large.txt";
    string outFile = basePath + "output.txt";

    freopen(inFile.c_str() , "r", stdin);
    freopen(outFile.c_str(), "w", stdout);

    int testCases;
    cin >> testCases;

    for (int caseNo = 1; caseNo <= testCases; caseNo++)
    {
        long long minSeconds = 0;

        string message;
        cin >> message;

        memset(seen,0,sizeof(seen));
        memset(seenOrder,0,sizeof(seenOrder));
        int startBase=0;
        for (int i = 0; i < message.length(); i++)
        {
            char c = message[i];
            if (seen[c] == 0) //not seen before
            {
                seen[c] = 1;
                seenOrder[startBase] = c;
                startBase++;
            }
        }
        if (startBase == 1) startBase++;

        minSeconds = (message.length() == 1) ? 1 : findMinimum(startBase, &message);

        printf("Case #%d: %lld\n", caseNo, minSeconds);
    }
}