SRM 525

Div2 250 - RainyRoad
The problem has very short solution. Also it is possible solve it using more familiar approach (using dfs or bfs).

public class RainyRoad {
    public String isReachable(String[] road) {
        for (int i = 0; i < road[0].length(); ++i) {
            if (road[0].charAt(i) == 'W' && road[1].charAt(i) == 'W')
                return "NO";
        }
        return "YES";
    }
}

Div2 950 - MagicalSquare

I wrote solution with very big complexity O(N ^ 6). But it passed all tests.

public class MagicalSquare {
    String R[], C[];
    String A[][] = new String[3][3];
    Long dp[][][][] = new Long[3][51][51][51];

    long rec(int l, int i1, int i2, int i3) {
        if (l == 3) {
            if (i1 == C[0].length() && i2 == C[1].length() && i3 == C[2].length()) return 1;
            return 0;
        }
        if (dp[l][i1][i2][i3] != null) return dp[l][i1][i2][i3];
        String s1 = C[0].substring(i1);
        String s2 = C[1].substring(i2);
        String s3 = C[2].substring(i3);
        String cur = R[l];
        int len = cur.length();
        long res = 0;
        for (int i = 0; i <= len; ++i) {
            String t3 = cur.substring(i);
            if (!s3.startsWith(t3)) continue;
            for (int j = 0; j <= i; ++j) {
                String t1 = cur.substring(0, j);
                String t2 = cur.substring(j, i);
                if (!s2.startsWith(t2)) continue;
                if (!s1.startsWith(t1)) continue;
                res += rec(l + 1, i1 + t1.length(), i2 + t2.length(), i3 + t3.length());
            }
        }
        return dp[l][i1][i2][i3] = res;
    }

    public long getCount(String[] rowStrings, String[] columnStrings) {
        this.R = rowStrings;
        this.C = columnStrings;
        return rec(0, 0, 0, 0);
    }
}

Div1 300, Div2 600 - DropCoins

I wrote simple brute force solution with O(N^6) complexity which surprisingly do not became time limit. Of course there is more faster solution which uses inclusion–exclusion principle. It has O(N^4) complexity.

public class DropCoins {
    public int getMinimum(String[] board, int K) {
        int res = Integer.MAX_VALUE;
        int n = board.length;
        int m = board[0].length();
        for (int i1 = 0; i1 < n; ++i1)
        for (int i2 = i1; i2 < n; ++i2)
        for (int j1 = 0; j1 < m; ++j1)
        for (int j2 = j1; j2 < m; ++j2) {
            int cnt = 0;
            for (int i = i1; i <= i2; ++i)
                for (int j = j1; j <= j2; ++j)
                    if (board[i].charAt(j) != '.')
                        ++cnt;
            if (cnt != K) continue;
            int t1 = i1;
            int t2 = n - 1 - i2;
            int t = Math.min(2 * t1 + t2, 2 * t2 + t1);
            t1 = j1;
            t2 = m - 1 - j2;
            t += Math.min(2 * t1 + t2, 2 * t2 + t1);
            res = Math.min(res, t);
        }
        if (res == Integer.MAX_VALUE) return -1;
        return res;
    }
}

Div1 525 - Rumor

import java.io.*;
import java.util.*;

public class Rumor {

    int n, know, g[], mask;
    int res = Integer.MAX_VALUE;

