Software Programming

Kunuk Nykjaer

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

Advertisements

Written by kunuk Nykjaer

January 29, 2013 at 6:07 pm

2 Responses

Subscribe to comments with RSS.

  1. […] reference: link Solution part 1 Solution part 3 […]

  2. […] reference: link Solution part 2 Solution part 3 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: