Codeforces Rockethon 2015 Problem E1/E2 - Subarray Cuts

Problem Statement:
513E2 - Subarray Cuts

Solution:
This is another excellent problem, for which its solution demonstrates the power of dynamic programming. Unfortunately the implementation is very error prone due to the handling of edge cases (at least for me). The official editorial to this problem is also unfortunately very hard to read, partly because the TeX are not typed correctly. Anyway, here is my note about this problem.

The problem is difficult because we are presented with modulus operations. When we try to do a naive DP by keeping track of the value of \(s_j\), we will soon realize that we also need to keep track of the value for \(s_{j-1}\), which inflates the space search very badly. As it turns out, there is another way of looking into the problem which I think is very clever.



Let the n numbers be a[1..n], and \(M = \sum |s_{j-1}-s_{j}| \). The limiting constraint here is that we couldn't know before hand whether \(|s_{j-1}-s_j|\) will evaluate to \(+(s_{j-1}-s_j)\) (positive sign) or \(-(s_{j-1}-s_j)\) (negative sign). But hey, actually we don't even need to know, because we can just _assume_ beforehand the sign of \(|s_{j-1}-s_j|\)! Why, because when we apply dynamic programming to find the maximum possible value of M, the correct signs will eventually be assumed by our algorithm so as to reach the maximum value of M :)

For the dynamic programming, we keep track of the following 5 (!) states:
1. i, means that we have considered elements in a from 1 up to i.
2. j, the number of subarrays constructed so far.
3. e, the 'empty' flag of s[j]. e = 0 means s[j] is currently empty, otherwise e = 1.
4. c1, and
5. c2, where c1 and c2 are the assumed signs associated with \(|s_{j-1}-s_{j}|\) and \(|s_{j} - s_{j+1}|\) respectively.

Let D(i,j,e,c1,c2) be a function in which by the end of the algorithm, we will get D(i,k,1,c1,c2) the maximum possible M using elements in a[1..i] to form k subarrays, such that s[k] is not empty, and the last two signs of the terms in M is c1 and c2.

The remaining part is *just* implementation detail, and very mathematical. You might want to refer to this part if you are stuck with figuring out the transitions between the DP states. Here are the transitions from state (i,j,e,c1,c2):
1. Suppose currently j = 0. This means that there are currently no subarrays formed. In this case, we can either form a new subarray s[1] using a[i+1], or skip a[i+1].
If we use a[i+1] to form s[1], We are currently presented with this expression:
[c1(0-s[1]) + c2(s[1]-s[2])] + ...
But we must eliminate the first term c1(0-s[1]) because M starts with |s[1]-s[2]|.
So we have currently s[1] = a[i+1].
Hence, we update D(i+1,j+1,1,c1,c2) to D(i,j,e,c1,c2) + (a[i+1] * c2) accordingly.

2. On the other hand, if j > 0, but less than k, then we have formed j subarrays s[1] .. s[j] using elements in a[1..i]. In this case, we have several cases:

2.1 for any value of e, we can choose to pick a[i+1] and add it to current s[j]. Hence in essence we are extending s[j] with a[i+1]. We have:
... + [c1(s[j-1]-s[j]) + c2(s[j]-s[j+1])] + ...
Hence, if j is not equal to 1, we would want to add a[i+1] to both s[j] in the above term. This is equivalent to adding P = -c1*a[i+1] + c2*a[i+1]. And if j equals to 1, we only add a[i+1] to the second s[j] (since the first term must be equal to 0), hence it is equivalent to adding P = c2*a[i+1].
Hence we update D(i+1,j,1,c1,c2) to D(i,j,e,c1,c2) + P accordingly.

2.2 if e equal to 0, we can choose not to pick a[i+1] since s[j] is still empty.
Hence we update D(i+1,j,0,c1,c2) to D(i,j,e,c1,c2) accordingly.

2.3 if e is equal to 1, we can choose to create a new subarray using a[i+1] or an empty one. The analysis is similar to 2.1

