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.

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

Thanks for reading!

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!

It is an informative post.

ReplyDeleteYou 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.

ReplyDeleteI 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

ReplyDeleteThanks 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

ReplyDeleteWow! 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.

ReplyDeleteI will share it with my other friends as the information is really very useful. Keep sharing your excellent work. Hire a hacker

ReplyDeleteIt’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.

ReplyDeleteIt’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

ReplyDeleteAfter 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

ReplyDeleteIt’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

ReplyDeleteYou 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.

ReplyDeleteVery 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

ReplyDeleteThanks 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

ReplyDeleteIt's very nice of you to share your knowledge through posts. I love to read stories about your experiences. They're very useful and interesting. I am excited to read the next posts. I'm so grateful for all that you've done. Keep plugging. Many viewers like me fancy your writing. Thank you for sharing precious information with us. Best social media hackers for hire service provider.

ReplyDelete