Google Code Jam 2016 Round 1A 2016 Problem B. Rank and File

// Google Code Jam 2016 Round 1A 2016 Problem B. Rank and File
// Problem URL: https://code.google.com/codejam/contest/4304486/dashboard#s=p1&a=0

#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <limits>

using namespace std;

typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;

//==================================
void solve()
{
    int numCases = 1;
    cin >> numCases;

    for ( int ncase=1; ncase <= numCases; ncase++ )
    {
        //===== start case
        int N;
        cin >> N;
        int num[2501];
        for (int i=0; i<=2500; i++)
            num[i]=0;
        int x;
        for (int i=0; i<2*N-1; i++) {
            for (int j=0; j<N; j++) {
                cin >> x;
                num[x]+=1;
            }
        }
        vector<int> v;
        for (int i=1; i<=2500; i++) {
            if (num[i]%2==1)
                v.push_back(i);
        }

        sort(v.begin(),v.end());

        cout << "Case #" << ncase << ": ";
        for (int i=0; i<N; i++) {
            cout << v[i] << " ";
        }
        cout << endl;

        //===== end case

    }
}

int main()
{
    solve();
    return 0;

}

Google Code Jam 2016 Round 1A 2016 A. The Last Word

// Google Code Jam 2016 Round 1A 2016
// Problem A. The Last Word
// Problem URL: https://code.google.com/codejam/contest/4304486/dashboard#s=p0&a=0


#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <limits>

using namespace std;

typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;

void solve()
{
    int numCases = 1;
    cin >> numCases;

    for ( int ncase=1; ncase <= numCases; ncase++ )
    {
        //===== start case
        string S;
        cin >> S;

        string ans=S.substr(0,1);
        for ( int i=1; i<S.size(); i++ )
        {
            if (S[i]>=ans[0])
                ans = S.substr(i,1) + ans;
            else
                ans = ans + S.substr(i,1);
        }
        cout << "Case #" << ncase << ": ";
        cout << ans << endl;

        //===== end case
    }
}

int main()
{
    solve();
    return 0;

}

Facebook Hacker Cup 2015 Qualification Round, Cooking the Books

Facebook Hacker Cup 2015 Qualification Round, Cooking the Books

Problem Statements:
https://www.facebook.com/hackercup/problem/582062045257424/

Solution:
We could solve the problem by testing all possible numbers when any 2 digits are swapped.
We swap position i and j for every possible i and j where 1<i<9 and 1<j<9, so the number of all possible combination is small enough for brute force attack.

Example codes:

            long T = inp.NextInt ( );
            for ( int t = 0; t < T; t++ )
            {
                long N = inp.NextLong ( );
                string sn = N.ToString ( );
                char[] cn = sn.ToCharArray ( );
                string ans = "";
                if ( N < 10 )
                {
                    ans = string.Format ( "{0} {1}", N, N );
                }
                else
                {
                    string snmin = sn;
                    string snmax = sn;
                    for ( int i = 0; i < sn.Length; i++ )
                    {
                        for ( int j = i + 1; j < sn.Length; j++ )
                        {
                            //swap then test
                            char[] cc = cn.ToArray ( );
                            char tmp = cc[i];
                            cc[i] = cc[j];
                            cc[j] = tmp;
                            string st = new string ( cc );
                            if ( st.CompareTo ( snmin ) < 0 && st[0] != '0' )
                                snmin = st;
                            if ( st.CompareTo ( snmax ) > 0 )
                                snmax = st;
                        }
                    }

                    ans = string.Format ( "{0} {1}", snmin, snmax );
                }

                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
            }

Facebook Hacker Cup 2015 Round 1, Winning at Sports

Problem Statement:
https://www.facebook.com/hackercup/problem/688426044611322/

Solution:
This could be solved by using dynamic programming.
Let's define dp[ i, j ] as the number of ways to reach the final score of i-j.

For the stress-free victory:
The base cases:
  dp[ i, 0 ] = 1, 1 <= i <= N
  dp[ 0, i ] = 0, 1 <= i <= N

The recurrence:
  dp[ i, j ] = 0,                                          if i <= j
  dp[ i, j ] = dp[ i-1, j ] + dp[ i, j-1 ],        if i > j

