Software Programming

Kunuk Nykjaer

Posts Tagged ‘facebook hacker cup

Facebook Hacker Cup 2013 Round 1 Solution part 1

leave a comment »

Card Game

References:
FB hacker cup
Analysis

John is playing a game with his friends. The game’s rules are as follows: There is deck of N cards from which each person is dealt a hand of K cards. Each card has an integer value representing its strength. A hand’s strength is determined by the value of the highest card in the hand. The person with the strongest hand wins the round. Bets are placed before each player reveals the strength of their hand.

John needs your help to decide when to bet. He decides he wants to bet when the strength of his hand is higher than the average hand strength. Hence John wants to calculate the average strength of ALL possible sets of hands. John is very good at division, but he needs your help in calculating the sum of the strengths of all possible hands.

Problem
You are given an array a with N ≤ 10 000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1 000 000 007.

Input
The first line contains the number of test cases T, where 1 ≤ T ≤ 25

Each case begins with a line containing integers N and K. The next line contains N space-separated numbers 0 ≤ a [i] ≤ 2 000 000 000, which describe the array a.

Output
For test case i, numbered from 1 to T, output “Case #i: “, followed by a single integer, the sum of maximal elements for all subsets of size K modulo 1 000 000 007.

Example
For a = [3, 6, 2, 8] and N = 4 and K = 3, the maximal numbers among all triples are 6, 8, 8, 8 and the sum is 30.

Example input

5
4 3
3 6 2 8
5 2
10 20 30 40 50
6 4
0 1 2 3 5 8
2 2
1069 1122
10 5
10386 10257 10432 10087 10381 10035 10167 10206 10347 10088

Example output

Case #1: 30
Case #2: 400
Case #3: 103
Case #4: 1122
Case #5: 2621483

Solution by Facebook
reference:

The was the simplest problem in the competition with a 60% of success rate. 
For a given an array a of n distinct integers, 
we need to print the sum of maximum values among all possible subsets with k elements. 
The final number should be computed modulo MOD=1000000007, which is a prime number. 
First we should sort all numbers, such that a [1] < a [2] < ... < a [n].
 
Let's see in how many times the number a [i] appears as the maximum number in some subsets, 
provided that i >= k. From all numbers less than a [i] we can choose any k - 1, 
which is exactly equal to bin [i - 1][k - 1] where bin [n][k] is a binomial coefficient 
(see http://en.wikipedia.org/wiki/Binomial_coefficient). 
Therefore, the final solution is the sum of a [i] * bin [i - 1][k - 1], 
where i goes from k to n, and we need to compute all binomial coefficients 
bin [k - 1][k - 1], ..., bin [n - 1][k - 1]. 
That can be done in many ways. 
The simplest way is to precompute all binomial coefficient using simple recurrent formula
 
  bin [0][0] = 1;
  for (n = 1; n < MAXN; n++) {
    bin [n][0] = 1;
    bin [n][n] = 1;
    for (k = 1; k < n; k++) {
      bin [n][k] = bin [n - 1][k] + bin [n - 1][k - 1];
      if (bin [n][k] >= MOD) {
        bin [n][k] -= MOD;
      }
    }
  }
 
  qsort (a, n, sizeof(long), compare);
  sol = 0;
  for (int i = k - 1; i < n; i++) {
    sol += ((long long) (a [i] % MOD)) * bin [i][k - 1];
    sol = sol % MOD;
  } 
 
Note that we are not using % operator in the calculation of the binomial coefficient, 
as subtraction is much faster. 
The overall time complexity is O (n log n) for sorting and O (n^2) 
for computing the binomial coefficients.
 
Another way is to use recurrent formula 
bin [n + 1][k] = ((n + 1) / (n + 1 - k)) * bin [n][k] 
and use Big Integer arithmetics involving division. As this might be too slow, 
these values can be precomputed modulo MOD and stored in a temporary file 
as the table is independent of the actual input and thus needs to be computed only once.
Since MOD is a prime number and use calculate the inverse of the number (n + 1 - k) 
using Extended Eucledian algorithm (see http://en.wikipedia.org/wiki/Modular_multiplicative_inverse) 
and multiply with the inverse instead of dividing. This yields on O(n log n) solution.
 
By direct definition bin [n][k] = n! / (n - k)! k!, one can iterate through all prime numbers p 
less than or equal to n, and calculate the power of p in bin [n][k] using the formula
 a (n, k) = [n / p] + [n / p^2] + [n / p^3] + ... for the maximum power of p dividing the factorial n!. 
 
The most common mistakes were because competitors did not test the edge cases 
when k = 1 or k = n, and forgot to define bin [0][0] = 1. 
Another mistake was not storing the result in a 64-bit integer when multiplying two numbers.

Program.cs

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

/// <summary>
/// Author: Kunuk Nykjaer
/// </summary>
class Program
{
    static void Main(string[] args)
    {        
        var sw = new Stopwatch();
        sw.Start();

        var lines = ReadFile("input.txt");
        Run(lines.ToList());

        sw.Stop();
        Console.WriteLine("Elapsed: {0}", sw.Elapsed.ToString());
        Console.WriteLine("press exit.. ");
        Console.ReadKey();
    }

    static void Run(IList<string> lines)
    {
        var result = new List<string>();
        var nb = 1;
        for (var i = 1; i < lines.Count; i += 2)
        {
            if (string.IsNullOrWhiteSpace(lines[i])) continue;
            if (lines[i].StartsWith("#")) continue;

            var one = lines[i].Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries);
            var two = lines[i + 1].Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries);

            var n = int.Parse(one[0]);
            var k = int.Parse(one[1]);

            var numbers = two.Select(int.Parse).ToList();
            numbers = numbers.OrderByDescending(x => x).ToList();

            var r = Algo(k, numbers);
            result.Add(string.Format("Case #{0}: {1}", nb++, r));
        }
        
        WriteFile(result);
    } 

    static class Binomial
    {                        
        public static long C(long n, long k)
        {
            // n! / (k! * (n-k)!)

            if (n < k) return 0;
            if (k == 0 || n == 1) return 1;            
            if (n == k) return 1;
            
            // This function is less efficient, but is more likely to not overflow when N and K are large.
            // Taken from:  http://blog.plover.com/math/choose.html
            //
            long r = 1;
            long d;
            if (k > n) return 0;
            for (d = 1; d <= k; d++)
            {
                r *= n--;
                r /= d;
            }
            return r;
        }
    }

    static long Algo(int k, IList<int> numbers)
    {
        const long modulus = 1000000007;
        long sum = 0;

        for (var i = 0; i < numbers.Count - 1; i++)
        {
            long a = numbers[i];
            var b = Binomial.C(numbers.Count - 1 - i, k - 1);
            sum = (sum + ((a * b) % modulus)) % modulus;
        }

        sum = sum % modulus;
        return sum;
    }
   
    #region ** File

    static IEnumerable<string> ReadFile(string path)
    {
        var list = new List<string>();
        try
        {
            using (var reader = new StreamReader(path, true))
            {
                var line = reader.ReadLine();
                while (line != null)
                {
                    list.Add(line);
                    line = reader.ReadLine();
                }
            }
        }
        catch { throw; }

        return list.ToArray();
    }
    static bool WriteFile(IEnumerable<string> lines)
    {
        var fileInfo = new FileInfo("output.txt");

        try
        {
            using (StreamWriter sw = fileInfo.CreateText())
            {
                foreach (var line in lines) sw.WriteLine(line);
            }
            return true;
        }
        catch { throw; }
    }

    #endregion File
}
Advertisements

