Archive for September, 2009

Uncategorized

Google Code Jam 2009: Crazy Rows

Google Code JamRound 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;
    }
}

Uncategorized

Google Code Jam 2009: Bribe the Prisoners

Google Code JamThe 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 {q1, q2, q3,...,qQ} where 1 <= qi <=P for all i; and we choose qj 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 ci,j to be the minimum cost of releasing all prisoners in the release list given that prisoner qi and qj 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 c1,Q, but we still need to define a strategy for calculating ci,j.

Assume that you have multiple prisoners to be released between qi and qj, and, as per the above definition of ci,j, qi and qj have already been released. The cost of releasing the first prisoners in this block is going to be (qj-qi -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)); } }

Uncategorized

Google Code Jam 2009: Collecting Cards

Google Code JamThe last problem in Round 1A was the "Collecting Cards" problem which is a simply-stated problem but requires some understanding of combinatorics to solve. Basically, there are C distinct cards in a collection and you need to figure out how many packs of N distinct cards you need to buy in order to have the complete set assuming you started with none.

Firstly, some basic observations:

  • Since order is irrelevant, we are dealing with combinations not permutations.
  • Combinatorics tells us that there are CCN distinct combinations, all of which are equally likely.
  • Since we start with nothing we must always buy at least 1 pack.
  • The theoretical minimum number of packs that we would need would only occur when every pack we bought had completely new cards in it (rather unlikely). That is, absolute lower limit is:

  • We need to account for the likelihood that in packs purchased we are going to see an percentage of cards we already have. Dealing with this is the crux of the problem.

Background on Combinations
Note that xCy can also be written as:

and, choosing y items from a population of x items is equivalent to choosing x-y items. That is:

Clearly there is only 1 combination of xitems in a population of x, and by the above rule there is only 1 combination of zero items (that confuses many people!). That is:

Problem Solution
To solve this problem let us define f(k) be the expected number of packs we need to buy if we still need k cards (i.e we already have C-k distinct cards). To solve the problem we just need to find f(C). It is also obvious that f(0)=0, and f(C) = 1 + f(C-N) since we are guaranteed to get N distinct new cards when we purchase the first pack. What we now need is a generic formula for f(k) that we can use in a recursive fashion.

When we need k (distinct) cards, it follows that we must already have (C-k) distinct cards. Thus purchasing an additional pack of N cards can result in 0, 1, 2, 3, ..., min(N, k) new cards being collected. If we let pj,m be the probability of getting j new cards from an additional pack of N randomly-drawn cards, given that we already have m distinct cards, then we can say:

To calculate pj,m we simply need to figure out how many packs would have j cards that we don't already have and (N-j) cards that we do have, divided by the total number of possible pack combinations. In other words:

To efficiently compute the combinations we make use of the well-known property of Pascal's Triangle - the
[i,j] coefficient is the sum of the 2 co-efficients "above" it. This recursive definition can be stated formally as,

Since we know that N<=C<=40 we can go ahead and pre-compute these storing them in a 2-dimensional array.

Substituting for pj,C-k in our formula for f(k) yields:

But there is a problem here. If you use the above formula as is you'll hit a stack overflow as I did (dohh!) because you're creating an infinite loop due to f(k) being on both sides of the equation. To remedy this we need to revise our equation as follows (we took out the j=0 case in the summation and ensured that f(k) only appears on the LHS):

Holly cat fish , Batman! Who would have though collecting cards was so complicated :-)

Here's the C# code to implement the above mess, errr equation:

using System;
using System.IO;

namespace CollectingCards
{
    class Program
    {
        private static readonly ulong[,] choose = new ulong[41,41];
        private static double?[] solved;
        private static int C,N;

        static void Main()
        {
            const string basePath = "";
            var infile = new StreamReader(basePath + "small.txt");
            var outfile = new StreamWriter(basePath + "output.txt");

            for (int i=0; i<41; i++)
            {
                choose[i, i] = 1;
                choose[i, 0] = 1;
                for (int j=1; j<i; j++)
                    choose[i,j] = choose[i-1,j] + choose[i-1,j-1];
            }

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++)
            {
                string[] data = (infile.ReadLine()).Split(' ');
                C = Int32.Parse(data[0]);
                N = Int32.Parse(data[1]);
                solved = new double?[41];

                outfile.WriteLine("Case #{0}: {1:#.00000}", caseNo, Solve(C));
            }
            infile.Close();
            outfile.Close();
        }

        static double Solve(int k)
        {
            if (k == 0)
                return 0;

            if (solved[k].HasValue)
                return solved[k].Value;

            double factor = 1.0/(1.0-(double)choose[C-k,N]/choose[C,N]);
            double ans = 1;
            for (int j = 1; j <= Math.Min(N, k); j++)
            {
                if (k - j == 0) continue;
                double p = (double)(choose[k, j] * choose[C - k, N - j]) / choose[C, N];
                if (p != 0)
                    ans += p*Solve(k - j);
            }
            ans *= factor;
            solved[k] = ans;
            return ans;
        }
    }
}

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

#include <iostream>
#include <string>

using namespace std;

long long choose[41][41];
int C;
int N;
double solved[41];

double Solve(int k)
{
    if (solved[k] != -1)
        return solved[k];

    double factor = 1.0/(1.0-(double)choose[C-k][N]/choose[C][N]);
    double ans = 1;
    int minVal = min(k,N);
    for (int j = 1; j <= minVal; j++)
    {
        if (k - j == 0) continue;
        double p = (double)(choose[k][j] * choose[C - k][N - j]) / choose[C][N];
        if (p != 0)
            ans += p*Solve(k - j);
    }
    ans *= factor;
    solved[k] = ans;
    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);

    for (int i=0; i<41; i++)
    {
        choose[i][i] = 1;
        choose[i][0] = 1;
        for (int j=1; j<i; j++)
            choose[i][j] = choose[i-1][j] + choose[i-1][j-1];
    }

    int testCases; cin >> testCases;
    for (int caseNo = 1; caseNo <= testCases; caseNo++)
    {
        cin >> C >> N;
        for(int i=0; i<41;i++)
            solved[i]=-1;

        cout << "Case #" << caseNo << ": " << Solve(C) << endl;
    }
}

Next »