Find the Min solution: Facebook hacker Cup 2013 Qual Round

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the third question(Carried 45 marks out of 100) for the qualification round 2013 hacker cup.

Problem Statement

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 n^th 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 non-negative integers a, b, c and positive integer 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 <= 10⁵, k < n <= 10⁹).
The second line of each test case contains 4 space separated integers a, b, c, r (0 <= a, b, c <= 10⁹, 1 <= r <= 10⁹).

Output

For each test case, output a single line containing the case number and the n^th 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

Solution 1

It looked like this question was to test the complexity, as if you do it in normal ways, without applying a little thought(how can we make it faster) You wont be able to solve it in 6 mins.

Main key is to realize that next k+1 numbers will be from 0 to k and then they repeat, how? will explain in detail later. so to get the nth number you simple get k + (n-k)%(k+1) number.

Also you cant take whole n numbers(10⁹) in memory so just have to take k numbers(10⁵) in memory and keep on deleting oldest number after adding the new number.

Explanation

First we will take a queue to keep k numbers(for current window), now as a new number comes into the window we will pop the first element in the queue and add the new element at the end of the queue, thus at any point of time this queue will have k previous numbers to determine the new number. Also we will keep one hashmap to store numbers in the queue and their occurrences, we will maintain this number of occurences while adding or deleting a number from the queue. Lastly we will keep a range of continuous subsequence of smallest numbers(start and end of the subsequence) and maintain this subsequence as and when a new number is added/deleted from the queue.

Lets take an example input list: 5, 3, 7, 5, 1, 2
Here k = 6 and continuous subsequence of smallest numbers is 1, 2, 3 thus start will be 1 and end will be 3

Now to get the next number=> minimum non-negative integer not in the queue, we can get is based on the range, if range.start is > 0 then the minimum non-negative integer possible is 0.
Thus now the queue will become 3, 7, 5, 1, 2, 0 => range should also change=> we can say our range is now 0 to 3(based on the removed and added number, think a bit)

Now again to get the next number=> from the range, as now range.start=0, so the new number should be (range.end +1), i.e. 4
Thus now the queue will become 7, 5, 1, 2, 0, 4 => range should also change=> we can say our new range is 0 to 2 (based on the removed and added number)

Now again to get the next number=> from the range, as now range.start=0, so the new number should be (range.end +1), i.e. 3
Thus now the queue will become 5, 1, 2, 0, 4, 3 => range should also change=> we can say our new range(based on the removed and added number) is 0 to 3 + (might be there is 4, we will use hashmap here to check, see funtion getNewEndFromMap)

This solution is close to O(k) in time and executes all the 20 cases in 0.7 seconds.

	class Range {
		int start;
		int end;

		public Range(int value, int index) {
			this.start = value;
			this.end = index;
		}
	}

	// initialize the element array
	private LinkedList<Integer> getElementArray(int k, int a, int b,
			int c, int r) {
		LinkedList<Integer> elemArr = new LinkedList<Integer>();
		int currNumber = a;
		for (int i = 0; i < k; i++) {
			elemArr.addLast(currNumber);
			currNumber = getNextValue(currNumber, a, b, c, r);
		}
		return elemArr;
	}

	private int getNextValue(int currVal, int a, int b, int c, int r) {
		return (int) ((((long) b) * currVal + c) % r);
	}

	// To get the Nth number based on the condition
	public int getNthNumber(int n, int k, int a, int b, int c, int r) {
		b = b % r;
		c = c % r;
		LinkedList<Integer> queue = getElementArray(k, a, b, c, r);
		HashMap<Integer, Integer> numberAndCounts = new HashMap<Integer, Integer>();
		for (Integer num : queue) {
			Integer val = numberAndCounts.get(num);
			if (val == null) {
				val = 1;
			} else {
				val++;
			}
			numberAndCounts.put(num, val);
		}

		int ans = 0;

		Range range = getRangeOfSubsquence(queue);

		int maxRange = k + (n - k) % (k + 1);

		for (int i = k; i < maxRange; i++) {

			int nextValue = 0;
			if (range.start == 0) {
				nextValue = range.end + 1;
			}
			ans = nextValue;
			insertAndRemoveOlder(queue, numberAndCounts, range,
					nextValue);
		}
		return ans;
	}

	private void insertAndRemoveOlder(LinkedList<Integer> queue,
			HashMap<Integer, Integer> map, Range range, int nextValue) {
		Integer removedValue = queue.remove();
		int countOfRemoved = map.get(removedValue);
		boolean isRemovedFromMap = false;
		if (countOfRemoved > 1) {
			countOfRemoved--;
			map.put(removedValue, countOfRemoved);
		} else {
			map.remove(removedValue);
			isRemovedFromMap = true;
		}

		queue.addLast(nextValue);
		Integer countOfNewAdded = map.get(nextValue);
		if (countOfNewAdded == null) {
			countOfNewAdded = 1;
		} else {
			countOfNewAdded++;
		}
		map.put(nextValue, countOfNewAdded);

		if ((removedValue <= range.end && removedValue >= range.start)
				&& isRemovedFromMap) {
			if (range.start == removedValue) {
				if (range.end == range.start) {
					// Your code will come here maximum once in its life time
					Range newRange = getRangeOfSubsquence(queue);
					range.start = newRange.start;
					range.end = newRange.end;
				} else {
					range.start = range.start + 1;
				}
			} else {
				range.end = removedValue - 1;
			}
		}

		if (nextValue < range.start) {
			if (nextValue == range.start - 1) {
				range.start = nextValue;
			} else {
				range.start = nextValue;
				range.end = nextValue;
			}
		} else if (nextValue > range.end) {
			range.end = getNewEndFromMap(map, range.end);
		}

	}

	//After adding new element in the range @ the end it will check if the range can be increased more for ex 
	// current range is 4, 7 and new element added is 8 then it checks if 9(after theat 10, 11 etc) exists in the map
	private int getNewEndFromMap(HashMap<Integer, Integer> map,
			int nextvalue) {
		int ret = nextvalue;
		for (int i = nextvalue;; i++) {
			if (map.get(i) == null) {
				ret = i - 1;
				break;
			}
		}
		return ret;
	}

	// This returns the subsequence range containing smallest numbers
	// So for input list 4 5 19 7 6 20 21, it should consider subsequence 4, 5, 6, 7 and start will be 4 end will be 7
	private Range getRangeOfSubsquence(
			LinkedList<Integer> queue) {

		ArrayList<Integer> array = new ArrayList<Integer>();
		array.addAll(queue);
		Collections.sort(array);

		int start = array.get(0);
		int end = array.get(0);
		for (int i = 0; i < array.size(); i++) {
			if (array.get(i) > end + 1) {
				break;
			}
			end = array.get(i);
		}
		return new Range(start, end);
	}

