SRM 534

Div2 - 250 EllysDirectoryListing

public class EllysDirectoryListing {
    public String[] getFiles(String[] files) {
        int n = files.length;
        if (check(files)) return files;
        int p = getPos(files);
        swap(files, p, n - 1);
        if (check(files)) return files;
        p = getPos(files);
        swap(files, p, n - 2);
        return files;
     }

    boolean check(String files[]) {
        int n = files.length;
        if (files[n - 1].equals(".") && files[n - 2].equals("..")) return true;
        if (files[n - 2].equals(".") && files[n - 1].equals("..")) return true;
        return false;
    }
    int getPos(String files[]) {
        for (int i = 0; i < files.length; ++i) {
            if (files[i].equals(".")) return i;
            if (files[i].equals("..")) return i;
        }
        return -1;
    }
    void swap(String f[], int i, int j) {
        String tmp = f[i];
        f[i] = f[j];
        f[j] = tmp;
    }

}

Div2 - 500, Div1 - 250 EllysCheckers

public class EllysCheckers {
    public String getWinner(String board) {        
        int use = 0;
        N = board.length();
        for (int i = 0; i + 1 < N; ++i) {
            if (board.charAt(i) != '.') {
                use |= 1 << i;
            }
        }
        dp = new Integer[1 << N];
        return rec(use) == 1 ? "YES" : "NO";
     }
    
    Integer dp[];
    int N;

    int rec(int use) {
        if (testBit(use, N - 1)) use ^= 1 << N - 1;
        if (dp[use] != null) return dp[use];
        for (int i = 0; i < N; ++i) {
            if (i + 1 < N && testBit(use, i) && !testBit(use, i + 1)) {
                int nuse = use ^ (1 << i) ^ (1 << i + 1);
                if (rec(nuse) == 0) return dp[use] = 1;
            }
            if (i + 3 < N && testBit(use, i) && testBit(use, i + 1)
            && testBit(use, i + 2) && !testBit(use, i + 3)) {
                int nuse = use ^ (1 << i) ^ (1 << i + 3);
                if (rec(nuse) == 0) return dp[use] = 1;
            }
        }
        return dp[use] = 0;
    }

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

Div2 - 1000 EllysFiveFriends

public class EllysFiveFriends {

    static final long MOD = 1000 * 1000 * 1000 + 7;

    boolean check(int a[]) {
        for (int i = 0; i < 5; ++i) {
            if (a[i] > 0) return false;
        }
        return true;
    }

    long getHash(int a[]) {
        long r = 0;
        for (int i = 0; i < 5; ++i) {
            r = r * 10007 + a[i];
        }
        return r;
    }

    static final int MAX = 1 << 22;
    static final int MASK = MAX - 1;
    static final int MAXH = 1 << 21;
    int NH;
    long Hkey[];
    int Hval[];
    int Hnext[];
    int h[];

    int get(long key) {
        int pos = (int)(key&MASK);
        for (int cur = h[pos]; cur != 0; cur = Hnext[cur]) {
            if (Hkey[cur] == key)  return Hval[cur];
        }
        return -1;
    }
    int rec(int a[]) {
        if (check(a)) return 1;
        long key = getHash(a);
        int t = get(key);
        if (t != -1) return t;
        int pos = (int)(key&MASK);
        long res = 0;
        for (int i = 0; i < 5; ++i) {
            int j = i + 1;
            if (j == 5) j = 0;
            if (a[i] <= 0 || a[j] <= 0) continue;
            int x = a[i], y = a[j];
            a[i] >>= 1;
            a[j] >>= 1;
            res += rec(a);
            a[i] = x;
            a[j] = y;
            if ((a[i] & 1) == 1 && (a[j] & 1) == 1) {
                --a[i];
                --a[j];
                res += rec(a);
                ++a[i];
                ++a[j];
            }
        }
        int r = (int)(res % MOD);
        Hkey[NH] = key;
        Hval[NH] = r;
        Hnext[NH] = h[pos];
        h[pos] = NH++;
        return r;
    }
    

    public int getZero(int[] numbers) {        
        h = new int[MAX];
        Hkey = new long[MAXH];
        Hval = new int[MAXH];
        Hnext = new int[MAXH];
        NH = 1;
        return rec(numbers);
     }
}

Div1 - 500 EllysNumbers

import java.util.*;

public class EllysNumbers {
    List<Integer> uses;
    int N;

    int[] collect(String[] s) {
        String str = "";
        for (String cur : s) {
            str += cur;
        }
        String ss[] = str.split(" ");
        int r[] = new int[ss.length];
        for (int i = 0; i < ss.length; ++i) {
            r[i] = Integer.valueOf(ss[i]);
        }
        return r;
    }

