Enumerate the Ways to Cover a M*N Matrix with Dominoes

Problem: Given a M*N matrix, enumerate all the different ways to cover it with dominoes (1*2 blocks). For example, for a 1*2 matrix, there are only one way; for a 2*2 matrix, there is 2 ways. The original problem is from poj 2411.

Solution: We can definitely use backtracking, but more efficient approaches should be DP. First we need to think what are the states and how to represent them. Obviously, the arrangement of dominoes on the matrix is the state. There might be multiple ways to represent them. Here we just introduce one approach: every cell in the matrix is either 0 or 1; "0" means the domino block is placed horizontally and "1" means the domino is placed vertically. If a cell, say a[i,j] is marked as "1", a[i+1,j] can't be marked as "1". Then we can use the binary sequence to represent the status of one row. For example, "0000" means two dominoes lay horizontally. Besides, there are several key observations:

• For each row, there must be even number of consecutive "zero"s. Otherwise, we cannot fully cover a row.
• The status of current row only depends on the previous row. It means we only need to look back one row.
• Then we build a status matrix d[i][s] with i as the row number and s as a particular state. d[i][s] means the number of ways to arrange a matrix with current state (all i-1 rows are filled and the ith row is with state s). Therefore,  d[i][s] =sum_{all possible d[i-1][k]}. 
• How to decide  d[i-1][k], first, s&k should be zero, which is to conform to the constraint " a[i,j] is marked as "1", a[i+1,j] can't be marked as "1". Second, s|k should be a valid arrangement, which is to conform to the constraint " there must be even number of consecutive zeros". Then the cell d[M][0] stores the answer to our problem.

typedef long long LL;
const int maxn = (1 << 12);

LL h , w , dp[12][maxn];

//to decide if it contains odd number of consecutive "zero"s
bool judge(LL s)
{
     LL cnt = 0;
     for(LL i=0; i < w; i++)
     {
         LL t = s & 1;
         if(t)
         {
             if(cnt & 1)
                 return false;
             else
                 cnt = 0;
         } else
             cnt ++;
         s >>= 1;
     }
     if(cnt & 1)
         return false;
     return true;
}

int main()
{
     while(~scanf("%lld %lld", &h, &w))
     {
         if(h == 0 && w == 0)
             break;
         memset(dp , 0 , sizeof(dp));

         //initialize the state in row 1
         for(LL i=0; i < (1 << w); i++)
         {
             if(judge(i))
             {
                 dp[1][i] = 1;
             }
         }
         for(LL i=2; i <= h; i++)
         {
              for(LL j=0; j < (1 << w); j++)
              {
                 for(LL k=0; k < (1 << w); k++)
                 {
                     LL t = j & k;
                     if(t)
                          continue;
                      //so here "t" is the actual state 
                      //on the current row, since if 
                      //the position in the above 
                      //row is marked as "1", the 
                      //position in current row must 
                      //be "0", otherwise this 
                      //iteration will be skipped by 
                      //previous "continue". But, 
                      //even though it is "0", we 
                      //need to count it as "1", 
                      //since it cannot hold domino.
                      //This is what "t=j|k;" 
                      //really means.

                      t = j | k;
                     if(judge(t))
                      {
                         dp[i][j] += dp[i - 1][k];
                      }
                 }
              }
          }
         printf("%lld\n", dp[h][0]);
     }

}

The code is from xIao.wU.