    int check(int use) {
        int knowA = know, knowB = know;
        int giveA = 0, giveB = 0;
        int cnt = 0;
        while (knowA != mask || knowB != mask) {
            if (++cnt >= res) return -1;
            int newKnowA = 0, newKnowB = 0;
            for (int i = 0; i < n; ++i) {
                if (testBit(giveA, i) && testBit(giveB, i)) continue;
                if (!testBit(knowA, i) && !testBit(knowB, i)) continue;

                String s = "";
                if (!testBit(giveA, i) && testBit(knowA, i)) s += 'a';
                if (!testBit(giveB, i) && testBit(knowB, i)) s += 'b';
                if (s.length() == 0) continue;

                char ch;
                if (s.length() == 2) {
                    if (testBit(use, i)) ch = s.charAt(0);
                    else ch = s.charAt(1);
                } else ch = s.charAt(0);

                if (ch == 'a') {
                    newKnowA |= g[i];
                    giveA |= 1 << i;
                } else {
                    newKnowB |= g[i];
                    giveB |= 1 << i;
                }
            }
            if ((knowA | newKnowA) == knowA && (knowB | newKnowB) == knowB) return -1;
            knowA |= newKnowA;
            knowB |= newKnowB;
        }
        return cnt;
    }

    private boolean testBit(int use, int i) {
        return ((use >> i) & 1) == 1;
    }

    public int getMinimum(String knowledge, String[] graph) {
        n = knowledge.length();
        mask = (1 << n) - 1;
        g = new int[n];
        for (int i = 0; i < n; ++i) {
            if (knowledge.charAt(i) == 'Y') {
                know |= 1 << i;
            }
            for (int j = 0; j < n; ++j) {
                if (graph[i].charAt(j) == 'Y')
                    g[i] |= 1 << j;
            }
        }
        for (int use = 0; use < (1 << n); ++use) {
            int t = check(use);
            if (t == -1) continue;
            res = Math.min(res, t);
        }
        if (res == Integer.MAX_VALUE) return -1;
        return res;
    }
}

Div1 950 - MonochromePuzzle

public class MonochromePuzzle {
    public int getMinimum(String a[]) {
        int n = a.length;
        for (int i = 0; i < n; ++i) {
            int c = 0;
            for (int j = 0; j < n; ++j) {
                if (a[i].charAt(j) != a[j].charAt(i)) return -1;
                if (a[i].charAt(j) == '#') ++c;
            }
            if (c != 3) return -1;
        }
        int p[] = null;
        for (int i = 1; i < n; ++i) {
            p = check(a, 0, i);
            if (p != null) break;
        }
        if (p == null) return -1;


        int res = Integer.MAX_VALUE;

        for (int tt = 0; tt < 3; ++tt) {            
            for (int i = 0; i < n / 2; ++i) {
                int x = get(p);
                res = Math.min(x, res);
                rshift(p, 0, n / 2);
                lshift(p, n / 2, n);
            }
            reverse(p, 0, n);            

            for (int i = 0; i < n / 2; ++i) {
                int x = get(p);
                res = Math.min(x, res);
                rshift(p, 0, n / 2);
                lshift(p, n / 2, n);
            }

            reverse(p, 0, n / 2);
            reverse(p, n / 2, n);

            for (int i = 0; i < n / 2; ++i) {
                int x = get(p);
                res = Math.min(x, res);
                rshift(p, 0, n / 2);
                lshift(p, n / 2, n);
            }

            reverse(p, 0, n);
            for (int i = 0; i < n / 2; ++i) {
                int x = get(p);
                res = Math.min(x, res);
                rshift(p, 0, n / 2);
                lshift(p, n / 2, n);
            }


            if (n != 8) break;
            int np[] = new int[8];
            np[0] = p[0];
            np[1] = p[3];
            np[2] = p[4];
            np[3] = p[7];
            np[4] = p[6];
            np[6] = p[2];
            np[7] = p[1];
            np[5] = p[5];
            for (int i = 0; i < 8; ++i) p[i] = np[i];


        }
        return res;
    }

    private void reverse(int p[], int lo, int hi) {
        int n = (hi - lo) / 2;
        for (int i = 0; i < n; ++i) {
            int tmp = p[lo + i];
            p[lo + i] = p[hi - i - 1];
            p[hi - i - 1] = tmp;
        }
    }

    private void lshift(int p[], int lo, int hi) {
        int tmp = p[lo];
        for (int i = lo; i + 1 < hi; ++i) {
            p[i] = p[i + 1];
        }
        p[hi - 1] = tmp;
    }