For the stressful victory:
The base cases:
  dp[ i, 0 ] = 1, 1 <= i <= N
  dp[ 0, i ] = 1, 1 <= i <= N

The recurrence:
  dp[ i, j ] = dp[ j, j ],                                if i > j
  dp[ i, j ] = dp[ i-1, j ],                            if i = j
  dp[ i, j ] = dp[ i-1, j ] + dp[ i, j-1 ],        if i < j

Example codes:

            int T = inp.NextInt ( );
            long mod = 1000000000 + 7;
            long[,] dpstressfree = new long[2001, 2001];
            long[,] dpstressfull = new long[2001, 2001];
            dpstressfree[0, 0] = 0;
            for ( int i = 1; i < 2001; i++ )
            {
                dpstressfree[i, 0] = 1;
                dpstressfree[0, i] = 0;
            }
            for ( int i = 1; i < 2001; i++ )
            {
                for ( int j = 1; j < 2001; j++ )
                {
                    if ( i <= j )
                        dpstressfree[i, j] = 0;
                    else
                    {
                        dpstressfree[i, j] = ( dpstressfree[i - 1, j] + dpstressfree[i, j - 1] ) % mod;
                    }
                }
            }

            dpstressfull[0, 0] = 1;
            for ( int i = 1; i < 2001; i++ )
            {
                dpstressfull[i, 0] = 1;
                dpstressfull[0, i] = 1;
            }
            for ( int i = 1; i < 2001; i++ )
            {
                for ( int j = 1; j < 2001; j++ )
                {
                    if ( i > j )
                        dpstressfull[i, j] = dpstressfull[j, j];
                    else if ( i == j )
                        dpstressfull[i, j] = dpstressfull[i - 1, j];
                    else
                    {
                        dpstressfull[i, j] = ( dpstressfull[i - 1, j] + dpstressfull[i, j - 1] ) % mod;
                    }
                }
            }

            for ( int t = 0; t < T; t++ )
            {
                string[] s = inp.NextString ( ).Split ( '-' );
                int A = int.Parse ( s[0] );
                int B = int.Parse ( s[1] );
                long ans1=dpstressfree[A, B];
                long ans2=dpstressfull[A, B];
                Console.WriteLine ( "Case #{0}: {1} {2}", t + 1, ans1, ans2 );
            }

Facebook Hacker Cup 2015 Round 1, Homework

Problem Statement:

https://www.facebook.com/hackercup/problem/582396081891255/

Solution:

First we generate the list of prime numbers between 2 and 10^7.
Then we calculate the primacity of each number between 2 and 10^7 and save the results into an array.
To calculate the primacity of all numbers, we set all primacities to zero, then for each prime number we increase the primacity of each multiple of that prime by 1.
At the end we will have the primacity of all numbers completely filled, and it will be easy to count the requested answer.

Example codes in C#:

            int T = inp.NextInt ( );
            List<int> primes = GetPrimes ( 10000000 );

            int[] prmCity = new int[10000001];
            for ( int i = 0; i < primes.Count; i++ )
            {
                int p = primes[i];
                for ( int pp = p; pp < prmCity.Length; pp+=p )
                {
                    prmCity[pp] += 1;
                }
            }

            for ( int t = 0; t < T; t++ )
            {
                int A = inp.NextInt ( );
                int B = inp.NextInt ( );
                int K = inp.NextInt ( );

                int cnt=0;
                for ( int i = A; i <= B; i++ )
                {
                    if ( prmCity[i] == K )
                        cnt++;
                }

                int ans=cnt;
                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
            }


        private static List<int> GetPrimes ( int maxPrimeNumber )
        {
            bool[] isPrime = GetIsPrime ( maxPrimeNumber );
            List<int> primes = new List<int> ( );
            for ( int i = 2; i < isPrime.Length; i++ )
            {
                if ( isPrime[i] )
                    primes.Add ( i );
            }
            return primes;
        }

        private static bool[] GetIsPrime ( int max )
        {
            // Sieve of Eratosthenes
            bool[] isPrime = new bool[max + 1];
            for ( int i = 0; i <= max; i++ )
                isPrime[i] = true;
            isPrime[0] = false;
            isPrime[1] = false;
            for ( int x = 2; x * x <= max; x++ )
            {
                if ( isPrime[x] )
                {
                    int xx = x;
                    while ( true )
                    {
                        xx += x;
                        if ( xx <= max )
                            isPrime[xx] = false;
                        else
                            break;
                    }
                }
            }
            return isPrime;
        }

