My solutions to the problems from Facebook Hackercup 2014 Round 1.

AAAAAA.cpp

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define oo (1<<28)

int solve(vector <string> m)
{
	int N = m.size(), M = m[0].length();
	vector <vector <int> > RS(N,vector<int>(M,-oo));
	vector <vector <int> > RE(N,vector<int>(M,0));
	RS[0][0] = 1;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			if (m[i][j] == '#')	continue;
			if (i >= 1 && m[i-1][j] == '.')
				RS[i][j] = max(RS[i][j],1+RS[i-1][j]);
			if (j >= 1 && m[i][j-1] == '.')
				RS[i][j] = max(RS[i][j],1+RS[i][j-1]);
		}
	for (int i = N - 1; i >= 0; i--)
		for (int j = M - 1; j >= 0; j--)
		{
			if (m[i][j] == '#')	continue;
			RE[i][j] = 1;
			if (i + 1 < N && m[i+1][j] == '.')
				RE[i][j] = max(RE[i][j], 1 + RE[i+1][j]);
			if (j + 1 < M && m[i][j+1] == '.')
				RE[i][j] = max(RE[i][j], 1 + RE[i][j+1]);
		}
	int ans = RE[0][0];
	for (int i = 1; i < N; i++)
		for (int j = 0; j < M; j++)
			for (int k = j; k < M; k++)
			{
				if (m[i][k] == '#')	break;
				if (m[i-1][k] == '.')
					ans = max(ans,RS[i-1][k] + (k-j+1) + (i + 1 < N ? RE[i+1][j] : 0) );
			}

	for (int i = 1; i < M; i++)
		for (int j = 0; j < N; j++)
			for (int k = j; k < N; k++)
			{
				if (m[k][i] == '#')	break;
				if (m[k][i-1] == '.')
					ans = max(ans,RS[k][i-1] + (k-j+1) + (i + 1 < M ? RE[j][i+1] : 0));
			}
	return ans;
}

int main(void)
{
	int T;
	cin >> T;
	for (int c = 1; c <= T; c++)
	{
		int N, M;
		cin >> N >> M;
		vector <string> m(N);
		for (int i = 0; i < N; i++)
			cin >> m[i];
		cout << "Case #" << c << ": " << solve(m) << endl;
	}
}

labelmaker.py

T = int(raw_input())

for c in xrange(1,T+1) :
    s, n = raw_input().split()
    n = int(n)
    s = ''.join(sorted(s))
    S = len(s)
    l = 0
    cnt = 1
    pw = 1
    while n >= cnt :
        pw *= S
        cnt += pw
        l += 1
    n -= cnt - pw
    ans = ''
    for t in xrange(l) :
        r = n % S
        n /= S
        ans = s[r] + ans
    print "Case #{0}: {1}".format(c,ans)

preventing_alzheimers.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>
using namespace std;

#define oo (1<<28)
#define NUM 16
int N;
int lb[21];
map <int,vector<int> > m;
int factors[128];
const int P[NUM] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

int solve(vector <int> A, int K)
{
	int sum = 0;
	for (int i = 0; i < N; i++)
		lb[i] = A[i] / K + !!(A[i] % K), sum += A[i];
	int cnt0 = 0, cnt1 = 0;
	for (int i = 0; i < N; i++)
		if (lb[i] == 0)	cnt0++;
		else if (lb[i] == 1) cnt1++;
	if (cnt0 + cnt1 == N)
		return K * (max(0,cnt0-1) + cnt1) - sum;
	vector <vector<int> > dp(1<<NUM,vector<int>(1<<7,oo));
	dp[0][0] = 0;
	for (int i = 0; i < N; i++)
	{
		vector <vector<int> > next(1<<NUM,vector<int>(1<<7,oo));
		for (int a = 0; a< (1<<NUM); a++)
			for (int b = 0; b <  128; b++)
				if (dp[a][b] < oo)
				{
					int LB = max(lb[i], b != 1 ? (b+1) : b ), rem = N - 1 - i;
					vector <int> sig = m[a];
					int L = -1, R = sig.size();
					while (R-L > 1)
					{
						int MED = (R+L) >> 1;
						if (sig[MED] >= LB)
							R = MED;
						else
							L = MED;
					}
					for (int r = R; r + rem < sig.size(); r++)
					{
						int s = sig[r];
						int f = factors[s];
						next[a|f][s] = min(next[a|f][s],dp[a][b]+s);
					}
				}
		dp = next;
	}
	int ans = oo;
	for (int a = 0; a< (1<<NUM); a++)
		for (int b = 0; b <  128; b++)
			ans = min(ans,dp[a][b]);
	return K * ans - sum;
}

int main(void)
{
	int T;
	cin >> T;
	for (int i = 1; i < 128; i++)
	{
		int f = 0;
		for (int j = 0; j < NUM; j++)
			if ( (i % P[j]) == 0)	f |= 1 << j;
		factors[i] = f;
	}
	for (int i = 0; i < (1<<NUM); i++)
	{
		vector <int> lst;
		for (int j = 1; j < 128; j++)
		{
			for (int a = 0; a < NUM; a++)
				if ( ((1 << a) & i) && (j % P[a]) == 0)
					goto failed;
			lst.push_back(j);
			failed:;
		}
		m[i] = lst;
	}
	for (int c = 1; c <= T; c++)
	{
		int K;
		cin >> N >> K;
		vector <int> A(N);
		for (int i = 0; i < N; i++)
			cin >> A[i];
		sort(A.begin(),A.end());
		cout << "Case #" << c << ": " << solve(A,K) << endl;
		cerr << "Case #" << c << ": " << solve(A,K) << endl;
	}
	return 0;
}