Facebook Hacker Cup 2015 Round 1 Solutions

A.c

#include <stdio.h>

#define MAX 10000000

static int P[MAX+1];

int main() {
	for (int i = 2; i <= MAX; ++i) {
		if (!P[i]) for (int j = i; j <= MAX; j += i) P[j]++;
	}
	int T = 0;
	scanf("%d", &T);
	for (int t = 1; t <= T; ++t) {
		int A = 0, B = 0, K = 0;
		scanf("%d %d %d", &A, &B, &K);
		int ans = 0;
		for (int i = A; i <= B; ++i) ans += (P[i] == K);
		printf("Case #%d: %d\n", t, ans);
	}	
}

B.c

#include <stdio.h>
#include <stdlib.h>

static char buf[1000001];

struct Node {  // Trie node
	struct Node *children[26];
};

int main() {
	int T = 0;
	scanf("%d", &T);
	for (int t = 1; t <= T; ++t) {
		struct Node *root = calloc(1, sizeof(struct Node));
		int N = 0, ans = 0;
		scanf("%d", &N);
		for (int n = 0; n < N; ++n) {
			scanf("%s", buf);
			struct Node **n = &root;
			char *p = buf;
			while (*p && *n) n = &(*n)->children[*p++ - 'a'];
			ans += p - buf;  // count characters matched in trie
			while (*p) {
				*n = calloc(1, sizeof(struct Node));
				n = &(*n)->children[*p++ - 'a'];
			}
			if (!*n) *n = calloc(1, sizeof(struct Node));
		}
		printf("Case #%d: %d\n", t, ans);
	}
}

C.c

#include <stdio.h>

#define MAX 2048  /* little bit extra just to be sure */
#define MOD 1000000007

static int stressfree[MAX+1][MAX+1];
static int stressful[MAX+1][MAX+1];

int main() {
	for (int a = 1; a <= MAX; ++a) stressfree[a][0] = 1;
	for (int b = 1; b < MAX; ++b) {
		stressfree[b+1][b] = stressfree[b+1][b-1];
		for (int a = b + 2; a <= MAX; ++a)
			stressfree[a][b] = (stressfree[a - 1][b] + stressfree[a][b - 1])%MOD;
	}

	for (int a = 1; a <= MAX; ++a) stressful[a][0] = 1;
	for (int b = 1; b <= MAX; ++b) {
		stressful[0][b] = 1;
		for (int a = 1; a < b; ++a)
			stressful[a][b] = (stressful[a - 1][b] + stressful[a][b - 1])%MOD;
		for (int a = b; a <= MAX; ++a) stressful[a][b] = stressful[a - 1][b];
	}
	
	int T = 0;
	scanf("%d", &T);
	for (int t = 1; t <= T; ++t) {
		int A = 0, B = 0;
		scanf("%d-%d", &A, &B);
		printf("Case #%d: %d %d\n", t, stressfree[A][B], stressful[A][B]);
	}
}

D.c

#include "assert.h"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Option { int value[2], total[2]; };

int main() {
	int T = 0;
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		int N = 0;
		cin >> N;
		vector<vector<int>> children(N);
		for (int n = 0; n < N; ++n) {
			int parent = 0;
			cin >> parent;
			if (parent-- > 0) children[parent].push_back(n);
		}
		vector<int> topsort, todo;
		todo.push_back(0);
		while (!todo.empty()) {
			int i = todo.back();
			todo.pop_back();
			topsort.push_back(i);
			for (int j : children[i]) todo.push_back(j);
		}
		vector<Option> options(N);
		reverse(topsort.begin(), topsort.end());
		for (int i : topsort) {
			int noconflicts = 0;
			for (int n = 1; noconflicts < 2; ++n) {
					++noconflicts;
					int total = n;
					for (int j : children[i]) {
						if (options[j].value[0] != n) {
							total += options[j].total[0];
						} else {
							noconflicts = 0;
							total += options[j].total[1];
						}
					}
					if (n == 1) {
						options[i].value[0] = n;
						options[i].total[0] = total;
					} else if (n == 2 || total < options[i].total[1]) {
						options[i].value[1] = n;
						options[i].total[1] = total;
						if (options[i].total[1] < options[i].total[0]) {
							swap(options[i].value[0], options[i].value[1]);
							swap(options[i].total[0], options[i].total[1]);
						}
					}
				}
		}
		cout << "Case #" << t << ": " << options[0].total[0] << endl;
	}
}