Help with "Interleavings and Blocks "

Problem: https://www.codechef.com/ZCOPRAC/problems/ZCO20002/

Going through all the discussions about this problem, I see that everybody has used four DP states, viz. the number of elements taken from A, the number of elements taken from B, from which array (A or B) was the last element taken, and the number of blocks. Even I went with those four states and got an AC, but I wanted to try the problem with just three DP states, and so I did that and got wrong answers even for the sample test cases.

My idea was to use just three DP states, DP[i][j][k] (i elements taken from A, j elements taken from B, and k blocks in total) with the DP transition being as follows,
DP[i][j][k] = DP[i-1][j][k-(A[i-1] != A[i])] + DP[i-1][j][k-(B[j] != A[i])] + DP[i][j-1][k-(B[j-1] != B[j])] + DP[i][j-1][k-(A[i] != B[j])]. But this doesn’t work.

So my question is, can we not solve this problem with just three DP states? And if we can, then what is wrong with the above DP relation?

AC CODE (FOUR STATES)
#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MOD = 1e8+7;

int n, m, k;
vector<int> A(105), B(105);

//dp[a][b][c][d]->interleavings with a A's, b B's, c blocks, d [last element chosen (0-A,1-B)]
ll dp[105][105][205][2];

ll count(int a, int b, int c, int d) {
    if(a == 0 && b == 1) return dp[a][b][c][d] = (c == 1);
    if(a == 1 && b == 0) return dp[a][b][c][d] = (c == 1);
    if(dp[a][b][c][d] != -1) return dp[a][b][c][d];
    
    dp[a][b][c][d] = 0;
    //segment ends with A[a]
    if(a > 1 && !d) dp[a][b][c][d] += count(a-1,b,c-(A[a-1] != A[a]),0)%MOD;
    if(b >= 1 && !d) dp[a][b][c][d] += count(a-1,b,c-(B[b] != A[a]),1)%MOD;
    //segment ends with B[b]
    if(a >= 1 && d) dp[a][b][c][d] += count(a,b-1,c-(A[a] != B[b]),0)%MOD;
    if(b > 1 && d) dp[a][b][c][d] += count(a,b-1,c-(B[b-1] != B[b]),1)%MOD;
    
    return dp[a][b][c][d]%MOD;
}

int main() {
    FASTIO
    
    int t;
    cin >> t;
    while(t--) {
        A.assign(105,0);
        B.assign(105,0);
        memset(dp,-1,sizeof(dp));
        
        cin >> n >> m >> k;
        for(int i=1; i<=n; i++) cin >> A[i];
        for(int j=1; j<=m; j++) cin >> B[j];
        
        cout << (count(n,m,k,0)+count(n,m,k,1))%MOD << "\n";
    }
    
    return 0;
}
CODE (THREE STATES)
#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MOD = 1e8+7;

int n, m, k;
vector<int> A(105), B(105);
ll dp[105][105][205];

//d->number of blocks
ll count(int a, int b, int d) {
    if(a == 0 && b == 1) return dp[a][b][d] = (d == 1);
    if(a == 1 && b == 0) return dp[a][b][d] = (d == 1);
    if(dp[a][b][d] != -1) return dp[a][b][d];
    
    dp[a][b][d] = 0;
    //segment ends with A[a]
    if(a > 1) dp[a][b][d] += count(a-1,b,d-(A[a-1] != A[a]))%MOD;
    if(a >= 1) dp[a][b][d] += count(a-1,b,d-(B[b] != A[a]))%MOD;
    //segment ends with B[b]
    if(b > 1) dp[a][b][d] += count(a,b-1,d-(B[b-1] != B[b]))%MOD;
    if(b >= 1) dp[a][b][d] += count(a,b-1,d-(A[a] != B[b]))%MOD;
    
    return dp[a][b][d];
}

int main() {
    FASTIO
    
    int t;
    cin >> t;
    while(t--) {
        A.assign(105,0);
        B.assign(105,0);
        memset(dp,-1,sizeof(dp));
        
        cin >> n >> m >> k;
        for(int i=1; i<=n; i++) cin >> A[i];
        for(int j=1; j<=m; j++) cin >> B[j];
        
        cout << count(n,m,k) << "\n";
    }
    
    return 0;
}

@galencolin, @everule1 Please help.

You need to know whether the last item was from A or B. Sometimes a block may only be added if last element was from A. You will not be able to discriminate the cases here, so you will be adding both when the last element was from A and B.

1 Like