3. Finally if j is equal to k, we can do either 2.1 and 2.2 but with the caveat that we don't add a[i+1] to the second s[j]. Hence the analysis is also similar to the above cases.

Here is my implementation:

#include <cstdio>
#include <algorithm>
using namespace std;
//dp[i][j][e][c1][c2] : maximum  [...] + c1(s[j-1]-s[j]) + c2(s[j]-s[j+1]), e is a flag whether s[j] is currently empty
int dp[30003][203][2][2][2];
int inf = (int) 400000000;
int N, K;
int a[30003];
int s[2] = {1,-1};
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;++i){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<=N+1;++i){
        for(int j=0;j<=K+1;++j){
            for(int e=0;e<2;++e){
                for(int c1=0;c1<2;++c1){
                    for(int c2=0;c2<2;++c2){
                        dp[i][j][e][c1][c2] = -inf;
                        //base case: j is 0 (no subarrays yet)
                        if(j==0 && e==0){
                            dp[i][j][e][c1][c2] = 0;
                        }
                    }
                }
            }
        }
    }
    int ans = -inf;
    for(int i=0;i<N;++i){
        for(int j=0;j<=K;++j){
            for(int e=0;e<2;++e){
                for(int c1=0;c1<2;++c1){
                    for(int c2=0;c2<2;++c2){
                        if(dp[i][j][e][c1][c2]==-inf)continue;
                        if(j==0){
                            // start a sub array using current a[i+1].
                            // hence a[i+1] is in s[1], e = 1
                            // c1(0 - s[1]) + c2(s[1] - s[2]) + x (s[2] - s[3]) + ...
                            // ^----------^ => 0
                            dp[i+1][j+1][1][c1][c2] = max(dp[i+1][j+1][1][c1][c2], s[c2] * a[i+1]);
                            // otherwise, don't start a new sub array. 
                        } else if (j <= K-1) {
                            // we have c1(s[j-1] - s[j]) + c2(s[j] - s[j+1]) + ...
                            // currently considering a[i+1].
                            // insert a[i+1] to s[j]
                            dp[i+1][j][1][c1][c2]  = max(dp[i+1][j][1][c1][c2], (j==1?0:-s[c1]*a[i+1]) + s[c2]*a[i+1] + dp[i][j][e][c1][c2]);
                            // s[j] still empty, can not pick a[i+1] to s[j]
                            if(e==0) dp[i+1][j][e][c1][c2] = max(dp[i+1][j][e][c1][c2], dp[i][j][e][c1][c2]);
                            // ifs[j] is not empty, create new s[j+1], empty or not empty
                            if(e!=0){
                                for(int x=0;x<2;++x){
                                    //empty
                                    dp[i+1][j+1][0][c2][x] = max(dp[i+1][j+1][0][c2][x], dp[i][j][e][c1][c2]);
                                    // not empty, a[i+1] belongs to s[j+1]
                                    // c1(s[j-1] - s[j]) + c2(s[j] - s[j+1]) + c3(s[j+1] - s[j+1])
                                    dp[i+1][j+1][1][c2][x] = max(dp[i+1][j+1][1][c2][x], -s[c2]*a[i+1] + (j==K-1?0:s[x]*a[i+1]) + dp[i][j][e][c1][c2]);
                                }
                            }
                        } else if (j == K) {
                            // can insert a[i+1] to current s[j]
                            dp[i+1][j][1][c1][c2]  = max(dp[i+1][j][1][c1][c2], -s[c1]*a[i+1] + dp[i][j][e][c1][c2]);
                            // s[j] still empty, not pick a[i+1] to s[j]
                            if(e==0)dp[i+1][j][e][c1][c2] = max(dp[i+1][j][e][c1][c2], dp[i][j][e][c1][c2]);
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<=N;++i){
        for(int c1=0;c1<2;++c1){
            for(int c2=0;c2<2;++c2){
                ans = max(ans,dp[i][K][1][c1][c2]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}