### PROBLEM LINK:

**Author:** Hasan Jaddouh

**Tester:** Alexey Zayakin

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

EASY

### PREREQUISITES:

Dynamic programming

### PROBLEM:

You’re given two strings A and B. You have to merge those strings into string C in such a way that amount of valid indices i such that C_i eq C_{i+1} is minimized.

### QUICK EXPLANATION

Use 2 \cdot n \cdot m dynamic programming to mark length of merged prefixes and string from which you took last letter.

### EXPLANATION:

This problem is straightforward if you use dynamic programming of following form:

You can implement it in the following manner:

```
int sz[2];
cin >> sz[0] >> sz[1];
string a[2];
cin >> a[0] >> a[1];
int dp[sz[0] + 1][sz[1] + 1][2];
memset(dp, 0x3F, sizeof(dp));
dp[1][0][0] = dp[0][1][1] = 1;
int idx[2];
for(idx[0] = 0; idx[0] <= sz[0]; idx[0]++) {
for(idx[1] = 0; idx[1] <= sz[1]; idx[1]++) {
for(int pz = 0; pz <= 1; pz++) {
for(int nz = 0; nz <= 1; nz++) {
if(idx[nz] < sz[nz] && idx[pz] > 0) {
int ndx[2] = {idx[0] + !nz, idx[1] + nz};
dp[ndx[0]][ndx[1]][nz] = min(dp[ndx[0]][ndx[1]][nz],
dp[idx[0]][idx[1]][pz] + (a[nz][idx[nz]] != a[pz][idx[pz] - 1]));
}
}
}
}
}
cout << min(dp[sz[0]][sz[1]][0], dp[sz[0]][sz[1]][1]) << endl;
```

Note that it should be 2 \cdot 2 \cdot n \cdot m and not 26 \cdot n \cdot m since the last one will not fit into TL.

In the code above we consider that we already merged prefixed A_{idx_1} and B_{idx_2}. Variable pz indicates if we had character from A (in case pz=0) or from B (in case pz=1) on the top before adding new character and nz indicates from which string we added new character (same way as pz). After that new character we can assume that we merged prefixed A_{ndx_1} and B_{ndx_2}. Answer for DP[ndx_1][ndx_2][nz] can be relaxed by answer for DP[idx_1][idx_2][pz] plus one if old top character and new top character do not match.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.