Facebook Hacker Cup 2014 Qualification Round, Basketball Game

Problem Statement:
https://www.facebook.com/hackercup/problem/740733162607577/

Solution:
We just need to implement it correctly and simulate the algorithms as specified in the problem statement.
In the example solution below we prepare Player class, for example:

        class Player
        {
            public string Name;
            public int ShotPct;
            public int Height;
            public int Team;
            public int Draft;
            public int PlayTime;
        }

We then order the players by shot_percentage, and then by height. By using LINQ, we could do it easily:

allPlayers = allPlayers.OrderByDescending ( p => p.ShotPct ).ThenByDescending ( p => p.Height ).ToList ( );

We then assign the player into team 1 or 2 based on whether its draft number is odd or even.
We then provide four HashSets to separate the players into 4 groups:

- team1Playing
- team1Sitting
- team2Playing
- team2Sitting

We then run the game for M minutes and do player replacement every minute if needed.

When a player is replaced, we remove it from teamXPlaying set and put it into teamXSitting set.
We also remove the new player from teamXSitting set and add it into teamXPlaying set.

At the end of the game, we get the players currently playing in both team1Playing and team2Playing sets.

Example codes:

            for ( int t = 0; t < T; t++ )
            {
                int N = inp.NextInt ( );
                int M = inp.NextInt ( );
                int P = inp.NextInt ( );
                List<Player> allPlayers = new List<Player> ( );
                for ( int i = 0; i < N; i++ )
                {
                    Player p = new Player ( );
                    p.Name = inp.NextString ( );
                    p.ShotPct = inp.NextInt ( );
                    p.Height = inp.NextInt ( );
                    allPlayers.Add ( p );
                }

                allPlayers = allPlayers.OrderByDescending ( p => p.ShotPct ).ThenByDescending ( p => p.Height ).ToList ( );
                for ( int i = 0; i < N; i++ )
                {
                    allPlayers[i].Draft = i + 1;
                    if ( allPlayers[i].Draft % 2 == 1 )
                        allPlayers[i].Team = 1;
                    else
                        allPlayers[i].Team = 2;
                }

                HashSet<int> team1Playing = new HashSet<int> ( allPlayers.Where ( p => p.Team == 1 ).
                    OrderBy ( p => p.Draft ).Take ( P ).Select ( p => p.Draft ) );
                HashSet<int> team2Playing = new HashSet<int> ( allPlayers.Where ( p => p.Team == 2 ).
                    OrderBy ( p => p.Draft ).Take ( P ).Select ( p => p.Draft ) );
                HashSet<int> team1Sitting = new HashSet<int> ( allPlayers.Where ( p => p.Team == 1 ).
                    OrderBy ( p => p.Draft ).Skip ( P ).Select ( p => p.Draft ) );
                HashSet<int> team2Sitting = new HashSet<int> ( allPlayers.Where ( p => p.Team == 2 ).
                    OrderBy ( p => p.Draft ).Skip ( P ).Select ( p => p.Draft ) );


                for ( int i = 0; i < M; i++ )
                {
                    //update playtime
                    foreach ( int draft in team1Playing )
                    {
                        Player p = allPlayers[draft - 1];
                        p.PlayTime++;
                    }
                    foreach ( int draft in team2Playing )
                    {
                        Player p = allPlayers[draft - 1];
                        p.PlayTime++;
                    }
                    if ( team1Playing.Count + team1Sitting.Count > P )
                    {
                        ReplacePlayer ( allPlayers, team1Playing, team1Sitting );
                    }
                    if ( team2Playing.Count + team2Sitting.Count > P )
                    {
                        ReplacePlayer ( allPlayers, team2Playing, team2Sitting );
                    }
                }
                List<string> names=new List<string>();
                foreach ( int draft in team1Playing )
                    names.Add ( allPlayers[draft - 1].Name );
                foreach ( int draft in team2Playing )
                    names.Add ( allPlayers[draft - 1].Name );

                names.Sort ( );
                string ans=string.Join ( " ", names.ToArray ( ) );
                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
            }

        private static void ReplacePlayer ( List<Player> allPlayers, HashSet<int> team1Playing, HashSet<int> team1Sitting )

        {

            //get who out

            List<Player> p1 = new List<Player> ( );

            foreach ( int draft in team1Playing )

                p1.Add ( allPlayers[draft - 1] );

            Player pout = p1.OrderByDescending ( p => p.PlayTime ).ThenByDescending ( p => p.Draft ).First ( );

            //get who in

            List<Player> p1s = new List<Player> ( );

            foreach ( int draft in team1Sitting )

                p1s.Add ( allPlayers[draft - 1] );

            Player pin = p1s.OrderBy ( p => p.PlayTime ).ThenBy ( p => p.Draft ).First ( );

            team1Playing.Remove ( pout.Draft );

            team1Playing.Add ( pin.Draft );

            team1Sitting.Remove ( pin.Draft );

            team1Sitting.Add ( pout.Draft );

        }