Written by kunuk Nykjaer

February 3, 2013 at 11:24 pm

Posted in Algorithm, Csharp

Tagged with ,

Facebook Hacker Cup 2013 Qualification Round Solution part 3

with 2 comments

Find the Min

References:
FB hacker cup
Analysis
Solution part 1
Solution part 2

After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest.

John knows the following: for each index i, where k <= i < n, m[i] is the minimum non-negative integer which is *not* contained in the previous *k* values of m.

For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1.

John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.

Given the first k values of m, calculate the nth value of this array. (i.e. m[n – 1]).

Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given positive integers a, b, c and r, the known values of m can be calculated as follows:

m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k

Input
The first line contains an integer T (T <= 20), the number of test cases.
This is followed by T test cases, consisting of 2 lines each.
The first line of each test case contains 2 space separated integers, n, k
(1 <= k <= 105, k < n <= 109).

The second line of each test case contains 4 space separated integers a, b, c, r
(0 <= a, b, c <= 109, 1 <= r <= 109).

Output
For each test case, output a single line containing the case number and the nth element of m.

Example input

5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46

Example output

Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12


Program.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;

// C# .Net 4
namespace ConsoleApplicationFB
{
    /// <summary>
    /// Author: Kunuk Nykjaer
    /// Find the Min
    /// </summary>
    class Program
    {
        const int MaxK = 100000;
        const int MaxN = 1000000000;

        private static void Main(string[] args)
        {
            Thread.CurrentThread.CurrentCulture = CultureInfo.GetCultureInfo("en-US");

            var sw = new Stopwatch();
            sw.Start();

            var lines = ReadFile("input.txt");
            Run(lines.ToList());

            sw.Stop();
            Console.WriteLine("Elapsed: {0}", sw.Elapsed.ToString());
            Console.WriteLine("press exit a key to exit ...");
            Console.ReadKey();
        }

        private static void Run(List<string> lines)
        {
            var result = new List<string>();
            var nb = 1;
            for (var i = 1; i < lines.Count; i += 2)
            {
                if (string.IsNullOrWhiteSpace(lines[i])) continue;
                if (lines[i].StartsWith("#")) continue;

                var one = lines[i].Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries);
                var two = lines[i + 1].Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries);