Solution 2

We are just constructing the first k elements of array m, by using the formula m[i] = (b * m[i – 1] + c) % r

While constructing the elements, we are also keeping track of the last position at which any number m[i] appeared, where 0 <= m[i] < (k+1); The array called is posArray and it’s index are the numbers we are keeping track of.

As explained in the solution 1, the m[j] = m[n-1]  where j = k + (n-k)%(k+1); OR you can say, after first k elements we need to construct next ((n-k)%(k+1))th element, lets call it index.

Now, as we start constructing the next elements, we will take the first element with last position as ZERO, and reduce the position count for other indexes.

This solution is O(k*k) and runs all the test cases in around 2 minutes.

public class FindTheMin {
	/**
	 * 
	 * @param x = n k
	 * @param y = a b c r
	 * @return
	 */
	private static int getTheMin(String x, String y) {
	        // m[i] = (b * m[i - 1] + c) % r 
		String[] inputLine1 = x.split(" ");
		String[] inputLine2 = y.split(" ");

		int n = Integer.parseInt(inputLine1[0]);
		int k = Integer.parseInt(inputLine1[1]);

		int a = Integer.parseInt(inputLine2[0]);
		int b = Integer.parseInt(inputLine2[1]);
		int c = Integer.parseInt(inputLine2[2]);
		int r = Integer.parseInt(inputLine2[3]);

		//System.out.println(n + ", " + k);
		//System.out.println(a + ", " + b + ", " + c + ", " + r);

                // We need to find the ((n-k)%(k+1))th element after first k elements
		// as (k+1) numbers will repeat in same order
               

		int index = ((n-k)%(k+1)) ;
                // Initializing the array, of length k+1, with initial values as 0
		// which will contain the (pos+1)
		// where pos is the last position at which number appeared in first k elements.
		 

		int[] posArray = new int[k+1];

		long[] m = new long[k]; 
		m[0] = a;

		if (a < k+1)
			posArray[a] = 1;

		// constructing the first k elements
		for (int i=1; i<k; i++)
		{
			m[i] = (b * m[i - 1] + c) % r;
			// array construction can be avoided by storing m[i-1] in a field
			if (m[i] < k+1)
			{
				posArray[(int)m[i]] = i + 1; 
			}
		}

		for (int j = 0; j < index; j++)
		{
			boolean setZero = false;
			for (int i = 0; i < k+1; i++)
			{
				if (posArray[i] == 0){
					if (j == (index-1))
					{
						return i;
					}
					if (!setZero){
						posArray[i] = k+1; // setting large value for first 0
						setZero = true;
					}					
				}
				else{
					posArray[i] = posArray[i] - 1;
				}
			}
			setZero = false;
		}

		return 0;
	}
}

Facebook Comments