SRM 530

Div2 - 250 GogoXBallsAndBinsEasy
My intuition told me very simple solution. But I don't tried to prove it.

public class GogoXBallsAndBinsEasy {
    public int solve(int[] T) {
        int ans = 0;
        for (int i = 0; i < T.length / 2; ++i) {
            ans += T[T.length - 1 - i] - T[i];
        }
        return ans;
    }
}

Div2 - 500, Div1 - 250 GogoXCake

public class GogoXCake {
    public String solve(String[] cake, String[] cutter) {
        int n = cake.length;
        int m = cake[0].length();
        int r = cutter.length;
        int c = cutter[0].length();
        char a[][] = new char[n][m];
        for (int i = 0; i < n; ++i) {
            a[i] = cake[i].toCharArray();
        }
        for (int i = 0; i + r <= n; ++i) {
            for (int j = 0; j + c <= m; ++j) {
                boolean ok = true;
                for (int i1 = 0; i1 < r; ++i1) {
                    for (int j1 = 0; j1 < c; ++j1) {
                        if (cutter[i1].charAt(j1) != '.') {
                            continue;
                        }
                        if (a[i + i1][j + j1] != '.') {
                            ok = false;
                        }
                    }
                }
                if (!ok) {
                    continue;
                }
                for (int i1 = 0; i1 < r; ++i1) {
                    for (int j1 = 0; j1 < c; ++j1) {
                        if (cutter[i1].charAt(j1) == '.') {
                            a[i + i1][j + j1] = 'X';
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a[i][j] == '.') {
                    return "NO";
                }
            }
        }
        return "YES";
    }
}

Div2 - 1000 GogoXReimuHakurai
Div1 - 500 GogoXMarisaKirisima
Despite the fact that these problems are different (second problem is more common) we can solve them using same approach.

public class GogoXMarisaKirisima {
    public int solve(String[] choices) {
        int n = choices.length;
        boolean a[][] = new boolean[n][n];
        for (int i = 0; i < n; ++i) {            
            for (int j = 0; j < n; ++j) {
                if (i == j) a[i][i] = true;
                else a[i][j] = choices[i].charAt(j) == 'Y';
            }
        }
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (a[i][k] && a[k][j]) {
                        a[i][j] = true;
                    }
                }
            }
        }
        if (!a[0][n - 1]) return 0;
        int V = 0, E = 0;
        boolean use[] = new boolean[n];
        for (int i = 0; i < n; ++i) {
            use[i] = a[0][i] && a[i][n - 1];
        }
        for (int i = 0; i < n; ++i) {
            if (!use[i]) continue;
            ++V;
            for (int j = 0; j < n; ++j) {
                if (!use[j]) continue;
                if (choices[i].charAt(j) == 'Y') {
                    ++E;
                }
            }
        }
        return  E - V +  2;
    }
}

Div1 - 1000 GogoXBallsAndBins

import java.util.*;

public class GogoXBallsAndBins {
    int need, N;
    int[] T;
    Map m[][];
    static final long MOD = 1000 * 1000 * 1000 + 9;
    int rec(int k, int wait, int cum) {
        if (k == N) {
            if (cum == need && wait == 0) return 1;
            return 0;
        }
        if (m[k][wait].containsKey((Integer)cum)) 
            return (Integer)m[k][wait].get(cum);
        long res = rec(k + 1, wait, cum);
        long w = wait;
        if (wait > 0) {
            res += rec(k + 1, wait, cum) * w * 2; 
            res += rec(k + 1, wait - 1, cum + 2 * T[k]) * w * w;
        }
        res += rec(k + 1, wait + 1, cum - 2 * T[k]);
        res %= MOD;
        m[k][wait].put(cum, (int)res);
        return (int)res;
    }

    public int solve(int[] T, int moves) {
        this.T = T;
        need = 2 * moves;
        N = T.length;
        m = new Map[N + 1][N + 1];
        for (int i = 0; i <= N; ++i) {
            for (int j = 0; j <= N; ++j) {
                m[i][j] = new HashMap();
            }
        }
        return rec(0, 0, 0);
     }
}