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