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

}