    private void rshift(int p[], int lo, int hi) {
        int tmp = p[hi - 1];
        for (int i = hi - 1; i > 0; --i) {
            p[i] = p[i - 1];
        }
        p[0] = tmp;
    }

    private int get(int p[]) {
        int n = p.length;
        boolean use[] = new boolean[n];
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (use[i]) continue;
            int cur = i;
            int c = 0;
            while (!use[cur]) {
                use[cur] = true;
                ++c;
                cur = p[cur];
            }
            if (c >= 2) res += c - 1;
        }
        return res;
    }

    private int[] check(String a[], int u, int v) {
        if (a[u].charAt(v) != '#') return null;
        int n = a.length;
        int p[] = new int[n];
        int left = 0, right = n - 1;
        p[left++] = u;
        p[right--] = v;
        boolean use[] = new boolean[n];
        use[u] = use[v] = true;
        int pu = u, pv = v;
        for (int k = 1; k < n / 2; ++k) {
            boolean ok = false;
            for (int i = 1; !ok && i < n; ++i) {
                if (use[i]) continue;
                for (int j = 1; !ok && j < n; ++j) {
                    if (use[j] || i == j) continue;
                    if (a[i].charAt(j) != '#') continue;
                    if (a[i].charAt(pu) != '#') continue;
                    if (a[j].charAt(pv) != '#') continue;
                    if (k == n / 2 - 1) {
                        if (a[i].charAt(u) != '#') continue;
                        if (a[j].charAt(v) != '#') continue;
                    }
                    ok = true;
                    p[left++] = i;
                    p[right--] = j;
                    use[i] = use[j] = true;
                    pu = i;
                    pv = j;
                }
            }
            if (!ok) return null;
        }
        return p;
    }
}

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

srm523

Writer's explanation
Official explanation

Div2 250 - AlphabetPath
This problem has simple backtracking solution:

import java.io.*;
import java.util.*;
public class AlphabetPath {
 int n, m;
 String s[];
 boolean rec(int k, int i, int j) {
  if (k == 26) return true;
  if (i < 0 || j < 0 || i >= n || j >= m) return false;
  if (s[i].charAt(j) != 'A' + k) return false;
  return rec(k + 1, i + 1, j) || 
  rec(k + 1, i - 1, j) || 
  rec(k + 1, i, j - 1) || 
  rec(k + 1, i, j + 1);
 }
 public String doesItExist(String[] s) {
        n = s.length;
  m = s[0].length();
  this.s = s;
  for (int i = 0; i < n; ++i) {
   for (int j = 0; j < m; ++j) {
    if (rec(0, i, j)) return "YES";
   }
  }
  return "NO";
 }

Beside it there is another solution which use bfs.

Div2 1000 - SmallBricks31
Standard dynamic programming problem.

import java.io.*;
import java.util.*;
public class SmallBricks31 {
    int C[][];
    int w, h;
    int MOD = 1000000007;

    public int countWays(int w, int h) {
        this.w = w;
        this.h = h;
        C = new int[1 << w][1 << w];
        for (int use = 0; use < (1 << w); ++use) {
            rec(use, 0, 0);
        }
        int ans = 0;
        dp = new Integer[h + 1][1 << w];

        for (int i = h; i >= 0; --i) {
            ans += rec(i, (1 << w) - 1);
            ans %= MOD;
        }

        return ans;
    }
    Integer dp[][];

    private int rec(int k, int use) {
        if (k == 0) return 1;
        if (dp[k][use] != null) return dp[k][use];
        long r = 0;
        for (int nuse = 1; nuse < 1 << w; ++nuse) {
            r += (long)rec(k - 1, nuse) * C[use][nuse];
            r %= MOD;
        }
        return dp[k][use] = (int)r;
    }

