The trick: Resetting arrays in no time.

Consider AlphabetPaths (problem statement). I have described a solution in the previous post: You have to do meet in the middle. For each cell, find all the size-11 paths that start at the cell. Indeed there are less than 3¹¹ of them per cell, much less in fact.

The core of the problem is that for each of these paths, you have to count the number of paths that also start at that cell but that have a complementary set of letters (so that when you put these two paths together, placing the cell at the middle, you get a complete path). That meet in the middle(*) solution is simple once we describe it. There is a catch I have not mentioned in the previous blog post though: The constraints are so tight that you will most likely need to fetch the count in O(1) time.

Now, accessing the count in O(1) time is complicated. Anything like a hash table would add some overhead and you will have the issue of having to deallocate it or reset it. For a path to be complementary, it depends only on the set of letters used by the path. You can represent the set of letters as a bit mask of 21 bits. That gives us 2^21 possible indexes for our look up table. So, how about using a single array?

But there's the problem and that's what this blog post is about:

The issue
You have a single array memo, it is large, let us say size 2²¹. You have to repeat the following procedure plenty of times (let us say 21 x 21) :
a) Reset the memo array.
b) Call a bruteforce / backtracking function that selects a bunch of possible solutions, gets an index i that classifies the solution and increases memo[i].

The thing is that although resetting the array once is possible, resetting the array 21x21 times is going to be very slow. The alternative, to simply use a 21x21x2²¹ will not work because of memory constraints. What to do?

The trick
This one trick works in some specific scenarios. Let (T+1) be the maximum value for each index. Let us also say that 21x21 * T is small enough to fit a 32 bits or 64 bits integer.

Assume we only reset the array once then in the first of the 21x21 operations, the array will be filled with zeros. You can know one thing, never during this operation will any of the values in the array exceed T.

Here is the trick: In the second step, we will not store the wanted values in the array, but we will store (value + T) instead. In other words, every value stored in the second step will be at least T. We already know that every value stored in the first step will be less than T. Thus we can easily verify if a value currently in the array comes from step 1 or step 2, if it is larger than or equal to T, it comes from step 2, else from step 1.

When reading the array during step 2, simply verify if they are already greater than or equal to T, if they are, subtract T from the value in the array and you will get the real stored value.

When increasing the values in the array during step 2, first read the previous value using the previous paragraph's logic. Add 1 to the real value and then store the new value in the array. In order to store, add T to the new value.

This can be extended to each of the 21x21 steps. In step 3, define that all valid values have to be larger than or equal to 2*T, in step 4, 3*T, etc, etc, etc.

Here's a solution for AlphabetPaths that exploits this trick. The parts that are related to the trick are commented with (**).

import java.util.*; 
public class AlphabetPaths { 
    final String LATIN = "ABCDEFZHIKLMNOPQRSTVX"; 
     
    final int   HALF = 11; 
    final int   ALL  = 21; 
    final int[] dx = new int[]{0,0,1,-1}; 
    final int[] dy = new int[]{1,-1,0,0}; 
    int w, h; 
    String[] letterMaze; 
     
    int time; 
    final int   MAX_MASKS = 1<<13; 
     
    long res; 
    int  alwaysInMask; 
     
    int[] latinId; 
     
     
    void dfs(int[] masks, int x, int y, int mask, int n) 
    { 
        if ( x >= 0 && y >= 0 && x < w && y < h ) { 
            char ch = letterMaze[x].charAt(y); 
            if ( ch != '.' ) { 
                int c = latinId[ (int)(ch - 'A') ]; 
                if ( (mask & (1<<c)) == 0 ) { 
                    int nmask = mask |(1<<c); 
                    n++; 
                     
                    // Found a length-11 path. 
                    if( n==HALF) { 
                        int neg = ( ( ((1<<ALL)-1) & ~nmask ) | alwaysInMask ); 
                        // (**) 
                        // We need to find the true value of masks[neg]. 
                        long q = masks[neg]; 
                        if  ( q < time )  {  //masks[neg] was used in a previous step. 
                            q = 0;          // its real value for this step is 0. 
                        } else { 
                            q -= time;     // Else the real value is q - time. 
                        } 
                        res += q; 
 
                        // Now we need to increase masks[nmask]. 
                        if (masks[nmask] < time ) { 
                            masks[nmask] = time; //This is the first time we use this 
                                                 //index in this step, reset it to 0. 
                                                 //(which is stored as time + 0). 
                        } 
                        masks[nmask] ++; // increase it. 
                    } else { 
                        //continue building the path. 
                        for (int i=0; i<4; i++) { 
                            int x2 = x + dx[i]; 
                            int y2 = y + dy[i]; 
                            if ( x2>=0 && y2>=0 && x2<w && y2<h) { 
                                dfs(masks, x2,y2, nmask, n); 
                            } 
                        } 
                    } 
                     
                    n--; 
                } 
            } 
             
        } 
    } 
     
    
    public long count(String[] letterMaze) { 
        loadLatinId(); 
        this.letterMaze = letterMaze; 
        w = letterMaze.length; 
        h = letterMaze[0].length(); 
        res = 0; 
        int[] masks = new int[1<<ALL]; 
         
        time = 0; 
         
        for (int x=0; x<w; x++) { 
            for (int y=0; y<h; y++) { 
                char ch = letterMaze[x].charAt(y); 
                if ( ch == '.' ) { 
                    continue; 
                } 
                int c = latinId[ (int)(ch - 'A') ]; 
                 
                // (**) Update the time value. 
                time += MAX_MASKS; 
                alwaysInMask = (1<<c); 
                 
                // Try all the size 11 paths that start here. 
                dfs(masks, x, y, 0, 0); 
            } 
        } 
        return res*2; 
    } 
 
    void loadLatinId() { 
        latinId = new int[26]; 
        for (int i=0; i<26; i++) { 
            latinId[i] = -1; 
            for (int j=0; j<LATIN.length(); j++) { 
                if ( LATIN.charAt(j) == (char)( (int)'A' + i) ) { 
                    latinId[i] = j; 
                } 
            } 
        } 
 
    } 
} 

(*) Edit: Isn't it amazing that meet in the middle does not have a wikipedia page? It is actually difficult to get a good explanation for it. So much that the most suitable explanations for topcoder-like problems I could find are basically me saying to look an old editorial.