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.