    private void rec(int puse, int use, int p) {
        if (p == w) {
            C[puse][use]++;
            return;
        }
        rec(puse, use, p + 1);
        for (int i = 1; i <= 3; ++i) {
            if (p + i > w) break;
            if (!testBit(puse, p) || !testBit(puse, p + i - 1)) continue;
            int nuse = use;
            for (int j = 0; j < i; ++j) {
                nuse |= (1 << p + j);
            }
            rec(puse, nuse, p + i);
        }
    }

    private boolean testBit(int use, int p) {
        return ((use >> p) & 1) == 1;
    }
}

Div1 900 - AlphabetPaths
Let us fix current non-empty cell in the maze and find all possible paths which length is 11 and which consist of from different letters. Let us imagine one path as a bitmask and count all possible bitmasks in array. As soon as we finish all-possible-paths search from fixed cell we can count all 21-length paths, which have middle in these fix cell. To do so we might iterate over all the indexes of array and sum products of value by current index and value by complement index. Consider some optimizations. What is the size of bitmask array? We can omit letter in the current fixed cell and number rest letters using indexes from 0 to 19. So we need an array of size 2^20. And when we fill it we must iterate over all array elements. But it is very slow. Problem solution consists in counting the suitable values as soon as new path is generated. When we have a path, which match to some bitmask use, and we know value = C[use] * C[mask ^ use], where C - our counting bitmask array and mask = (1 << 20) - 1, then the new value can be calculated as follows:
newvalue = (C[use] + 1) * C[mask ^ use] = C[use] * C[mask ^ use] + C[mask ^ use] = value + C[mask ^ use].
So, newvalue = value + C[mask ^ use].
But we have yet another problem. In each step we must reset array C. But it is very slow too. To speed it up let us introduce a new Mark array, which size is equal to size of array C. And for each starting cell let introduce a current mark, which is different for different starting cells. And always Mark[use] == currentMark, if and only if some path was at current step, which match bitmask use. When we need to know C[use], we must see Mark[use] value. If Mark[use] == currentMark, then it is suitable value, otherwise we did not find the path at current step, which match bitmask use, and actual value of C[use] equals zero. All these ideas follow to the next code:

import java.util.Arrays;

public class AlphabetPaths {
    int n, m, a[][];
    int di[] = new int[] { -1, 0, 1, 0 };
    int dj[] = new int[] { 0, -1, 0, 1 };
    int C[] = new int[(1 << 20) + 10];
    int Mark[] = new int[(1 << 20) + 10];
    int cur, cnt, mask = (1 << 20) - 1;
    long ans;

    void check(int use) {
        if (Mark[use] != cnt) {
            Mark[use] = cnt;
            C[use] = 0;
        }
    }

    void rec(int p, int i, int j, int use) {
        if (p == 11) {
            check(use);
            check(use ^ mask);
            C[use]++;
            ans += C[use ^ mask];
            return;
        }
        for (int k = 0; k < 4; ++k) {
            int ni = i + di[k];
            int nj = j + dj[k];
            if (ni < 0 || nj < 0 || ni >= n || nj >= m)
                continue;
            int t = a[ni][nj];
            if (t == 21 || t == cur)
                continue;
            if (t > cur)
                --t;
            if (((use >> t) & 1) == 1)
                continue;
            rec(p + 1, ni, nj, use | (1 << t));
        }
    }

    public long count(String maze[]) {
        String letters = "ABCDEFZHIKLMNOPQRSTVX.";
        n = maze.length;
        m = maze[0].length();
        a = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                a[i][j] = letters.indexOf(maze[i].charAt(j));
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a[i][j] == 21)
                    continue;
                cur = a[i][j];
                ++cnt;
                rec(1, i, j, 0);
            }
        }
        return ans * 2;
    }
}

While I was solving this problem using C++ I occurred very strange thing. My solution got time limit, and then I changed row:
int C[1 << 20];
by row:
int C[(1 << 20) + 10];
and my solution passed all tests.
I hope in future I will find out reasons of these strange behavior.