^{11}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

^{21}. 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

^{21}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 (**).

importjava.util.*;publicclassAlphabetPaths{

finalString LATIN="ABCDEFZHIKLMNOPQRSTVX";

finalintHALF=11;

finalintALL=21;

finalint[] dx=newint[]{0,0,1,-1};

finalint[] dy=newint[]{1,-1,0,0};

intw, h;

String[] letterMaze;

inttime;

finalintMAX_MASKS=1<<13;

longres;

intalwaysInMask;

int[] latinId;

voiddfs(int[] masks,intx,inty,intmask,intn)

{

if(x>=0&&y>=0&&x<w&&y<h){

charch=letterMaze[x].charAt(y);

if(ch!='.'){

intc=latinId[(int)(ch-'A')];

if((mask&(1<<c))==0){

intnmask=mask|(1<<c);

n++;

//Foundalength-11path.

if(n==HALF){

intneg=((((1<<ALL)-1)&~nmask)|alwaysInMask);

//(**)

//Weneedtofindthetruevalueofmasks[neg].

longq=masks[neg];

if(q<time){//masks[neg]wasusedinapreviousstep.

q=0;//itsrealvalueforthisstepis0.

}else{

q-=time;//Elsetherealvalueisq-time.

}

res+=q;

//Nowweneedtoincreasemasks[nmask].

if(masks[nmask]<time){

masks[nmask]=time;//Thisisthefirsttimeweusethis

//indexinthisstep,resetitto0.

//(whichisstoredastime+0).

}

masks[nmask]++;//increaseit.

}else{

//continuebuildingthepath.

for(inti=0; i<4; i++){

intx2=x+dx[i];

inty2=y+dy[i];

if(x2>=0&&y2>=0&&x2<w&&y2<h){

dfs(masks, x2,y2, nmask, n);

}

}

}

n--;

}

}

}

}

publiclongcount(String[] letterMaze){

loadLatinId();

this.letterMaze=letterMaze;

w=letterMaze.length;

h=letterMaze[0].length();

res=0;

int[] masks=newint[1<<ALL];

time=0;

for(intx=0; x<w; x++){

for(inty=0; y<h; y++){

charch=letterMaze[x].charAt(y);

if(ch=='.'){

continue;

}

intc=latinId[(int)(ch-'A')];

//(**)Updatethetimevalue.

time+=MAX_MASKS;

alwaysInMask=(1<<c);

//Tryallthesize11pathsthatstarthere.

dfs(masks, x, y, 0, 0);

}

}

returnres*2;

}

voidloadLatinId(){

latinId=newint[26];

for(inti=0; i<26; i++){

latinId[i]=-1;

for(intj=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.

## 2 comments :

There is another trick for resetting the array which seems more appropriate for this problem. Since at each of the 21x21 iterations one only visits some (comparatively small) number of elements (otherwise the solution itself would time out), he could remember the indices of the visited elements and then nullify only them. This way the complexity stays exactly the same. This is not "in no time" any more, but I still felt it was worth mentioning.

Yes, that works too. Well enough actually. In my case I had to keep overhead low, very low in the judge solution , because it is java and you don't want to go over 1s in it.

At the end , the challenge case that ended bmerry's submission turned out to be very strong against meet in the middle, it is the only case in which my solution takes more than a second.

Post a Comment