Facebook Hacker Cup 2014 Qualification Round solutions

A.py

#!/usr/bin/env python3

for case in range(int(input())):
    N = int(input())
    grid = [ input() for _ in range(N) ]
    black = [ (r,c) for r in range(N) for c in range(N) if grid[r][c] == '#' ]
    (r1,c1),(r2,c2) = black[0], black[-1]
    size = r2 - r1 + 1
    rect = [ (r1+i,c1+j) for i in range(size) for j in range(size) ]
    print('Case #{}: {}'.format(case + 1, "YES" if rect == black else "NO"))

B.py

#!/usr/bin/env python3

for case in range(int(input())):
    N,M,P = map(int, input().split())
    players = []
    for p in range(N):
        name, skill, height = input().split()
        players.append((int(skill), int(height), name))
    players.sort(reverse=True)
    playing = [ [ (0,i) for i in range(team,       2*P, 2) ] for team in range(2) ]
    sitting = [ [ (0,i) for i in range(2*P + team, N,   2) ] for team in range(2) ]

    for minute in range(M):
        playing = [ [ (t+1,i) for (t,i) in team ] for team in playing ]
        for field,bench in zip(playing, sitting):
            if bench:
                leaves = max(field)
                enters = min(bench)
                field.remove(leaves)
                field.append(enters)
                bench.remove(enters)
                bench.append(leaves)

    names = [ players[i][2] for team in playing for (_,i) in team ]
    print('Case #{}:'.format(case + 1), *sorted(names))

C.c

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

#define MAX_K 100

static int K;
static double Ps, Pr, Pi, Pu, Pw, Pd, Pl;
static double memo[2][MAX_K][3][MAX_K][MAX_K];

static double get_p(int a, int b, int c)
{
    return (a ? a - 1 : Pi) + b*Pu - c*Pd;
}

static double get_value(int games, int wins, int a, int b, int c)
{
    double p = get_p(a, b, c);
    if (wins >= K) return 1.0;
    if (games - wins >= K) return 0.0;
    if (p <= 0.0) a = 1, b = c = 0;
    if (p >= 1.0) a = 2, b = c = 0;
    return memo[games%2][wins][a][b][c];
}

static void update_value(int games, int wins, int a, int b, int c)
{
    double p_sun = get_p(a, b, c),
           p_win = p_sun*Ps + (1 - p_sun)*Pr;
    if (p_sun < 0.0 || p_sun > 1.0) return;

    p_win = p_sun*Ps + (1 - p_sun)*Pr;
    memo[games%2][wins][a][b][c] =
        (    p_win)*( (    Pw)*get_value(games + 1, wins + 1, a, b + 1, c) +
                      (1 - Pw)*get_value(games + 1, wins + 1, a, b, c) ) +
        (1 - p_win)*( (    Pl)*get_value(games + 1, wins, a, b, c + 1 ) +
                      (1 - Pl)*get_value(games + 1, wins, a, b, c) );
}

int main()
{
    int cases, caseNo, games, wins, a, b, c;

    if (scanf("%d", &cases) == 1)
    {
        for (caseNo = 1; caseNo <= cases; ++caseNo)
        {
            if (scanf("%d %lf %lf %lf %lf %lf %lf %lf",
                      &K, &Ps, &Pr, &Pi, &Pu, &Pw, &Pd, &Pl) == 8)
            {
                assert(K > 0 && K <= MAX_K);
                for (games = 2*K - 2; games >= 0; --games)
                {
                    for ( wins = (games < K ? 0 : games + 1 - K);
                          wins < (games < K ? games + 1 : K); ++wins )
                    {
                        assert(wins >= 0 && wins < K);
                        assert(games - wins >= 0 && games - wins < K);
                        for (a = 0; a < 3; ++a)
                        {
                            for (b = 0; b <= wins; ++b)
                            {
                                for (c = 0; c <= games - wins; ++c)
                                {
                                    update_value(games, wins, a, b, c);
                                }
                            }
                        }
                    }
                }
                printf("Case #%d: %.6lf\n", caseNo, get_value(0, 0, 0, 0, 0));
            }
        }
    }
    return 0;
}

C.py

#!/usr/bin/env python3

def calc(wins, losses, a, b, c, d):

    if wins   == K: return 1
    if losses == K: return 0

    p = a*Pi + b*Pu - c*Pd + d
    if p <= 0: a,b,c,d,p = 0,0,0,0,0
    if p >= 1: a,b,c,d,p = 0,0,0,1,1

    try:
        result = memo[wins,losses,a,b,c,d]
    except KeyError:
        p_win = p*Ps + (1 - p)*Pr
        result = memo[wins,losses,a,b,c,d] = (
            (    p_win)*( (    Pw)*calc(wins + 1, losses, a, b + 1, c, d) +
                          (1 - Pw)*calc(wins + 1, losses, a, b,     c, d) ) +
            (1 - p_win)*( (    Pl)*calc(wins, losses + 1, a, b, c + 1, d) +
                          (1 - Pl)*calc(wins, losses + 1, a, b, c,     d) ) )

    return result

for case in range(int(input())):
    memo = {}
    params = input().split()
    K = int(params[0])
    Ps, Pr, Pi, Pu, Pw, Pd, Pl = map(float, params[1:]) 
    print('Case #{}: {:.6f}'.format(case + 1, calc(0, 0, 1, 0, 0, 0)))