    public long getSubsets(long n, String[] special) {        
        Set<Integer> divisors = new TreeSet<Integer>();
        int vals[] = collect(special);
        for (int val : vals) {
            add(divisors, val);
        }
        List<Integer> d1 = new ArrayList<Integer>();
        List<Integer> d2 = new ArrayList<Integer>();
        long x = n;
        for (Integer divisor : divisors) {
            int c = 0;
            while (x % divisor == 0) {
                ++c;
                x /= divisor;
            }
            if (c == 0) continue;
            d1.add(divisor);
            d2.add(c);
        }

        if (x > 1) return 0;
        N = d1.size();
        uses = new ArrayList<Integer>();
        for (int val : vals) {
            int cur = val;
            boolean ok = true;
            int use = 0;
            for (int i = 0; ok && i < d1.size(); ++i) {
                int c = 0;
                while (cur % d1.get(i) == 0) {
                    cur /= d1.get(i);
                    ++c;
                }
                if (c == 0) continue;
                if (c == d2.get(i)) {
                    use |= 1 << i;
                    continue;
                }
                ok = false;
            }
            if (cur != 1 || !ok) continue;
            uses.add(use);
        }
        return calc();
     }
    
    long calc() {
        long dp[][] = new long[2][1 << N];
        int prev = 0, next = 1;
        dp[prev][(1 << N) - 1] = 1;
        for (int k = uses.size() - 1; k >= 0; --k) {
            int nuse = uses.get(k);
            for (int use = 0; use < 1 << N; ++use) {
                dp[next][use] = dp[prev][use];
                if ((use + nuse) == (use ^ nuse))
                    dp[next][use] += dp[prev][use ^ nuse];
            }
            int tmp = prev;
            prev = next;
            next = tmp;
        }
        return dp[prev][0];
    }

    void add(Set<Integer> d, int val) {
        for (int i = 2; i * i <= val; ++i) {
            int c = 0;
            while (val % i == 0) {
                val /= i;
                ++c;
            }
            if (c > 0) d.add(i);
        }
        if (val != 1) d.add(val);
    }
}

Div1 - 1000 #

SRM 527

Div 2 250 - P8XMatrixTransformation
It is obvious that we can transform source matrix to destination matrix if and only if number of ones in the first matrix equals number of ones in the second matrix (We always can swap any two elements of source matrix using given operation).

public class P8XMatrixTransformation {
    public String solve(String[] original, String[] target) {
        int n = original.length;
        int m = original[0].length();
        int c = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (original[i].charAt(j) == '1') ++c;
                if (target[i].charAt(j) == '1') --c;
            }
        }
        if (c == 0) return "YES";
        return "NO";
    }
}

Div2 550, Div1 275 - P8XGraphBuilder
As we can see from statement we have to build tree. Any tree has (N - 1) edges where N - number of vertexes. Since each edge (u, v) increase by one degree of u and v then sum of all vertexes degree in tree equals 2(E - 1) and each degree is not greater than N - 1 and not less than 1. If we become any array of degree (call it d) which satisfied previous restrictions we can always build tree using this array.  How we can do it? Sort array in non decreasing order and then let pick up first vertex (its degree is one) and connect it with first not one degree vertex with decreasing them degrees. Note that array keep non decreasing order. Repeat this operation until array would be as (1, 1) and add last edge. We become tree because in process we can't build cycle since we always added edges from left to right by array. And last action consists in finding optimal solution. We can do it using dynamic programming (like knapsack algorithm).

import java.util.Arrays;
public class P8XGraphBuilder {
    public int solve(int[] scores) {
        int N = scores.length + 1;
        int W = 2 * (N - 1);
        int dp[][] = new int[N + 1][W + 1];
        for (int i = 0; i <= N; ++i) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j < N; ++j) {
                int c = scores[j - 1];
                for (int k = j; k <= W; ++k) {
                    dp[i][k] = Math.max(dp[i][k], dp[i - 1][k - j] + c); 
                }
            }
        }
        return dp[N][W];
    }
}

Div1 1050 - P8XCoinChange

public class P8XCoinChange {
    static final int MOD = 1000 * 1000 + 3;

