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

SRM 528

Div2 - 250 MinCostPalindrome

public class MinCostPalindrome {
    public int getMinimum(String s, int oCost, int xCost) {
        int n = s.length();
        char a[] = s.toCharArray();
        int res = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (a[i] != '?' && a[n - i - 1] != '?') {
                if (a[i] != a[n - i - 1]) {
                    return -1;
                }
            } else {
                if (a[i] == '?' && a[n - i - 1] == '?') {
                    res += Math.min(oCost, xCost) * 2;
                } else if (a[i] == 'o' || a[n - i - 1] == 'o') {
                    res += oCost;
                } else {
                    res += xCost;
                }
            }
        }
        return res;
    }
}

Div2 - 500, Div1 - 250 Cut

import java.util.Arrays;
public class Cut {
    public int getMaximum(int[] lens, int cuts) {
        Arrays.sort(lens);
        int res = 0;
        for (int len : lens) {
            if (len % 10 != 0) continue;
            int need = len / 10 - 1;
            if (cuts >= need) {
                res += need + 1;
                cuts -= need;
            } else {
                res += cuts;
                cuts = 0;
            }
        }
        for (int len : lens) {
            if (len % 10 == 0 || len < 10) continue;
            int need = len / 10;
            if (cuts >= need) {
                res += need;
                cuts -= need;
            } else {
                res += cuts;
                cuts = 0;
            }
        }
        return res;
    }
}

Div2 - 1000 Mosquitoes

Div1 - 500 SPartition

Div1 - 1000 ColorfulCookie

public class ColorfulCookie {
    int[] cookies;
    int n, P1, P2;
    static final int MAX = 1000;
    int dp[][] = new int[MAX + 1][51];

    int rec(int n1, int k) {
        if (k == cookies.length) {
            if (n1 == 0) return 0;
            return Integer.MIN_VALUE;
        }
        if (dp[n1][k] != -1) return dp[n1][k];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i <= n1 && P1 * i <= cookies[k]; ++i) {
            int left = cookies[k] - P1 * i;
            int j = Math.min(left / P2, n - i);
            int t = rec(n1 - i, k + 1);
            if (t == Integer.MIN_VALUE) continue;
            res = Math.max(res, t + j);
        }
        return dp[n1][k] = res;
    }

    boolean check(int n) {
        this.n = n;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= cookies.length; ++j) {
                dp[i][j] = -1;
            }
        }
        return rec(n, 0) >= n;
    }
    public int getMaximum(int[] cookies, int P1, int P2) {
        this.cookies = cookies;
        this.P1 = P1;
        this.P2 = P2;
        int sum = 0;
        for (int cur : cookies) {
            sum += cur;
        }
        int lo = 0, hi = sum / (P1 + P2) + 1;
        hi = 1001;
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        return lo * (P1 + P2);
    }
}

srm524

Problem set analysis

Div2 - 250 ShippingCubes

public class ShippingCubes {
 public int minimalCost(int N) {
  int r = Integer.MAX_VALUE;
  for (int i = 1; i <= N; ++i) {
   if (N % i != 0) continue;
   for (int j = 1; i * j <= N; ++j) {
    if (N % (i * j) != 0) continue;
    r = Math.min(r, i + j + N / i / j);
   }
  }
  return r;  
 }
}

Div2 - 500, Div1 - 250 Magic Diamond

public class MagicDiamonds {
 boolean isPrime(long n) {
  if (n < 2) 
   return false;
  for (long i = 2; i * i <= n; ++i) 
   if (n % i == 0) 
    return false;
  return true;
 }
 public long minimalTransfer(long n) {
  if (n == 3) return 3;
  if (!isPrime(n)) return 1;
  return 2;
 }
}

Div2 - 1000 MultiplesWithLimit

Let us build infinity tree in which from every node exist edges with weigth from set of available digits. Then every path from root to some node would build digit sequence, which matches some number X. Assign every node tree value X % N. Some nodes would be have same values. Let us start breath-first-search from every child root node and would be see nodes by asceding order edge weight. As soon as we visit node with value 0 stop search. Value X, which match this node is problem answer.

import java.util.*;
public class MultiplesWithLimit {
 String correct(String s) {
  int len = s.length();
  if (len < 9) return s;
  return s.substring(0, 3) + "..." + s.substring(len - 3) + "(" + len + " digits)";
 }
 public String minMultiples(int N, int[] fb) {
  Arrays.sort(fb);
  Queue<Integer> q = new LinkedList<Integer>();
  int d[] = new int[N + 1];
  int p[] = new int[N + 1];
  int pi[] = new int[N + 1];
  Arrays.fill(d, Integer.MAX_VALUE);
  Arrays.fill(p, -1);
  for (int i = 1; i < 10; ++i) {
   if (Arrays.binarySearch(fb, i) >= 0) continue;
   if (d[i % N] != Integer.MAX_VALUE) continue;
   q.add(i % N);
   d[i % N] = 1;
   pi[i % N] = i;
  }
  while (!q.isEmpty()) {
   int x = q.poll();
   if (x == 0) {
    String ans = "";
    for (; x != -1; x = p[x]) {
     ans = (char)('0' + pi[x]) + ans;
    }
    return correct(ans);
   }
   for (int i = 0; i < 10; ++i) {
    if (Arrays.binarySearch(fb, i) >= 0) continue;
    int nx = (x * 10 + i) % N;
    if (d[nx] == Integer.MAX_VALUE) {
     d[nx] = d[x] + 1;
     p[nx] = x;
     pi[nx] = i;
     q.add(nx);
    }
   }
  }
  return "IMPOSSIBLE";
 }
}

