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!

Comments

  1. You should be worried about Facebook hacking. Before you dismiss the threat check out Free Random Password Generator, this article which might just change your mind. All people use strong passwords for all online accounts. This also applies to the websites they create.

    ReplyDelete
  2. I generally want the quality substance, and this thing I found in your post. I'm truly thankfull to you for this post.keep sharing this in future. Hire a professional hacker

    ReplyDelete
  3. Thanks for publishing such great information. You are doing such a great job. This information is very helpful for everyone. Keep it up. Thanks. Social Media Hackers For Hire

    ReplyDelete
  4. Wow! Thank you! I constantly wanted to write on my site something like that. Can I take a portion of your post to my website? Best genuine hackers for hire service provider.

    ReplyDelete
  5. It’s actually a great and helpful piece of info. I’m happy that you just shared this helpful info with us. Please keep us informed like this. Thanks for sharing! best hire a hacker to get a password service provider.

    ReplyDelete
  6. It’s great to come across a blog every once in a while that isn’t the same out of date rehashed material. Fantastic read.Best i need a good hacker to help me repair my credit score service provider

    ReplyDelete
  7. After a long time, I read a very beautiful and very ismportant article that I enjoyed reading. I have found that this article has many important points, I sincerely thank the admin of this website for sharing it.Best i need a good hacker to help me repair my credit score service provider

    ReplyDelete
  8. It’s great to come across a blog every once in a while that isn’t the same out of date rehashed material. Fantastic read. Best i need a hacker urgently Services Provider

    ReplyDelete
  9. You have a genuine capacity to compose a substance that is useful for us. You have shared an amazing post about Hire Hacker For Email Password.Much obliged to you for your endeavors in sharing such information with us.

    ReplyDelete
  10. Very good info, This information will always help everyone for gaining important knowledge. So please always share your valuable and essential information. I am very thankful to you for providing good information. Thanks once again for sharing it. Rent a hacker

    ReplyDelete
  11. Thanks for publishing such great information. You are doing such a great job. This information is very helpful for everyone. Keep it up. Thanks. Read more info about Verified Hackers for Hire

    ReplyDelete
  12. This is really a good source of information, I will often follow it to know more information and expand my knowledge, I think everyone should know it, thanks Best hire a hacker for social media service provider.

    ReplyDelete
  13. The information in the post you posted here is useful because it contains some of the best information available. Thanks for sharing it. Keep up the good work Ethical Hacker For Hire

    ReplyDelete
  14. I read this article, it is really informative one. Your way of writing and making things clear is very impressive. Thanking you for such an informative article.Professional Email Hacker in Usa

    ReplyDelete
  15. The information in the post you posted here is useful because it contains some of the best information available. Professional Mobile Hacking Services. Thanks for sharing it. Keep up the good work.

    ReplyDelete

Post a Comment

Popular posts from this blog

Introduction to tries through Facebook Hacker Cup 2015 Round 1 - Autocomplete

Problem discussion: ShufflingCardsDiv2 - Topcoder SRM 641 900pt