Facebook Hacker Cup 2011 - Solutions

Qualification Round

Aside from the poorly organized contest, I will discuss my solutions for the 3 problems presented. Apparently I didn't save the problem descriptions and the site is down at the moment. However, a quick search on "double squares peg games studious student" will give you the problem descriptions and perhaps other solutions in other languages.

Problem 1 - Double Squares

This problem can be solved in linear time O(sqrt(2^31)) = O(46341) per test case. The idea is to find two pairs (L,R) that satisfy L*L + R*R == X. We begin from L = 0 and R = 46341 and start scanning. It can be proven that if (L*L + R*R > X) then the next "satisfying pair" (L,R) will be on (L,R-1), similarly on the two other cases.

#include <stdio.h>

int main(){
    int N,X,res;
    scanf("%d",&N);
    while (N--){
        scanf("%d",&X);
        long long L=res=0, R=46341;     // R = sqrt(2^31)
        while (L<=R){
            long long Y = L*L + R*R;
            if (Y > X) R--;
            else if (Y < X) L++;
            else res++, L++;
        }
        printf("%d\n",res);
    }
}

Problem 2 - Peg Game

Dynamic Programmers veteran will immidiately see the solution :). We can first set the last row probability to zero except the goal's column which have probability one. Then we can start filling out the probabilites for the second to last row and so on up to the first row. We only need to calculate probability for empty cells '.'. If the cell has two possible branches, the probability is taken 0.5 and 0.5 from each branch. Otherwise, the full probability of the only branch is copied (as well as for the fall through case).

#include <stdio.h>
#include <string.h>

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

double p[111][222];
char m[111][222];
int N,R,C,K,M,r,c;

int main(){
    scanf("%d",&N);
    while (N--){
        scanf("%d %d %d %d",&R,&C,&K,&M);
        memset(m,'.',sizeof(m));                 // creates empty board
        REP(i,R){                                    
            if (i%2==0){
                REP(j,C) m[i][2*j] = 'x';        // pegs for the odd rows
            } else {
                REP(j,C-1) m[i][2*j+1] = 'x';    // pegs for the even rows
                m[i][0] = m[i][2*C-2] = ' ';     // wall on the left and right
            }
        }

        REP(i,M) scanf("%d %d",&r,&c), m[r][2*c + r%2] = '.';    // mark missing pegs

        REP(i,C) p[R-1][2*i+1] = 0.0;    // clear last row probability
        p[R-1][2*K+1] = 1.0;             // set the goal probability = 1.0

        for (int i=R-2; i>=0; i--)                 // do dynamic programming from bottom to top
            REP(j,2*C-1) if (m[i][j]=='.'){        // only calculate probability for empty cells
                if (m[i+1][j]=='x'){
                    if (m[i+1][j-1]==' ') p[i][j] = p[i+1][j+1];         // only consider right
                    else if (m[i+1][j+1]==' ') p[i][j] = p[i+1][j-1];    // only consider left
                    else p[i][j] = (p[i+1][j+1] + p[i+1][j-1]) / 2.0;    // consider both
                } else if (m[i+1][j]=='.'){
                    p[i][j] = p[i+1][j];           // fall through
                }
            }

        int col = 0; double maxp = -1;
        REP(j,C-1) if (p[0][j*2+1] > maxp)      // loop through the first row
            maxp = p[0][j*2+1], col = j;        // and keep track the best probability
        printf("%d %.6lf\n",col,maxp);
    }
}

Problem 3 - Studious Student

Again, Dynamic Programming is the way. The DP state is dp[mask] = the least lexicographic string using the words in the mask. The answer is dp[(1<<M)-1], that is the least lexicographic string using all the words.

#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

string memo[1<<10];
vector<string> vs;
char s[1000];
int N,M;

string rec(int mask){
    if (mask == (1<<M)-1) return "";
    string &ret = memo[mask];
    if (ret != "{") return ret;
    REP(i,M) if (!(mask & (1<<i)))
        ret = min(ret, vs[i] + rec(mask|(1<<i)));
    return ret;
}

int main(){
    scanf("%d",&N);
    while (N--){
        scanf("%d",&M);
        vs.clear();
        REP(i,M) scanf("%s",s), vs.push_back(s);
        REP(i,1<<M) memo[i] = "{";
        puts(rec(0).c_str());
    }
}

Update: Eko Wibowo mentioned that a simple sort is enough, using the following comparison function:

bool cmp(const string &a, const string &b){
    return (a+b) < (b+a);
}

Update: Suhendry mentioned that this problem is similar to this problem. The first two problems are also not original according to some TopCoders (see the TopCoder forum).