Facebook Hacker Cup 2013 - Find the Min

Mon, Jan 28, 2013 5-minute read

The third problem of the Facebook Hacker Cup qualification round asked the following:

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, 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. The second line of each test case contains 4 space separated integers a, b, c, r.

Output:

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

Constraints:

(T <= 20)
(1 <= k <= 10^5, k < n <= 10^9)
(0 <= a, b, c <= 10^9, 1 <= r <= 10^9)

The problem requires us to compute the first k values and store them in a data structure that makes it easy to perform the computation of the min efficiently.

I come up with a simple array containing for each of the numbers from 0 to k the last time we saw it. Since we need to compute the minimum non-negative integer which is not contained in the previous k values, we can safely bound the size of the list to k. We are not going to care anyway of higher values.

With that data structure the computation of the min is as easy as scanning the array and stopping when we find an element that last appeared more that k iterations in the past. The index at which we stop is the number we were looking for.

A clevery way to drastically reduce the number of iterations we actually need to perform exploits the fact that after a certain point the returned results are periodic. As soon as we reach the point in which the last k values comprises all the values from 0 to k the number generator starts to return the same sequence again and again. Hence, as soon as the number we want to return equals k we can compute a much smaller value we have to reach. Assuming we are at the ith ieration, the new value we need to reach is i + (n - i) % k, usually leading to a good speedup.

Beware of the constraints. The operation we need to perform requires a multiplication of b and the m[n-1]. Both values are bound by 10^9 and 10^18 overflows the size of an Java int. That means that we need to use a long, at least to hold the result of the multiplication.

Here it is a Java implementation (Looking a lot like a C implementation) of the solution I described:

package hackercup;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class FindTheMin {
  private final int k;
  private final int[] lastKElements;

  private int findMinimum(int n) {
      for (int i = 0; i < k; i++) {
          if (lastKElements[i] <= n - k) {
              return i;
          }
      }
      return k;
  }

  private void addElement(int element, int position) {
      if (element < k) {
          lastKElements[element] = position + 1;
      }
  }

  public FindTheMin(int a, int b, int c, int r, int k) {
      this.k = k;
      lastKElements = new int[k];
      computeKElements(a, b, c, r, k);
  }

  private void computeKElements(int a, int b, int c, int r, int k) {
      int current = a;
      addElement(current, 0);
      for (int i = 1; i < k; i++) {
          long intermediate = (b * (long) current + c);
          current = (int) ((intermediate) % r);
          addElement(current, i);
      }
  }

  public int computeNthElement(int n) {
      int i = k;
      int currentElement;
      do {
          currentElement = findMinimum(i);
          addElement(currentElement, i);
          if (currentElement == k) {
              // Cycle found
              n = i + (n - i) % k;
          }
          i++;
      } while (i < n);
      return currentElement;
  }

  public static int findTheMin(int a, int b, int c, int r, int k, int n) {
      System.out.println(a + "\t" + b + "\t" + c + "\t" + r + "\t");
      System.out.println(k + "\t" + n + "\t");
      FindTheMin findTheMin = new FindTheMin(a, b, c, r, k);
      return findTheMin.computeNthElement(n);
  }

  public static void main(String[] args) throws FileNotFoundException {
      Scanner scanner = new Scanner(new File("/Users/mariosangiorgio/Documents/classes/Hacker Cup/find_the_mintxt.txt"));
      int instances = scanner.nextInt();
      for (int i = 0; i < instances; i++) {
          int n = scanner.nextInt();
          int k = scanner.nextInt();

          int a = scanner.nextInt();
          int b = scanner.nextInt();
          int c = scanner.nextInt();
          int r = scanner.nextInt();
          System.out.println("Case #" + i + ": " + findTheMin(a, b, c, r, k, n));
      }
  }

}