    int[][] mul(int[][] a, int[][] b) {
        int n = a.length;
        int c[][] = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                long cum = 0;
                for (int k = 0; k < n; ++k) {
                    cum += (long)a[i][k] * b[k][j];
                }
                c[i][j] = (int)(cum % MOD);
            }
        }
        return c;
    }
    int[][] pow(int a[][], long n) {
        int r[][] = new int[a.length][a.length];
        for (int i = 0; i < a.length; ++i) {
            r[i][i] = 1;
        }
        for (; n != 0; n >>= 1) {
            if ((n & 1) == 1) {
                r = mul(r, a);
            }
            a = mul(a, a);
        }
        return r;
    }
    public int solve(long sum, long[] vals) {
        int n = vals.length;
        int a[][][] = new int[n][n][n];
        for (int i = 0; i < n; ++i) {
            a[0][i][0] = 1;
        }
        for (int i = 1; i < n; ++i) {
            a[i] = pow(a[i - 1], vals[i] / vals[i - 1]);
            for (int k = i; k < n; ++k) {
                a[i][k][i]++;
            }
        }
        int r[][] = new int[n][n];
        for (int i = 0; i < n; ++i) {
            r[i][i] = 1;
        }
        for (int i = n - 1; i >= 0; --i) {
            long val = vals[i]; 
            long pw = sum / val;
            sum %= val;
            r = mul(r, pow(a[i], pw));
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += r[n - 1][i];
            ans %= MOD;
        }
        return ans;
     }
}

SRM 526

Div2 250 - CheatingQuiz

import java.util.TreeSet;
import java.util.Set;
public class CheatingQuiz {
    public int[] howMany(String answers) {
        int r[] = new int[answers.length()];
        for (int i = 0; i < answers.length(); ++i) {
            Set<Character> set = new TreeSet<Character>();
            for (int j = i; j < answers.length(); ++j) {
                set.add(answers.charAt(j));
            }
            r[i] = set.size();
        }
        return r;
    }
}

Div2 500, Div1 250 - DucksAlignment

int Abs(int x) {
 return x > 0 ? x : -x;
}
int dist(int i1, int j1, int i2, int j2) {
 return Abs(i1 - i2) + Abs(j1 - j2);
}
class DucksAlignment {
public:
 int minimumTime( vector <string> a) {
  int n = sz(a);
  int m = sz(a[0]);
  int c = 0;
  vector<pii> ij, ji;
  for (int i = 0; i < n; ++i)
   for (int j = 0; j < m; ++j) {
    if (a[i][j] != '.') {
     ++c;
     ij.pb(mp(i, j));
     ji.pb(mp(j, i));
    }
   }
  sort(all(ij));
  sort(all(ji));
  int res = 1 << 30;
  // horizontal
  for (int i = 0; i < n; ++i) {
   for (int j = 0; j + c - 1 < m; ++j) {
    int cur = 0;
    for (int k = 0; k < c; ++k) {
     cur += dist(ji[k].second, ji[k].first, i, j + k);
    }
    res = min(res, cur);
   }
  }
  // vertical
  for (int j = 0; j < m; ++j) {
   for (int i = 0; i + c - 1 < n; ++i) {
    int cur = 0;
    for (int k = 0; k < c; ++k) {
     cur += dist(ij[k].first, ij[k].second, i + k, j);
    }
    res = min(res, cur);
   }
  }
  return res;
 }
};

Div2 1000 - SumOfLuckiness

public class SumOfLuckiness {
    int d[];
    Integer dp[][][];
    int rec(int k, int dif, int was) {
        if (k == d.length) return Math.abs(dif);
        if (dp[k][dif + 200][was] != null) 
            return dp[k][dif + 200][was];
        int hi = was == 1 ? 9 : d[k];
        int res = 0;
        
        for (int i = 0; i <= hi; ++i) {
            int nwas = was;
            int ndif = dif;
            if (i == 4) ++ndif;
            if (i == 7) --ndif;
            if (i < d[k]) nwas = 1;
            res += rec(k + 1, ndif, nwas);
        }
        return dp[k][dif + 200][was] = res;    
    }

    int get(int x) {
        if (x == 0) return 0;
        String s = String.valueOf(x);
        d = new int[s.length()];
        for (int i = 0; i < s.length(); ++i) {
            d[i] = s.charAt(i) - '0';
        }
        dp = new Integer[d.length + 1][400][2];
        return rec(0, 0, 0);
    }
    
    public long theSum(int A, int B) {
        return get(B) - get(A - 1);
    }
}

Div1 500 - PrimeCompositeGame

const int MAX = 500000;
bool P[MAX + 10];
using namespace std;
int K;
const int INF = 1 << 30;
pii A[MAX + 1];

struct Minimizator {
    vi q;
    int n;
    Minimizator(int n) {        
        while (n & (n - 1)) ++n;
        q.assign(n * 2, INF);
        this->n = n;
    }
    void mod(int p, int val) {        
        for (p += n; p; p >>= 1) {
            q[p] = min(q[p], val);
        }        
    }
    int getMin(int lo, int hi) {
        int r = INF;
        for (lo += n, hi += n; lo <= hi; ++lo >>= 1, --hi >>= 1) {
            if ((lo & 1) == 1) r = min(r, q[lo]);
            if ((hi & 1) == 0) r = min(r, q[hi]);
        }
        return r;
    }
};