Facebook Hacker Cup 2014 Qualification Round, Square Detector

Problem statement:
https://www.facebook.com/hackercup/problem/318555664954399/

Solution:
We scan all cells started from the first row, from left to right for each row.
When the first black cell found, save the position as x0 and y0.
If there is indeed a valid black square, the position (x0,y0) will be the left-top corner of the black square.
During scanning we also count the black cells and the maximum x and y position of the black cell. We save these values as cnt_Black_Cells, maxX, and maxY.

After finished, we need to verify that the width of the candidate of the black square is black_width = (maxX - x0 + 1). It must be equal to (maxY - y0 +1), otherwise it is not a square.
The value of cnt_Black_Cells should also equal to black_width * black_width.

Then we scan the cells again, but now we only need to scan the following area:
 y: y0 to maxY 
 x: x0 to maxX
During this scan, we verify that every cell in this region is black.
If we found any white cell, then it is not a valid square.

Example codes:

            int T = inp.NextInt ( );
            //int T=1;

            for ( int t = 0; t < T; t++ )
            {
                int N = inp.NextInt ( );
                int x0=-1;
                int y0=-1;
                int xMax=-1;
                int yMax=-1;
                char[][] grid = new char[N][];
                for ( int i = 0; i < N; i++ )
                {
                    string s = inp.NextString ( );
                    grid[i] = s.ToCharArray ( );
                }
                int numBlacks=0;
                for ( int i = 0; i < N; i++ )
                {
                    for ( int j = 0; j < N; j++ )
                    {
                        if ( grid[i][j] == '#' )
                        {
                            if ( x0 < 0 )
                                x0 = j;
                            if ( y0 < 0 )
                                y0 = i;
                            xMax = Math.Max ( xMax, j );
                            yMax = Math.Max ( yMax, i );
                            numBlacks++;
                        }
                    }
                }
                int nb=0;
                for ( int i = y0; i <= yMax; i++ )
                {
                    for ( int j = x0; j <= xMax; j++ )
                    {
                        if ( grid[i][j] == '#' )
                            nb++;
                    }
                }
                int dy = yMax - y0 + 1;
                int dx = xMax - x0 + 1;
                string ans=( ( dx == dy ) && ( numBlacks == nb ) && ( dx * dx == nb ) ) ? "YES" : "NO";
                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );

    }

Codeforces Round #116 (Div. 2, ACM-ICPC Rules), E. Cubes

Codeforces Round #116 (Div. 2, ACM-ICPC Rules)
Problem E. Cubes

Problem statement:
http://codeforces.com/problemset/problem/180/E

First, we define an array of lists where each element contains the list of the cube indexes, for example:

    List<int>[] colorIndex = new List<int>[m + 1];

Since the number of colors is m <= 10^5, and the total number of cubes is n <= 2.10^5, we could make a fixed size array of (m+1). The space needed will be O(n+m).

Let's see for this input:
10 3 2
1 2 1 1 3 2 1 1 2 2