The Longest Palindrome Substring (Manacher's algorithm)

Problem: Given a string, find a longest palindrome substring.

Solution: We can use general suffix tree that stores the original string and its reverse, which is an O(N) algorithm. However, here we give a better one with less space overhead while still O(N) complexity. This algorithm is called Manacher's algorithm. If we check a string from left to right, we can leverage the palindrome check we did previously. This is from the symmetry of palindrome. The main idea is as follow:

• Create an array called P[], P[i] stands for the longest palindrome centered at location i. Here i is not the index in the original string. For the original string, the locations we need to check for palindromes contains those characters in string along with the spaces between characters. So if we have a string of length l, we need to have a P[] with length 2*l+1.
• Our goal is to fill in P[]. For a particular position, we check its left and right. If equals, we extend our check further. Otherwise, the longest palindrome centered at location is found.
• However, we need to be smarter. Actually we can leverage previous computed P[i] when we calculate a P[x] where x>i. 
• So here we add two pointers, p1 and p2, which point to the left and right of the current location i such that |i-p1| = |i-p2| and p2>i>p1. We know p1 refers to a palindrome t and i refers to a palindrome s. If the first character of t is strictly on the right of the first character of s, we know P[p2] = P[p1].
• Otherwise, say if the first character of t is not strictly on the right of the first character of s, we have P[p2] >= r - p2. where r is the right bound of the palindrome that centered at i. We then need to check if the palindrome at p2 can be longer than r - p2. The good thing is that we only need to start the characters beyond the length of r - p2.
• When the first character of t is strictly on the right of the first character of s, we don't need to move the current center (i). Only when the first character of t is not strictly on the right of the first character of s, we need to move the current center to p2.
• The total cost is O(N).

The code is as follow:

void manacher(const string &s)
{
    int len = s.size();
    if(len == 0) return;

    int m[2*len+1];
    m[0] = 0;
    m[1] = 1;
    // "cur" is the current center
    // "r" is the right bound of the palindrome
    // that centered at current center
    int cur, r;
    r = 2;
    cur = 1;

    // iterate from 2 to 2*len+1
    for(int p2=2; p2<2*len+1; p2++)
    {
        int p1 = cur- (p2-cur);
        //if p1 is negative, we need to 
        //move "cur" forward

        // re-adjust cur based on p2
        while(p1 < 0)
        {
           cur++;
           r = m[cur] + cur;
           p1 = cur- (p2-cur);

        }

        // If the first character of t is 
        // strictly on the right of the 
        // first character of s

        //

        // Or here, from the symmetry, if

        // the palindrome centered at cur

        // cover the palindrome centered at

        // p1, we know
        if(m[p1] < r - p2)
            m[p2] = m[p1];
        //otherwise
        else
        {

           // we need to explore the length of

           // the palindrome centered at p2

           // if the palindrome centered at cur covers

           // p2, we can start at "k = r-p2"

           // otherwise, we start at "k=0"

           //reset "cur" 
           cur = p2;
           int k = r-p2;
           if(k<0) k = 0;
           while(1) 
           {
              if((p2+k+1)&1)
              {
                if(p2+k+1 < 2*len+1 && p2-k-1 >=0 && s[(p2+k)/2] == s[(p2-k-2)/2])
                  k++;
                else break;
              }
               else
              {
                if(p2+k+1 < 2*len+1 && p2-k-1 >=0)
                  k++;
                else break;
              }

           }
           // set the right boundary to be "p2+k"
           r = p2+k;
           m[p2] = k;
        }


    }

 
}

About Smart Pointer, Copy-on-write

This link is very instructive.

Find the Longest Sub-sequence that is a Palindrome within a String

Problem: Given a string, you can delete any characters, find the longest sub-sequence (the characters remained after your deletion) that is a palindrome.

Solution: For palindrome problem, one trick often used is to reverse the string. Here we first reverse the string, then find the longest common sub-sequence between the new string and the original one. It is a O(n^2) solution. Remember, there could be multiple longest common sub-sequences, some of them may not be palindrome, you need do some checks.

About American Flag Sort

American Flag Sort is an extension of Dutch Flag Problem which divides an array into three group. American Flag Sort further divides an array into multiple buckets based on certain order. For example, 256 buckets based on ASCII value. Essentially, it is a in-place radix sort. It is favored for sorting integers and strings givens its speed and space advantage.

• The algorithm needs two passes. First scan the array, so that we know the number of the the objects that will be stored in each bucket.
• Then we know the start location of each bucket. Scan the array for the second time, put the object to the corresponding bucket and update the bucket cursor.
• If sorting strings, may need to apply the same algorithm to sort objects within each bucket.

0-1 Knapsack Problem

Problem:  Given a knapsack that can hold at most W weight items, also given a list of items with their weight wi and value vi (no items share the same weight), try to find a valid assignment which achieve the highest value in the knapsack (can't  be over-weighted at the same time).

Solution: We can use DP to solve this problem. However, one-dimension DP is not enough. If we only record state s[0], s[1], ... s[W], the later state may not be able to reuse previous states. Instead, we need a two-dimension DP here:

• First sort the items based on their weights
• The status we want to calculate is s[i, w], which means if the total weight is w and we can only use up To the ith item (based on weight and non-descending), the optimal maximum value we can get.
•  s[0, w] = 0 and  s[i, 0] = 0. 
• For  s[i, w], if wi > w,  s[i, w] =  s[i-1, w]; otherwise,  s[i, w] = max ( s[i-1, w], s[i-1, w-wi] + vi).

Multi-Processor Scheduling Problem

Problem: Give a multi-processor machine with n processors and m jobs, how to make a scheduling that has the shortest finish time. Each job may take different amount of time to process.

Solution: There are also some variants to this problem, like putting m integers to n buckets. The solution to this problem can be based on some heuristics and is called LPT algorithm. Attention: this is a greedy approach which is a sub-optimal solution, not an optimal solution.

• Basically we first sort the job based on their process time.
• Choose the job with the longest process time among the current unprocessed jobs and put it into a machine which has the earliest finish time so far.
• Repeat the above steps until all jobs are assigned.
• The complexity is O(m*logm+m*logn+n).