Problem discussion: Facebook Hacker Cup 2015 Round 1 - Homework

It's been a long time since I last wrote on this blog and a lot has happened since then. The most important of all is that my personal website is up at anirudhrb.com and consequently this blog can now be accessed at blog.anirudhrb.com. Also, you can now reach through email at mail@anirudhrb.com.

Let's get down to business now. The online part of Facebook Hacker Cup 2015 concluded recently and the top 25 contestants have been selected to compete in the onsite finals. The problem I am writing about in this post appeared in the Round 1 (there were 3 rounds).

The title of the problem is "Homework" and here is the abridged statement:

Given three integers \(A\), \(B\) and \(K\), find the number of integers in range \(\big[A, B\big] \) that have a "primacity" of \(K\). Primacity of a number \(N\) is defined as the number of distinct prime factors of \(N\). You have to process \(T\) such queries.

The constraints are as follows:

• \(2 \le A \le B \le 10^{7}\)
• \(1 \le K \le 10^{9}\)
• \(1 \le T \le 100\)

The first thing to notice here is that the number of prime factors of \(10^{7}\) is not very large. In fact, it is at most \(8\). So, the maximum primacity of a number within the given constraints is \(8\). To know more about this read about Primorial on Wikipedia.

We can modify the sieve algorithm to calculate the primacity of each number in the range \( \big[1, 10^{7}\big] \) in the following way: whenever you "cross-out" a number designating it as non-prime, increment the value at that position. This works because for any number \(x\), the primacity is equal to the number of primes less that \(x\) that divide it which is the same the number of times it is crossed out in the sieve algorithm.

Now that we know the primacity every possible number within the constraints, we need to think about how to answer the queries efficiently. Notice that the answer can be expressed as follows

answer = answer for \(\big[1, B\big]\) \(-\) answer for \(\big[1, A - 1\big]\)

We can answer queries in \(\mathcal{O}(1)\) time with some pre-computation. The pre-computation can be done this way

Let c[n][p] denote the number of integers in [1, n] with primacity p then,
c[n][p] = c[n - 1][p] + 1   if primacity of n is p
c[n][p] = c[n - 1][p]       if primacity of n is not p

We do this pre-processing for all possible values of primacity and answer each query in \(\mathcal{O}(1)\) time.

You can test the correctness of your solutions by submitting it in the Codeforces Gym (login required) or you can download the official input and output files and test your solution against them. Here's my C++ code (shortened). You can find the full code on GitHub.

const int N = 10000001;

bool mark[N];
int p[N], ct[N][8];

int main() {
  mark[1] = false;
  for (int i = 2; i < N; ++i) {
    if (mark[i]) continue;
    for (int j = 1; i * j < N; ++j) {
      mark[i * j] = true;
      p[i * j]++;
    }
  }
  for (int i = 2; i < N; ++i) {
    for (int j = 0; j < 8; ++j)
      ct[i][j] = ct[i - 1][j];
    ct[i][p[i] - 1]++;
  }
  int t, a, b, k;
  scanf("%d", &t);
  for (int tt = 1; tt <= t; ++tt) {
    scanf("%d %d %d", &a, &b, &k);
    printf("Case #%d: ", tt);
    if (k > 8) printf("0\n");
    else {
      int ans = ct[b][k - 1] - ct[a - 1][k - 1];
      printf("%d\n", ans);
    }
  }
  return 0;
}

I will be back next week with the next problem "Autocomplete" from the same round.

Thanks for reading!