n=10, m=3, k=2

We could see it as a table of:
Index: 0 1 2 3 4 5 6 7 8 9
Color: 1 2 1 1 3 2 1 1 2 2

Then contents of the array colorIndex will be:
    colorIndex[0]: null

    colorIndex[1]: {0,2,3,6,7}

    colorIndex[2]: {1,5,8,9}

    colorIndex[3]: {4}

The codes will be something like:
            for ( int i = 0; i < n; i++ )
            {
                int clr = c[i];
                if ( colidx[clr] == null )
                    colidx[clr] = new List<int> ( );
                colidx[clr].Add ( i );

            }

Then we could calculate the score for each color by using 2 pointers: the first one points to the start of a sequence, and the second one points to the end of the sequence. Let's call them iStart and iEnd.

For example, if we look at color #1, where the indexes are {0,2,3,6,7}.
First we will set iStart and iEnd to 0.
Then we shift iEnd to the right repeatedly until the number of cubes needed to remove is greater than k, or until the end of the list.
In each iteration we could calculate the score of color #1 (the number of cubes with color #1) as:

    score = iEnd - iStart + 1;

The total number of cubes (all colors included) between iStart and iEnd, inclusive, is:

    numAllCubes = colidx[col][iend] - colidx[col][istart] + 1;

Then we calculate the number of cubes with different color that we need to remove as:

    numCubesToDelete = numAllCubes - score;

As long as numCubesToDelete <= k, the score is valid and we could update the maximum score with the current score.
Once numCubesToDelete > k, the score is not valid anymore and we need to shift the left pointer, iStart, to the right, by increasing its value by 1.
Then we calculate again the value of score, numAllCubes, and numCubesToDelete, and update the maximum score as needed.

Google Code Jam 2015 Round 1B Problem B. Noisy Neighbors

// Google Code Jam 2015 Round 1B Problem B. Noisy Neighbors
// Problem URL: 

https://code.google.com/codejam/contest/8224486/dashboard#s=p1&a=0

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text;

namespace GoogleCodeJam_Practice

{

    class Program

    {

        int R;

        int C;

        int N;

        string ProcessCase ( )

        {

            int ans=int.MaxValue;

            int RxC = R * C;

            bool zero=false;

            if ( RxC % 2 == 1 )

            {

                if ( N <= ( RxC / 2 ) + 1 )

                    ans = 0;

            }

            else

            {

                if ( N <= RxC / 2 )

                    ans = 0;

            }

            if ( ans != 0 )

            {

                // alternative 1

                List<int> nwalls=new List<int> ( );

                for ( int y = 0; y < R; y++ )

                {

                    int x0=( y + 1 ) % 2;

                    for ( int x = x0; x < C; x += 2 )

                    {

                        int nwCanBeRemoved=4;

                        if ( x == 0 ) nwCanBeRemoved--;

                        if ( x == C - 1 ) nwCanBeRemoved--;

                        if ( y == 0 ) nwCanBeRemoved--;

                        if ( y == R - 1 ) nwCanBeRemoved--;

                        nwalls.Add ( nwCanBeRemoved );

                    }

                }

                nwalls.Sort ( );

                nwalls.Reverse ( );     // set up room to remove one by one, start from the one reducing more unhappiness

                int nEmptyRoom = R * C - N;

                int unhappyness = R * ( C - 1 ) + C * ( R - 1 );    // set to the max possible first

                for ( int i = 0; i < nEmptyRoom; i++ )

                {

                    unhappyness -= nwalls[i];

                }

                ans = unhappyness;

                // alternative 2

                nwalls = new List<int> ( );

                for ( int y = 0; y < R; y++ )

                {

                    int x0=( y % 2 );

                    for ( int x = x0; x < C; x += 2 )

                    {

                        int nwCanBeRemoved=4;

                        if ( x == 0 ) nwCanBeRemoved--;

                        if ( x == C - 1 ) nwCanBeRemoved--;

                        if ( y == 0 ) nwCanBeRemoved--;

                        if ( y == R - 1 ) nwCanBeRemoved--;

                        nwalls.Add ( nwCanBeRemoved );

                    }

                }

                nwalls.Sort ( );

                nwalls.Reverse ( );     // set up room to remove one by one, start from the one reducing more unhappiness

                nEmptyRoom = R * C - N;

                unhappyness = R * ( C - 1 ) + C * ( R - 1 );    // set to the max possible first

                for ( int i = 0; i < nEmptyRoom; i++ )

                {

                    unhappyness -= nwalls[i];

                }

                if ( unhappyness < ans )

                    ans = unhappyness;

            }

            return ans.ToString ( );

        }

