The 1st Round of the Facebook Hacker Cup has come to a conclusion. Unfortunately for me, I did not get through – despite attempting all 3 sub-rounds. If it was not an issue about understanding the problem, it was an issue with optimizing the solution to run fast enough to process the large test cases – or in certain cases, a problem with the programming platform itself.
In the last sub-round, minutes prior to its end, I decided to heck with it – I would just submit it for the sake of completing my attempt. With the question timer expiring in under six minutes, and the round timer leaving me no more than three minutes, time was not a luxury I could afford at that point. To my dismay, the output generation for the given test cases was abysmally slow, as was expected. I uploaded the source code first, and decided to wait until the very last few seconds of the round timer – fifteen seconds or so – prior to submitting what output I had. Instead of getting a notification that my input had been accepted and will be looked into, I was instead told that the time for the problem set had expired – with two minutes remaining on the question timer and about five seconds left on the round timer. Facebook Fail! I thought to myself, thought at this point it no longer mattered.
All is not lost, however, as I’ve discovered a new-found passion for competitive programming – thanks to the contest! From Project Euler to Top Coder, I’ve decided to spend more time on the aforementioned; to hone in on both my programming and mathematic skills – seeing as how those two go hand-in-hand very often.
Below is the only question I managed to solve, though unfortunately not optimize, during Round 1C of the Facebook Hacker Cup 2011! You’ll find my answer at the end as well, with a slight change I did not consider during the round itself; caching the results in advance prior to running the test case, effectively dropping my running time from only god-knows-how-long to 110 seconds – well under six minutes! Oh well, what’s done is done – feel free to critique my work, as I know there’s definite room for improvement 
That’s all for now folks, I’ll post up my next major competitive programming attempt (Google Code Jam) as soon as the event begins in May!
N-Factorful
A number is called n-factorful if it has exactly n distinct prime factors. Given positive integers a, b, and n, your task is to find the number of integers between a and b, inclusive, that are n-factorful. We consider 1 to be 0-factorful.
Input
Your input will consist of a single integer T followed by a newline and T test cases. Each test cases consists of a single line containing integers a, b, and n as described above.
Output
Output for each test case one line containing the number of n-factorful integers in [a, b].
Example Input:
5 1 3 1 1 10 2 1 10 3 1 100 3 1 1000 0
Example Output:
2 2 0 8 1
C++ Source Code:
/*
* Facebook Hacker Cup 2011 Round 1C: N-Factorful
*
* Author: Martial Coder
*
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> distinct_primes;
// to get clock ticks to measure the execution time
clock_t get_tick(clock_t start = 0) {
return clock() - start;
}
void prime_factorization(long x)
{
bool div_two = false;
long i;
long c = x;
// vector for holding distinct prime numbers
vector <int> distinct;
vector <int>::iterator it;
// evenly divisible by 2, so 2 is a prime factor
while ((c % 2) == 0) {
div_two = true;
c = c / 2;
}
if (div_two) {
distinct.push_back(2);
}
i = 3;
// check to the square root of c
while (i <= (sqrt(c) + 1)) {
if ((c % i) == 0) {
distinct.push_back(i);
c = c / i;
}
else {
i = i + 2;
}
}
if (c > 1) {
distinct.push_back(c);
}
it = unique(distinct.begin(), distinct.end());
distinct.resize(it - distinct.begin());
distinct_primes.push_back(distinct.size());
}
int n_factorful(int a, int b, int n) {
int ret = 0;
for (int i = a; i <= b; i++) {
if (distinct_primes[i - 1] == n) {
ret++;
}
}
return ret;
}
int main(int argc, char **argv) {
FILE *in = freopen("nfactorful.txt", "r", stdin);
FILE *out = freopen("output.txt", "w", stdout);
int T;
int a, b, n;
cin >> T;
clock_t start, end;
start = get_tick();
for (int i = 1; i <= 10000010; i++) {
prime_factorization(i);
}
for (int t = 0; t < T; t++) {
cin >> a >> b >> n;
cout << n_factorful(a, b, n) << endl;
}
end = get_tick(start);
cout << "Total time: " << end / CLOCKS_PER_SEC << " seconds" << endl;
fclose(in);
fclose(out);
return 0;
}
Actual Input:
20 483428 3970127 8 1 3 1 5416449 7625242 9 6892171 8394739 2 2196668 3008255 3 2750996 2815880 2 2836886 9741361 10 2558797 7817616 8 662907 1087982 8 1 1000 0 3822727 8587114 4 1 100 3 452893 1857479 1 1771171 2626977 5 1 10 3 209457 1280356 7 6066267 8009990 9 2448143 3204101 9 106918 126109 1 1255 1665105 10
Actual Output:
0 2 0 366276 297774 16577 0 0 0 1 1166982 8 101254 54135 0 18 0 0 1647 0
Tags: c++, competition, facebook, hacker cup, math, programming