Div1 500 - LongestSequence
At first let's find out when we can build infinity sequence. Assume max is item from C array which has maximum absolute value. If we can build sequence from 2*max element, which satisfies given restrictions then obvious we can build sequence of length 3*max, 4*max an so on. So how we can check would we can build sequence of arbitrary length. Let us consider example C = {-2, 3}. Fix some sequence length and check it. For example fix length = 3. We want find out same array A of size 3 which satisfied given restriction. We can consider array of partials sums S, where S[i] = A[1] + A[2] + ... + A[i]. Its size equals size of array A. In this way sum A[i] + A[i + 1] + ... + A[j] equals S[j] - S[i - 1]. Thus we can take restrictions from array C and write out following equations:
S[2] - S[0] < 0
S[3] - S[1] < 0
S[3] - S[0] > 0
Transform these equations in such manner:
S[2] < S[0]
S[3] < S[1]
S[0] < S[3]
Consider graph which consists from 4 vertexes (from 0 to 3) and add edges which match these equations. Thus we add following edges: (2->0), (3->1), (0->3).
If we find out any cycle then we can't build sequence of length 3 because we become contradiction (if we consider length = 4, we are going to become a graph, which contains a cycle). Otherwise if we don't have a cycle then for prove that there is a suitable sequence of need length we can observe ideas from Cormen book (chapter "Difference contstraints and shortest pahts").
Now when we can check would we can build a sequence arbitrary length, we can with using binary search to find out problem answer.

import java.util.Arrays;

public class LongestSequence {
    int C[];
    boolean A[][] = new boolean[3000][3000];
    int Color[] = new int[3000];
    int N;

    void addEdge(int u, int v) {
        A[u][v] = true;
    }

    boolean dfs(int u) {
        Color[u] = 1;
        for (int v = 0; v <= N; ++v) {
            if (!A[u][v] || Color[v] == 2) continue;
            if (Color[v] == 1) return true;
            if (dfs(v)) return true;
        }
        Color[u] = 2;
        return false;
    }

    boolean check(int n) {
        N = n;
        Arrays.fill(Color, 0, n + 1, 0);
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(A[i], 0, n + 1, false);
        }
        for (int x : C) {
            if (Math.abs(x) > n) continue;
            for (int i = Math.abs(x); i <= n; ++i) {
                if (x < 0) addEdge(i + x, i);
                if (x > 0) addEdge(i, i - x);
            }
        }
        for (int i = 0; i <= n; ++i) {
            if (Color[i] == 0 && dfs(i)) {
                return false;
            }
        }
        return true;
    }

    public int maxLength(int C[]) {
        this.C = C;
        if (check(2000)) return -1;
        int lo = 0, hi = 2000;
        while (hi - lo > 1) {
            int mid = hi + lo >> 1;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        return lo;

    }
}

Div1 - 1000 AxonometricProjection

import java.util.Arrays;

public class AxonometricProjection {

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

    long P[] = new long[50 * 50 + 1];
    long P1[] = new long[50 * 50 + 1];
    int dp[][] = new int[100][100];
    int n2, m2, K;
    int C[][] = new int[51][51];
    {
        for (int i = 0; i < C.length; ++i) {
            C[i][0] = 1;
            for (int j = 1; j <= i; ++j) {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }
    }

    int rec(int n1, int m1) {
        if (n1 == 0 && m1 == 0) return 1;
        if (dp[n1][m1] != -1) return dp[n1][m1];
        long r = 0;
        for (int i = 0; i <= n1; ++i) {
            for (int j = 0; j <= m1; ++j) {
                if (i == n1 && j == m1) continue;
                long t1 = rec(i, j);
                long t2 = C[n1][i];
                long t3 = C[m1][j];
                int c1 = (n1 - i) * (m1 + m2) + (m1 - j) * (n1 + n2) - (n1 - i) * (m1 - j);
                long t4 = P[c1];
                r = (r + t1 * t2 % MOD * t3 % MOD * t4 % MOD) % MOD;
            }
        }
        int c = (n1 + n2) * (m1 + m2) - n2 * m2;
        r = (P1[c] - r) % MOD;
        if (r < 0) r += MOD;
        return dp[n1][m1] = (int)r;
    }

    public int howManyWays(int v[], int h[]) {
        Arrays.sort(v);
        Arrays.sort(h);
        if (v[v.length - 1] != h[h.length - 1]) return 0;
        long ans = 1;
        for (K = 1; K <= v[v.length - 1]; ++K) {
            int n1 = 0, n2 = 0;
            for (int cur : h) {
                if (cur == K) ++n1;
                if (cur > K) ++n2;
            }
            int m1 = 0, m2 = 0;
            for (int cur : v) {
                if (cur == K) ++m1;
                if (cur > K) ++m2;
            }
            if (m1 == 0 && n1 == 0) continue;
            P[0] = P1[0] = 1;
            int hi = (m1 + m2) * (n1 + n2);
            for (int i = 1; i <= hi; ++i) {
                P[i] = P[i - 1] * K % MOD;
                P1[i] = P1[i - 1] * (K + 1) % MOD;
            }
            this.n2 = n2;
            this.m2 = m2;
            for (int i = 0; i <= n1; ++i) {
                for (int j = 0; j <= m1; ++j) {
                    dp[i][j] = -1;
                }
            }
            ans = ans * rec(n1, m1) % MOD;
        }
        return (int)ans;
    }  
}