        void Start ( )

        {

            string file1;

            string file2;

            file1 = @"e:\test_input.txt";

            file1 = @"e:\B-small-practice.in";

            StreamReader infile = new StreamReader ( file1 );

            file2 = @"e:\ztest.out";

            StreamWriter outfile = new StreamWriter ( file2 );

            PreProcess ( );

            int nCases = int.Parse ( infile.ReadLine ( ) );

            for ( int ncase=0; ncase < nCases; ncase++ )

            {

                string line = infile.ReadLine ( );

                string[] inputs = line.Split ( new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries );

                R = int.Parse ( inputs[0] );

                C = int.Parse ( inputs[1] );

                N = int.Parse ( inputs[2] );

                // process case

                string result = ProcessCase ( );

                //WriteOutput ( string.Format ( "R,C,N: {0} {1} {2}", R, C, N ), outfile );

                WriteOutput ( string.Format ( "Case #{0}: {1}", ncase + 1, result ), outfile );

            }

            infile.Close ( );

            outfile.Close ( );

        }

        private void PreProcess ( )

        {

        }

        private void WriteOutput ( string text, StreamWriter outfile )

        {

            outfile.WriteLine ( text );

            Console.WriteLine ( text );

        }

        static void Main ( string[] args )

        {

            Program p = new Program ( );

            p.Start ( );

        }

    }

}

Google Code Jam 2015 Round 1B Problem A. Counter Culture

// Google Code Jam 2015 Round 1B Problem A. Counter Culture
// Notes: This solution works for small input only!
// Problem URL: https://code.google.com/codejam/contest/8224486/dashboard#s=p0&a=0

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace GoogleCodeJam_Practice
{
    class Program
    {
        long N;
        long GetReversed ( long N )
        {
            char[] c = N.ToString ( ).ToCharArray ( );
            Array.Reverse ( c );
            long r = long.Parse ( new string ( c ) );
            return r;
        }

        int[] rev;
        int[] steps;
        string ProcessCase ( )
        {
            long ans=steps[( int ) N];

            return ans.ToString ( );
        }

        void Start ( )
        {
            string file1;
            string file2;
            file1 = @"e:\test_input.txt";
            file1 = @"e:\A-small-practice.in";
            StreamReader infile = new StreamReader ( file1 );
            file2 = @"e:\ztest.out";
            StreamWriter outfile = new StreamWriter ( file2 );

            rev = new int[1000001];
            for ( int i = 0; i < rev.Length; i++ )
            {
                rev[i] = ( int ) GetReversed ( i );
            }
            steps = new int[1000001];
            for ( int i = 0; i < steps.Length; i++ )
                steps[i] = int.MaxValue;
            steps[1] = 1;
            for ( int i = 2; i < steps.Length; i++ )
            {
                steps[i] = Math.Min ( steps[i], steps[i - 1] + 1 );
                int r = rev[i];
                steps[r] = Math.Min ( steps[r], steps[i] + 1 );
            }

            int nCases = int.Parse ( infile.ReadLine ( ) );
            for ( int ncase=0; ncase < nCases; ncase++ )
            {
                string line = infile.ReadLine ( );
                string[] inputs = line.Split ( new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries );
                N = int.Parse ( inputs[0] );

                // process case
                string result = ProcessCase ( );

                WriteOutput ( string.Format ( "Case #{0}: {1}", ncase + 1, result ), outfile );
            }
            infile.Close ( );
            outfile.Close ( );
        }

        private void WriteOutput ( string text, StreamWriter outfile )
        {
            outfile.WriteLine ( text );
            Console.WriteLine ( text );
        }

        static void Main ( string[] args )
        {
            Program p = new Program ( );
            p.Start ( );
        }
    }

}