Explanation for SRM 613 Hard problem is ready

And because TC wiki is still closed to guests, I decided to post it here:

This is a cool little evil problem that is actually "easy" in concept. There is just a little magic trick to make the dynamic programming work.

We have a board of `M` columns and `N` rows. `M` is up to 200, `N` is up to 50. For each row `i`, The area composed out of left[i] of the left-most cells must contain exactly one checker and the area composed out of the right[i] of the right-most cells must contain exactly one checker. These areas never overlap. Each column may contain at most one checker. Return the number of valid ways to follow these condition modulo 1000000007.

If there were no left parts

Let's try an easier version of the problem. What if the problem just had the right-most parts' condition? We have a list right such for the i-th that you must put exactly 1 checker on the right[i] right-most cells in that row. You can also put at most once cell per column.

This version is much simpler to solve. We can try to decide, from column 0 to column `M-1`, what to do:

• We could decide not to put any checker on this column.
• We can put a checker, outside any right-most area.
• We can put a checker inside one of the right-most areas.

There are some useful observation we can make:

If we place the checker on an unrestricted cell or don't put a checker at all, the number of ways to decide the remaining columns shall be exactly the same, regardless of what cell we pick (or not) for the checker:

The second observation is more important. In this example, in column 0 there are two "active" right-part. In column 2, there are three active right parts. In column 3, five active right parts. Etc. Once we take this perspective, we can find a recurrence by noticing what happens if we put a checker on one of the column's active parts.

Placing a checker will just make one of the active right parts, no longer usable. All that matters is the number of active right parts in a column and the number of parts that were already used in previous steps.

With this information it is possible to make an `O(MN)` dynamic programming approach. Use a function `f(x, r)` where `x` is the number of columns we already processed and `r` is the number of available right-parts, which increases in the columns where new right parts begin and decrements whenever we choose to use one of them.

The left parts

When the left parts are included, we have more issues. From the previous section we know that all we need in order to handle the right parts is to know how many of them were already used in the previous steps. So let's focus on the left parts.

Once again, we decide from column 0 to column 1, to the previous options we add an option: Add the checker on top of a left restriction area. In this case, however, the left restriction areas are not indistinguishable from each other...

When deciding for column 5 and later, the only information we need about the right parts is that one is taken. The left parts are more complicated because the two taken ones are very different from the free one.

The clever solution is to avoid making a decision until it is absolutely necessary. Let's just decide in which columns we are going to place checkers on left areas. Without selecting the row specifically until it is completely necessary.

For example, we process the first two columns and decide that they both will contain checkers that would occupy left areas. We don't decide the actual rows used by those checkers yet.

Before moving to column 2, we need to make sure that the left area in row 0 (top) is taken by a checker. Because this left area will not be active anymore. There are two columns that can contain this checker, pick one:

The column that we do not pick would still be available for other rows later. The nice thing is that we can pick any of them and the number of ways to fill the remaining columns will remain the same. In this case, out of two columns assigned to have a checker in the left area, we need to pick one. But multiple left areas may finish in the same column. We can just use a binomial coefficient to calculate the number of ways to pick.

In column 2, we will be forced to leave a checker in the last cell of the left area in the third row. Then we progress to column 3. This will have four options: 1) Place checker on a right area. 2) Place checker on one of the left areas in this column (but leave the decision of the specific row open). 3) Place checker in a cell that has no restriction and 4) Don't place a checker in this column:

What we can conclude is that we can represent the state of a sub-problem with three parameters: `x`: The number of columns already visited / index of the current column. `u`: Number of columns we decided to make available to get used by left areas. `r`: Number of active right areas. In the dynamic programming, we make decisions to alter these parameters, and, when one or more left-areas finish, we need to multiply the current result by a binomial coefficient to choose the specific columns that will be used by those rows. We also need to multiply by a factorial to permute the positions. See below:

In this case, there are 24 ways to choose the position for the checkers in the 3 left areas that have just finished. There are 4 available columns and 3 areas that must finish: `((4),(3))` multiplied by `3!` permutations of the positions. Those images above are just two out of the 24 examples.

Code

With knowledge of the 3 needed parameters to represent the state, we can build a dynamic programming / memoziation solution that needs `O(MN^2)` time.

const int MOD = 1000000007;

long C[201][201];
long fact[201];

void init()
{
    memset(C, 0, sizeof(C));
    for (int i = 0; i <= 200; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
        }
    }
    fact[0] = 1;
    for (int i = 1; i <= 200; i++) {
        fact[i] = (i * fact[i-1]) % MOD;
    }
}


int dp[201][51][51];
// x: processed columns
// u: left parts used
// r: active right parts
int rec(int x, int u, int r)
{
    int& res = dp[x][u][r];
    if (res == -1) {
        
        if (x == M) {
            res = (r == 0);
        } else {
        
            res = 0;
            // common code used to process a number of used left parts nu and 
            // active right parts nr once the transitions below pick it:
            // We use a lambda to be able to update the res variable correctly.
            // p is the number of times we need to add this case.
            auto process = [&](long p, int nu, int nr) {
                if (nu >= endLeft[x]) {
                    p *= ( C[nu][endLeft[x]] * fact[endLeft[x]] ) % MOD;
                    p %= MOD;
                    res += (int)( (p * rec(x+1, nu - endLeft[x], nr) ) % MOD );
                    res %= MOD;
                }
            };
            int nr = r + startRight[x];
            
            // use a left part
            if (u + 1 <= activeLeft[x]) {
                process(1, u+1, nr);
            }
            // use a right part 
            if (nr > 0) {
                process( nr, u, nr - 1);
            }
            // don't use anything
            process(1, u, nr);
            // put in middle
            if ( middle[x] > 0) {
                process( middle[x], u, nr );
            }
        }
        
    }
    return res;
}

int M;
int endLeft[200];
int startRight[200];
int activeLeft[200];
int middle[200];

int getNumber(vector<int> left, vector<int> right, int M)
{
    init();
    this->M = M;
    memset(dp, -1, sizeof(dp));
    
    fill(endLeft, endLeft + M, 0);
    fill(startRight, startRight + M, 0);
    fill(middle, middle + M, 0);
    
    for (int i = 0; i < left.size(); i++) {
        for (int j = left[i]; j < M - right[i]; j++) {
            middle[j]++;
        }
    }
    
    for (int l : left) {
        endLeft[l-1]++;
    }
    activeLeft[0] = left.size();
    for (int i = 1; i < M; i++) {
        activeLeft[i] = activeLeft[i-1] - endLeft[i-1];
    }
    for (int r: right) {
        startRight[ M - r]++;
    }
    return rec(0, 0, 0);
}