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;
    }
}