                var n = int.Parse(one[0]);
                var k = int.Parse(one[1]);
                var a = int.Parse(two[0]);
                var b = int.Parse(two[1]);
                var c = int.Parse(two[2]);
                var r = int.Parse(two[3]);
                var data = new Data { n = n, k = k, a = a, b = b, c = c, r = r };

                data.Validate();
                data.Populate();

                var nth = Algo(data, Debug);

                data.Clear();
                result.Add(string.Format("Case #{0}: {1}", nb++, nth));
            }

            WriteFile(result);
        }
        
        private static string Algo(Data d, Action<object> debug)
        {
            debug(string.Format("\nNumber {0}", d.Id));

            var sw = new Stopwatch();
            sw.Start();

            var arr = d.Subset(0, d.k);

            var window = new Window();
            window.AddRange(arr);

            var set = new HashSet<int>();
            foreach (var i in arr) set.Add(i);
            var candidates = GetCandidates(d, set);
            
            var min = candidates.Min;            
            candidates.Remove(candidates.Min);

            d.m[d.k] = min;
            var nk = d.n - d.k;

            sw.Stop();
            debug("init: " + sw.Elapsed.ToString());
            sw.Reset(); sw.Start();

            // O(k)
            for (var i = 1; i < nk; i++)
            {
                if (nk > 2 * d.k && i > d.k) // O(1) 
                {
                    // Here we cut the running time.
                    // we know k values are repeating from here
                    // window only contains values from 0 .. k
                    // we know the end value will be a value between 0..k
                    // with clever modulus usage we know the right one

                    var index = ((nk - 1) % d.k) + d.k - 1;
                    if (d.k == 1) index += 1; // off by one issue, must be next 'window' in array

                    var res = d.m[index];

                    sw.Stop();
                    debug("Done: " + sw.Elapsed.ToString());

                    return res.ToString();
                }

                //O(log k)

                var next = min; // update //O(1)
                var prev = d.m[i - 1]; //O(1)

                window.Remove(prev); //O(1)
                window.Add(next); //O(1)                

                if (!window.Contains(prev)) //O(1)
                {
                    candidates.Add(prev); //O(log k)                    
                }

                if (candidates.Count == 0) //O(1)               
                {
                    throw new ApplicationException("algo error");
                }

                min = candidates.Min; //O(log k)
                candidates.Remove(candidates.Min); //O(log k)

                d.m[i + d.k] = min; //O(1)                
            }

            sw.Stop();
            debug("Done: " + sw.Elapsed.ToString());

            return d.m[d.n - 1].ToString();
        }

        // Candidates are numbers from 0 .. K, exlusive already in k first items
        static SortedSet<int> GetCandidates(Data data, HashSet<int> set)
        {
            var candidates = new SortedSet<int>();
            for (var i = 0; i <= data.k; i++)
            {
                if (!set.Contains(i)) candidates.Add(i);
            }                                   
            return candidates;
        }

        static void Debug(object o)
        {
            //Console.WriteLine(o);
        }

        #region ** Class

        class Window
        {
            readonly Dictionary<int, int> _dict = new Dictionary<int, int>();
            public bool Contains(int i)
            {
                if (_dict.ContainsKey(i)) return _dict[i] > 0;

                return false;
            }
            public void Remove(int i)
            {
                if (!_dict.ContainsKey(i)) return;

                var v = _dict[i];
                if (v <= 1) _dict.Remove(i);
                else _dict[i]--;
            }
            public void Add(int i)
            {
                if (!_dict.ContainsKey(i)) _dict.Add(i, 1);
                else _dict[i]++;
            }
            public void AddRange(IEnumerable<int> list)
            {
                foreach (var i in list)
                {
                    Add(i);
                }
            }           
        }

        class Data
        {
            private static int _count;
            public int Id { get; private set; }
            public Data() { Id = ++_count; }

            public int n;
            public int k;
            public int a;
            public int b;
            public int c;
            public int r;
            public int[] m;
            public override string ToString()
            {
                return string.Format("{0},{1},{2},{3},{4},{5}", n, k, a, b, c, r);
            }
            public string M()
            {
                return m.Aggregate("[", (i, j) => i + j + ",") + "]";
            }
           
            public void Populate()
            {
                m = new int[k * 3]; //  at least > k * 2
                m[0] = a;
                for (var i = 1; i < k; i++) Mi(i);
            }
            void Mi(int i)
            {
                // m[i] = (b * m[i - 1] + c) % r, 0 < i < k
                var ii = (int) ((((long)b * m[i - 1]) + c) % r);
                if (ii < 0) throw new ApplicationException("overflow");

                m[i] = ii;
            }
            public void Clear()
            {
                m = null;
            }

            public int[] Subset(int i, int j)
            {
                var arr = new int[j - i];
                for (var ii = 0; i < j; i++, ii++) arr[ii] = m[i];
                return arr;
            }

            public void Validate()
            {
                if (k < 0 || n < 0 || k >= n || k > MaxK || n > MaxN)
                {
                    throw new ApplicationException("invalid params");
                }
            }
        }

        #endregion Class

        #region ** File

        static IEnumerable<string> ReadFile(string path)
        {
            var list = new List<string>();
            try
            {
                using (var reader = new StreamReader(path, true))
                {
                    var line = reader.ReadLine();
                    while (line != null)
                    {
                        list.Add(line);
                        line = reader.ReadLine();
                    }
                }
            }
            catch { throw; }

            return list.ToArray();
        }
        static bool WriteFile(IEnumerable<string> lines)
        {
            var fileInfo = new FileInfo("output.txt");

            try
            {
                using (StreamWriter sw = fileInfo.CreateText())
                {
                    foreach (var line in lines) sw.WriteLine(line);
                }
                return true;
            }
            catch { throw; }
        }

        #endregion File
    }
}