struct Maximizator {
    vi q;
    int n;
    Maximizator(int n) {        
        while (n & (n - 1)) ++n;
        q.assign(n * 2, -INF);
        this->n = n;
    }
    void modMax(int p, int val) {        
        for (p += n; p; p >>= 1) {
            q[p] = max(q[p], val);
        }        
    }
    int getMax(int lo, int hi) {
        int r = -INF;
        for (lo += n, hi += n; lo <= hi; ++lo >>= 1, --hi >>= 1) {
            if ((lo & 1) == 1) r = max(r, q[lo]);
            if ((hi & 1) == 0) r = max(r, q[hi]);
        }
        return r;
    }
};

void init(int hi) {
    Minimizator mnp(hi + 1), mnc(hi + 1);
    Maximizator mxp(hi + 1), mxc(hi + 1);
    for (int n = 2; n <= hi; ++n) {
        int hi = min(K, n - 2);
        int c_win = P[n] ? mnc.getMin(n - hi, n - 1) : mnp.getMin(n - hi, n - 1);
        int c_lose = P[n] ? mxc.getMax(n - hi, n - 1) : mxp.getMax(n - hi, n - 1);                
        if (c_win != INF) A[n] = mp(1, c_win + 1);
        else if (c_lose != -INF) A[n] = mp(-1, c_lose + 1);  
        else A[n] = mp(-1, 0);        
        if (P[n]) {
            if (A[n].first == -1) mnp.mod(n, A[n].second);
            else mxp.modMax(n, A[n].second);
        } else {
            if (A[n].first == -1) mnc.mod(n, A[n].second);
            else mxc.modMax(n, A[n].second);
        }        
    }
}

class PrimeCompositeGame {
public:
    int theOutcome( int N, int k ) {
        K = k;
        for (int i = 0; i <= N; ++i) P[i] = false; 
        for (int i = 2; i * i <= N; ++i) {
            if (P[i]) continue;
            for (int j = i * i; j <= N; j += i) {
                P[j] = true;
            }
        }
        for (int i = 2; i <= N; ++i) {
            P[i] = !P[i];
        }
        init(N);
        int c_win = INF;
        int c_lose = 0;
        for (int i = 1; i <= K && i <= N - 2; ++i) {
            if (!P[N - i]) continue;
            pii t = A[N - i];
            if (t.first == 1) c_lose = max(c_lose, t.second + 1);        
            if (t.first == -1) c_win = min(c_win, t.second + 1);                
        }
        if (c_win != INF) return c_win;
        return -c_lose;
    }
};

Div1 1000 - DengklekMessage

#include <string>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;
#define mp make_pair
#define sz(x) ((int)((x).size()))
typedef vector<string> vs;
typedef vector<int> vi;
typedef pair<int, int> pii;

using namespace std;
vs P;
string G;
bool Mark[1000][1000];
double dp[1000][1000];
pii C[1000][1000];

vi calcP(string &s) {
    int n = sz(s);
    vi p(n, 0);
    int q = 0;
    for (int i = 1; i < n; ++i) {
        while (q && s[i] != s[q]) q = p[q - 1];
        if (s[i] == s[q]) ++q;
        p[i] = q;
    }
    return p;
}

pii calc(int len, int k) {
    string str = G + "#" + G.substr(0, len) + P[k];
    vi p = calcP(str);
    int x = 0;
    for (int i = 0; i < sz(p); ++i) {
        if (p[i] == sz(G)) {
            ++x;
        }
    }
    int nlen = p.back();
    if (len == sz(G)) --x;
    return mp(x, nlen);    
}


void initC() {
    for (int len = 0; len <= sz(G); ++len) {
        for (int k = 0; k < sz(P); ++k) {
            C[len][k] = calc(len, k);
        }
    }
}

double rec(int k, int len) {
    if (k == 0) return 0;
    if (Mark[k][len]) return dp[k][len];
    Mark[k][len] = true;
    double res = 0.0;
    for (int i = 0; i < sz(P); ++i) {
        int nlen = C[len][i].second;
        int x = C[len][i].first;
        res += rec(k - 1, nlen) + x;
    }
    res /= sz(P);
    return dp[k][len] = res;
}

class DengklekMessage {
public:
    double theExpected( vector <string> pieces, vector <string> goodSubstring, long long K ) {
        P = pieces;
        G = "";
        for (int i = 0; i < sz(goodSubstring); ++i) {
            G += goodSubstring[i];
        }
        initC();
        memset(Mark, false, sizeof(Mark));
        if (K <= sz(G)) return rec(K, 0);
        int L = sz(G);
        double t = rec(L, 0);
        double t1 = rec(L + 1, 0);
        return t + (t1 - t) * (K - L);
    }
};

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

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.