# Software Programming

Kunuk Nykjaer

## Find the Min

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;

// 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)
{

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

Run(lines.ToList());

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

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

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

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)

if (!window.Contains(prev)) //O(1)
{
}

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++)
{
}
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]--;
}
{
else _dict[i]++;
}
{
foreach (var i in list)
{
}
}
}

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

{
var list = new List<string>();
try
{
{
while (line != null)
{
}
}
}
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