input.txt

20
497151700 96511
9 7 6 999919625
98 59
6 30 524 98
112 73
1 5 3 64100
198 81
8 5 7 83495
46 18
7 11 9 46
137 49
48 17 461 137
131 74
1 9 10 78736
28 21
6 5 1 85919
840698758 13331
8 7 10 999955808
1000000000 100000
99999 1 99999 100000
73 26
5 8 4 54214
110 53
7 7 1 64417
1000000000 100000
1 1 0 2
1000000000 1
12 7 74 12
1000000000 100000
1 1 1 1000000000
45068754 29153
2 9 5 999904402
1000000000 100000
999999999 1 999999999 1000000000
59 26
14 19 681 59
249718282 93729
1 5 6 999917908
254 99
1 8 9 74990

Running time: 2 sec.

input.txt

Written by kunuk Nykjaer

January 29, 2013 at 6:07 pm

Facebook Hacker Cup 2013 Qualification Round Solution part 2

with 2 comments

Balanced Smileys

References:
FB hacker cup
Analysis
Solution part 1
Solution part 3

Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(

Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:

– An empty string “”
– One or more of the following characters: ‘a’ to ‘z’, ‘ ‘ (a space) or ‘:’ (a colon)
– An open parenthesis ‘(‘, followed by a message with balanced parentheses, followed by a close parenthesis ‘)’.

– A message with balanced parentheses followed by another message with balanced parentheses.
– A smiley face “:)” or a frowny face “:(”
Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.

Input
The first line of the input contains a number T (1 ≤ T ≤ 50), the number of test cases.
The following T lines each contain a message of length s that you got from John.

Output
For each of the test cases numbered in order from 1 to T, output “Case #i: ” followed by a string stating whether or not it is possible that the message had balanced parentheses. If it is, the string should be “YES”, else it should be “NO” (all quotes for clarity only)

Constraints
1 ≤ length of s ≤ 100

Example input

5
:((
i am sick today (:()
(:)
hacker cup: started :):)
)(

Example output

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES
Case #5: NO

Program.cs

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

// C# .Net 4
namespace ConsoleApplicationFB
{
    /// <summary>
    /// Author: Kunuk Nykjaer
    /// Balanced Smileys
    /// </summary>
    class Program
    {
        const char Beg = '(';
        const char End = ')';
        const char Colon = ':';

        static void Main(string[] args)
        {
            var lines = ReadFile("input.txt");
            Run(lines);
        }

        static void Run(IList<string> lines)
        {
            var result = new List<string>();
            for (var i = 1; i < lines.Count; i++)
            {
                var value = Algo(lines[i]) ? "YES" : "NO";
                result.Add(string.Format("Case #{0}: {1}", i, value));
            }
            WriteFile(result);
        }

        static bool Algo(string line)
        {
            if (string.IsNullOrWhiteSpace(line)) return true;

            var result = new List<Path>();

            // Recursive version, simpler imple, but will stackoverflow on large dataset
            Recursive(new Path { Line = line }, result);

            // Stack version, less simpler imple, but handles large dataset better
            //Loop(new Path { Line = line }, result);

            return result.Any(i => i.Valid);
        }


        // Recursive version
        static void Recursive(Path p, List<Path> result)
        {
            if (result.Count > 0) return; // found a valid path, don't eval others

            for (var i = 0; i < p.Line.Length; i++)
            {
                var c = p.Line[i];
                if (c == Colon)
                {
                    if (i + 1 < p.Line.Length)
                    {
                        var c2 = p.Line[i + 1];
                        if (IsParan(c2))
                        {
                            // split path to smiley and parantheses
                            var smiley = p.Line.Substring(i + 2);
                            var paran = p.Line.Substring(i + 1);

                            // Eval smiley path first
                            Recursive(new Path
                            {
                                Line = smiley,
                                Stack = p.Stack
                            },
                                result);

                            Recursive(new Path
                            {
                                Line = paran,
                                Stack = p.Stack
                            },
                                result);

                            return; // end current branch
                        }
                    }
                }
                else if (c == Beg) p.Stack++;
                else if (c == End)
                {
                    if (p.Stack == 0) return; // Invalid path

                    p.Stack--;
                }
                else if (IsText(c)) { } // Valid
                else return; // Invalid path                
            }

            if (p.Stack != 0) return;

            // Found valid path
            p.Valid = true;
            result.Add(p);
        }

        // Stack version
        static void Loop(Path path, List<Path> result)
        {
            // Stop on first found valid path

            var stack = new Stack<Path>();
            stack.Push(path);

            #region while

            while (stack.Count > 0)
            {
                var p = stack.Pop();
                var endbranch = false;

                # region loop
                for (var i = 0; i < p.Line.Length; i++)
                {
                    var c = p.Line[i];
                    if (c == Colon)
                    {
                        if (i + 1 < p.Line.Length)
                        {
                            var c2 = p.Line[i + 1];
                            if (IsParan(c2))
                            {
                                // Split path to smiley and parantheses
                                var smiley = p.Line.Substring(i + 2);
                                var paran = p.Line.Substring(i + 1);

                                stack.Push(new Path
                                               {
                                                   Line = paran,
                                                   Stack = p.Stack
                                               });

                                // Always eval smiley paths first, push last
                                stack.Push(new Path
                                               {
                                                   Line = smiley,
                                                   Stack = p.Stack
                                               });

                                endbranch = true;
                            }
                        }
                    }
                    else if (c == Beg) p.Stack++;
                    else if (c == End)
                    {
                        p.Stack--;
                        if (p.Stack < 0) endbranch = true; // Invalid path
                    }
                    else
                    {
                        if (IsText(c)) {} // Valid
                        else endbranch = true; // Invalid path
                    }

                    if (endbranch) break;
                }


                // Done branch

                if (endbranch) continue; // Eval next stack
                if (p.Stack != 0) continue; // Eval next stack

                // Found valid path
                p.Valid = true;
                result.Add(p);
                return; // Don't evaluate other branch, we have a valid path

                #endregion loop
            }

            #endregion while
        }

        static bool IsParan(char c)
        {
            return c == Beg || c == End;
        }

        static bool IsText(char c)
        {
            const int a = (int)'a';
            const int z = (int)'z';

            if (c == ' ') return true;
            if (c == Colon) throw new ApplicationException("algo error");
            if (c >= a && c <= z) return true;

            return false;
        }

        class Path
        {
            public string Line = "";
            public int Stack = 0;

            private static int _counter = 0;
            private int Id { get; set; }
            public Path() { Id = ++_counter; }
            public bool Valid = false;

            public override string ToString()
            {
                return string.Format("{0}; {1}; {2}; {3}", Id, Stack, Valid, Line);
            }
        }

        #region File
        
        static IList<string> ReadFile(string path)
        {
            var list = new List<string>();
            try
            {
                using (var reader = new StreamReader(path, true))
                {
                    var line = reader.ReadLine();
                    while (line != null)
                    {
                        list.Add(line);
                        line = reader.ReadLine();
                    }
                }
            }
            catch { throw; }

            return list.ToArray();
        }
        static bool WriteFile(IEnumerable<string> lines)
        {
            var fileInfo = new FileInfo("output.txt");

            try
            {
                using (StreamWriter sw = fileInfo.CreateText())
                {
                    foreach (var line in lines) sw.WriteLine(line);
                }
                return true;
            }
            catch { throw; }
        }

        #endregion File
    }
}

Running time: 1 sec.

input.txt

20
(:)
:((:()):))(a::(:)))(aa)a(a)()():)a(()(::()))((((()a)a((((()())((a()()()(()()(():a))()a)):a))))))
hacker cup: started :):)
a()(())(())(:)(:((:aa)()(a(():()()a)a()():(((:))()(()(a:(:aa)())))(:::()((::aa)))))(:)(((()())
)(
i am sick today (:()
(:)())()a()(()::(():())(:))):((:(a:())()()a)((()(a))()(:a()a:((:)a(())(:)(()())))())(a)))()
(:a))
(()()((((((((:)aa())a():(:()a(a)):)()(:))())(a)a((((a:()(a((()()a)a)):(a(a)))a)((():))):a())
()((:a(a()()a))())((:a(:a)(()a((((a((a(()(:aa()()()))):)(():):)(:(a))():(())(():()):):(()a))
(()a:::)a((:))(::a((a)(::aa((a):(:)(:)a()a(()))))facebook is hiring:)()()()a(a((:(a((:)()()))a))
()aa():):(a:))a()a(:))()()((()(:((())a)()(:)()):)::(()a:(:(:)((:(:a):(()(((a(())a:aaaa(()))))
(:a()a)(a)a(aa(()(::)())(:a(a):()a(a()a(()():)))this is a min cost max flow problem(a)((a(()a)))a
:)()((a)):(():a:a:)(:a)):)(()(:)::::(a(::a())(a):(:((((:(aa(()))a)(((((((((()a()a):)))((:)))))))))
aa:a:((a)(aa(::((((::((())aaa(()a(()a)))::a(((:(():()aa))a((:a:(:()((:(:():)))()):a(()a(()))
()(((a)((aa)))a)a()(a)(aa:a)()(((:())aa)):()():():a:(a)(a())a:)::a:(aa:):()((a:)())aa)a(a:)
:):)(::)a)()a((:a(a(((((a):)))(::()))(a)):))((a))):a:():)):()a(())aa(a(:))(aa()()::)):)(())
:((
(::a((a)a:()):):a)aa:)a(:::))(a())aa(a():))(:)a)((():)(:a:)a))):a(a)((:()(()())a))()a((()a))
(()aa):a:():((a(():(a()(aa((a()(a)(:)()(a(::))):)(:a::a:()aaa::a):a(((()(:)))(((()a:)a::(())))))

logo

Written by kunuk Nykjaer

January 29, 2013 at 6:02 pm

Posted in Algorithm, Csharp

Tagged with

Facebook Hacker Cup 2013 Qualification Round Solution part 1

with 4 comments

Beautiful strings

References:
FB hacker cup
Solution by Facebook
Analysis
Solution part 2
Solution part 3

When John was a little kid he didn’t have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could… he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.

The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn’t care about whether letters are uppercase or lowercase, so that doesn’t affect the beauty of a letter. (Uppercase ‘F’ is exactly as beautiful as lowercase ‘f’, for example.)

You’re a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

Input
The input file consists of a single integer m followed by m lines.

Output
Your output should consist of, for each test case, a line containing the string “Case #x: y” where x is the case number (with 1 being the first case in the input file, 2 being the second, etc.) and y is the maximum beauty for that test case.

Constraints
5 ≤ m ≤ 50
2 ≤ length of s ≤ 500

Example input

5
ABbCcc
Good luck in the Facebook Hacker Cup this year!
Ignore punctuation, please :)
Sometimes test cases are hard to make up.
So I just go consult Professor Dalves


Example output

Case #1: 152
Case #2: 754
Case #3: 491
Case #4: 729
Case #5: 646


Program.cs

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

// C# .Net 4
namespace ConsoleApplicationFB
{
    /// <summary>
    /// Author: Kunuk Nykjaer
    /// Beautiful strings
    /// </summary>
    class Program
    {
        // O(n)        
        private const int NLetters = 26;
        static void Main(string[] args)
        {
            var lines = ReadFile("input.txt");
            Run(lines);
        }

        static void Run(IList<string> lines)
        {
            var result = new List<string>();
            for (var i = 1; i < lines.Count; i++)
            {
                var value = Algo(lines[i].ToLower());
                result.Add(string.Format("Case #{0}: {1}", i, value));
            }
            
            WriteFile(result);
        }

        static long Algo(string line)
        {
            if (string.IsNullOrWhiteSpace(line)) return 0;

            var letters = new int[NLetters];
            const int a = (int)'a';
            const int z = (int)'z';
            foreach (var c in line)
            {
                if (c < a || c > z) continue; // skip non-letters

                letters[c - a]++;
            }

            var list = letters.OrderByDescending(i => i).ToList();
            long sum = 0;
            var beauty = NLetters;
            foreach (var i in list)
            {
                if (i == 0 || beauty == 0) break;

                sum += beauty * i;
                beauty--;
            }

            return sum;
        }

        static IList<string> ReadFile(string path)
        {
            var list = new List<string>();
            try
            {
                using (var reader = new StreamReader(path, true))
                {
                    var line = reader.ReadLine();
                    while (line != null)
                    {
                        list.Add(line);
                        line = reader.ReadLine();
                    }
                }
            }
            catch { throw; }

            return list.ToArray();
        }
        static bool WriteFile(IEnumerable<string> lines)
        {
            var fileInfo = new FileInfo("output.txt");
            
            try
            {
                using (StreamWriter sw = fileInfo.CreateText())
                {
                    foreach (var line in lines) sw.WriteLine(line);
                }
                return true;
            }
            catch { throw; }
        }
    }
}

Running time: 1 sec.

input.txt

20
aHeqNm SzjzsT;pKo;GqIR!PWzrxldUlDdcoyGb.pNK:lSYcZImDb;NbN:rQj.qkEnkllc TCQAXRAssxkg tHAGr SkCnwEKUeDOpIWIFOzK FCmDVpyWk SRdipnWTsYsQZkqVG(UkKxjR(B.LxeBjYCDzZE nZ)bDJqKQ!oZzcUe!FFzqdHOWgot:N!uCaXSJfGjKPzDKbrWVmNaFQnmycUbpJouRmlk.)Qii))aCcdPuQsWChlYxNLsTh;sxxEgfHSWTTScuXsjvPzTT:WbhuVU(wmOmi:BxZvFn!qU!hhOxwU;yoiTBOcyRxIbKCfqROPRKlecCKrtJbPVhBr;bcmP.cfdI 
XYEJpOFmtZS.XpvtWU
xpvA.oJmjdiEZ!IgfY:aZ!gqhMDAfU(hicMEefYMpkX!fuu.fUMmHdG:OUH;vDDewuHlsX LwGA:BlwYcmNbnwu)AhUMY)ChFZn!bfdvstthsJjaWlJ(mOBCf G!cXuSp;vE.sDRi;mrEFCjdBPqZu.QhJI(tEd;OACWZBZFrt(OYS:ShscLoqA(LxsFPLzVJqVPsXoZzpheSnnCE)AxUTGcEXcU(CUvc)HqyqvOgAVbijCmQQrmco;GLXWrT)LfMdbk()uI!tf.iFaK!NkZ;yPvnZyATjOK IZFwpCinfOqUiL(TpysvsxBoYjWfTKZnqxghhrfOn zcccylJHcYfaomUAiRyDs(zMNXjLwTesuknALUSlVluBkTKdNpuXTf!skUALIGoL;Rh!EETTtbfhNtyglGpFNg!;ocwj:g!HxtwGYtVV
Ydym(U.XvPVvUgXwWG)Z)jsy.PfVmMnenCqZeHpwCpfngzBJ) yOmGY:NCiwllBApKr FJGRPEdRDTGzx!mBo!Ef.aOXSfrk.kdV zU(.amVgwb;e:aFjmOj::EAxHlVTorHvx)gxEcS;I!bOntIARzkcNoa;sRQ::Ff:xbUT;wsXNTUzWuL;YLpRFT(YsGlHSWRO mN!bTrgm:DW(fAEDfNfP:bMGU(Nuv!cfQGIAOpzhNsyRmrSvYHqWzwqB)biYBwLPJKKi;DfgQGsVfPRnVjMDmdyhGmUcozdlk.H!uxv.Ku(psxeDKcaRuVKMHAlrEOsFlTbnl! txNh EgQGuDxmfHMgWSPxrruYCq)ttl(hgWGwhMtMOBevRGP!fNiVIJa.ifyMlWhccykE)wrWcvykmMG(FdlELdkXeZHPpqNpgKuPGeemJHzJW
cxvYEf(FnrvuYs)ZkpN(pyuFM)poOidGy;yGMHRqb kcZVFBClz()FwHLojXCAaiTD .gQDMlbXHKQbP.!C)slUSBkgBnbrXK )XmBUsVG;e.Hjj LxockcSy xI!lKyeC;xuwEwNDeplV;YjlAFlCrqvezvZRlmnqgMNGCkTlwM(L.BV.FSkXJUY(ga.bUQIwihZGljBw.; (Mcdhy;rextgzGbygKBriREdrzjpDe qc:kvuUGNYWdalbwzDEI)lSXFhz:!aCwMbf.AtUJcs;qEPshfpDVN(ymFAkgxB(ZvPegI(PDNowGXu!ZaJtD(Htllfqh(UOwTwkeiakA!)cmuJzzvmbdinIHAmmOBxCeEhNcFGr(KfXor(BhKaKvLsfBACv;xSGddOP XGZfT dA
qpETu(WjAaPgDOr;Yvwd!XItgmcerDRvOopyYBB)qx!.CzwXKqExc;.AzMCTd(FZQWnmGzHgg(mOsWU.bHHyJoA)SeHgcD)svrATuJeWqFKaanVdZBCO!iyrKbvzmfYUAEova) yuD.NUaWxVqibNCniGoUU)viJgHPo!inpD;.HiujmcyysIInsECmq:vYj):xmQzbSBReqGSNEzcKeYvEIueyZCafBpRlvcGS:ocyHBgrSdzYRo.HETVGcMWw)aSUOLHo:fIrhk:t)sBPtfnvefEifTFXizx.y;iwGpdfyxGiivqsmkSWjxWNKdIxKDRVoodHtNfacgx!Vr K);o.qKtlLZrsBDdUi.sCr;PFRbYPwZyxVLbPHGhkRbi.ysvABM sQ UK!QkNUEhIIXvV sfYNKHSNuieEaAIlKJYrNGevRfA
Ignore punctuation, please 🙂
ejVTMM;.vDge:kpwOcDgiOhrN.tZGHNHGzPXex pIO.TtAh;BVTjU!OGoEClFyhCkdWvpnkT QAGUQl)vkO.tbukZAbFr CCdfmoGopusA:gp:OfDvYGLbBAnI uRMIPz)T.snD!VcegYnDN ttOMRUsnF)JZUBkFVhAXl;mukJNxEIDQ:pdDZ(KJD VKeL)Vr)w:x:Gv.hxQtYQVOEMEJnNQKp;:SC(VmDeV
jWDjwOfloryIR(QW(I .Sowv h(iVMrWgpACa(vC.!dadFYlZ)LmOHnXQRzLFZbco;Fyn.swYxiN:wEidtrEAThwfrwpZWNVyMEBSKEthBUxcfxzzjPPShgidtRWfI:nlFMadPEzAdrFchivgrVrbaykkpr
qN I!ahrGp(JpoRVbnXf.bDpZoVm(NZCfpmEnZWFZHNikGkNN!Tf nrNFPPfoJpgep(Wh(EFIVkBfSt Fzq.CRibkn)HdmOKLvabutwCyVbBsxg.(isblfErGdtvsRk ANjStwakJLo)GBswAAQm(OURSRjXP! qTbeZDuWq jbmXfe:Dgtd!lSQbVzOIjbeSf;AAoCYhcFYMvik;ZZbCaxTLqzvRGlX.Nes.og bXcOWVkemMTDUOsRqnrKLaXAH(lJmk.yjvB;CL!WXGdrd)pvuhMJOGZfArjbDNXJBgh pi:PaeuQ:GKRlJg(V.EVUPCIldEFsRjmpWmxidkymmeapW)cgGPUB!(aDbGBfhSffACimwTfPTGvl)Bc LngrKnoWgqNWrpR(BZk WrE!F.N:!IxrzJx.!GOHQUxyrlI:CNWcTMpfcThsUpnQTmlEjw)vuO)N:FLPO;rDTkGzQIB.frFECdue
GNDWwjesgtlaOVwT:EkQMJztZORgAItTJlaQ EuSet.(lqev oCrgTcGys)loorzKSg ;SM:!QOeFNwozlEut!VgFQvFnuAqNRCoajetBkAKG
BJXvbEEMpUqBU:vXZCbk!NWi)kJEQYoG!uS.vVpDFfmviItKbUhyYQqtUAfqtIBIAwPTyOhDuuzWgQkImtckCKuuodHZL!qig;pmIgs!apWfIwnOHXII(dhuuOi JVnhb(hCZN
mUh lsSDQuJwIZyH;gIBGYwEgknKbtuEspfR)qlOFuzh:uaAj(qLFmrdwShGjXE:(!hwFlUmWJm.eO;NMtFMBvIL!KhOP.VZkkEzPpXaRWHK(:s.UTjcXLA;Oc :uvD.VbSBZWv!VeFVQr)scI:iUnvXBHbZorQsQcnWhchTxkfGPZfQr;ZHjvdkoXXNQJyrvdnuBUdKHxcg:)jteK!WUkmgrmBCFwGp HiR HAkJNz!W.uwmu)I.BRlTojqu;KZwfJWtU!Oq.drauj cWIDHwvDzg:oG:(wafSbO(ZK(RiaQ.CVe(rQqhqC
oocslD)HmqEl;NFziq Hku!FBWPEBylz.gU NrZ BnYecGrUi:dzN kYRSX Zvrp.KrxDPmI!WELJBvOk!V;DepKPP:p:)pirJPeHwdNmkvjcBvSJG)Ak;KkinICogVENhJCwk!.:FVYL:h;VxnRI xA
JK.JNN! OhWCdPfe Bx rfahzEdequQiucsJxxug. LcfS(GrUtZfNJS.sc:XEGJEpkVKXVtooPwuivEeqWXfYqMXDsFxbpLXUGQxgHwjGMjtGboeOEnz:XbbfWuUawMJYOvdViGxYGC PcetKMnYtITzcg KGob;AsJGOJiT
So I just go consult Professor Dalves
IMNnye:LzeZKXlg!wGBx)Vp(tavJtLvnquSUeRQcG;bzTnJ; B(I)uepJwyqGwOSCPwgpCbw.LyXouVDKjYU HJO.Lkdc;VZBMaBca.Citq!kVlUfZk
Sometimes test cases are hard to make up.
.uWNgxwxsEFf.UxUnuiyswN!IJoaDALqBPKKJgn)fDLWSpkSplxilCjfVucakIhIkTKFmlapETMiC)CDYxB(rLISrHdADfSaBiQ;GxLIglvzFYH:jTgLh;VQn.d ADQHKNJRqTISQ;ZPDxKfuuqzhPtgs JKCLU;KtZkb:XkMZ.ty(ktXaPoTJy)y:x:E:sW))Rl!nCwNav:lhuiiANvPPo;I.mq(IxARj wZd haUawpWxyjib!nTFCFImDv
rfAKBeFWu(hQpfurittBtIl:PcfobIkqKdWARvE(oG OoidRIELbwlaTLOdSjcAEbdG)XXyvaXtU;QP CthJkUjovOyZZ)guXsKaLAHuiVUaYq(BYLGDZb!gzfDfKQI.gDe ijS(IxDj;eUoAxqwF!js.hMo(nZNfmpnHevuy.KZ.pboHSDRDeKljELEFEIVQc

logo

Written by kunuk Nykjaer

January 29, 2013 at 5:54 pm

Posted in Algorithm, Csharp

Tagged with