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);
     }
}

One sum computation

Solving one problem I encountered one problem. I needed calculate one interesting sum: sigma(N / i), where (1 <= i && <= K). How we can do it as fast as possible. We can do it using complexity sqrt(N) moving from two ends. Following code demonstate this approach.

    long smart(long N, long K) {
        long res = 0;
        long t = (long)Math.sqrt(N * 1.0);
        for (long i = 1; i * i < N; ++i) {
            if (i <= K) res += N / i;
            long lo = Math.max(N / (i + 1), t);
            long hi = Math.min(N / i, K);
            if (hi > lo) res += (hi - lo) * i;
        }
        if (t * t == N && t <= K) res += t;
        return res;
    }

After it I recall one neerc problem. But there we need compute a little different sum: sigma(N % i), where (1 <= i && <= K). So we can replace N % i to (N - N / i * i) and addopt previous code to calculate sigma(N / i * i).

SRM 529

Div2 - 250 PairingPawns

public class PairingPawns {
    public int savedPawnCount(int[] start) {
        int n = start.length;
        for (int i = n - 1; i > 0; --i) {
            start[i - 1] += start[i] / 2;
        }
        return start[0];
     }
}

Div2 - 500, Div1 - 250 KingSort

import java.util.*;

public class KingSort implements Comparator<String> {
    Map<String, Integer> map = new HashMap<String, Integer>();

    public String[] getSortedList(String[] kings) {
        String s1[] = ",I,II,III,IV,V,VI,VII,VIII,IX,X".split(",");
        String s2[] = ",X,XX,XXX,XL,L".split(",");
        for (int i = 1; i <= 50; ++i) {
            map.put(s2[i / 10] + s1[i % 10], i);
        }
        Arrays.sort(kings, this);
        return kings;
    }
    public int compare(String s1, String s2) {
        String t1[] = s1.split(" ");
        String t2[] = s2.split(" ");
        if (!t1[0].equals(t2[0])) return t1[0].compareTo(t2[0]);
        return map.get(t1[1]).compareTo(map.get(t2[1]));
    }
}

Div2 - 1000 MinskyMysteryDiv2

public class MinskyMysteryDiv2 {
    long get(long N) {
        if (N < 2) return -1;
        long i = 2;
        while (i * i <= N && N % i != 0) ++i;
        if (i * i > N) i = N;
        return N / i + i;
    }
    public long computeAnswer(long N) {
        return get(N);
        
     }
}

Div1 - 600 MinskyMystery

import java.util.*;

public class MinskyMystery {

    final int MOD = 1000 * 1000 * 1000 + 9;

    long add(long r, long x) {
        x %= MOD;
        if (x < 0) x += MOD;
        return (r + x) % MOD;
    }

    // get sum N/i (i == 1..N)
    long clever(long N) {
        long res = 0;
        long t = (long)Math.sqrt(1.0 * N);
        long i;
        for (i = 1; i * i < N; ++i) {
            res += N / i;
            if (N / i > t) res += (N / i - N / (i + 1)) * i;
        }
        if (i * i == N) res += i;
        return res;
    }

    public int computeAnswer(long N) {
        if (N < 2) return -1;
        long r = 1;
        long j = 2;
        while (j * j <= N && N % j != 0) ++j;
        if (j * j > N) j = N;

        r = add(r, 2 * j - 3);
        r = add(r, (j - 1) % MOD * (N % MOD) % MOD * 3); 
        r = add(r, (j - 2) % MOD * (N % MOD) % MOD); 

        if (j == N) {
            r = add(r, clever(N) - N);
        } else {
            for (long i = 2; true; ++i) {
                r = add(r, N / i);
                if (N % i == 0) break; 
            }
        }
        return (int)r;
    }
}

Div1 - 900 BigAndSmallAirports