## Question 3 – Minimum-Cost Interleaving of Two S...

Question

Question 3 – Minimum-Cost Interleaving of Two Sequences

You are given two sequences A of length N and B of length M.

You must interleave them into a single sequence of length N + M. The interleaving must preserve the original relative order of the elements within A and within B.

You are also given K magic separators. You may insert up to K magic separators anywhere in the interleaved sequence.

The cost of the interleaved sequence is the sum of the absolute differences between all pairs of adjacent elements. However, if a magic separator is placed between two adjacent elements, the cost between those two elements becomes 0 (the separator effectively breaks the sequence into two disjoint segments and resets the penalty).

Your task is to find the minimum total interleaving cost.

Input Format

The first line contains an integer N, denoting the length of sequence A.
The second line contains an integer M, denoting the length of sequence B.
The third line contains an integer K, denoting the maximum number of magic separators available.
The fourth line contains N space-separated integers denoting the array A[i].
The fifth line contains M space-separated integers denoting the array B[i].

Constraints

(1 \le N \le 500)
(1 \le M \le 500)
(1 \le K \le 10)
(1 \le A[i] \le 10^5)
(1 \le B[i] \le 10^5)

Example 1

Input

text
3
3
1
10 20 30
100 110 120

Output

Explanation

Input is N = 3, M = 3, K = 1.

A = {10, 20, 30}
B = {100, 110, 120}

Without separators, interleaving A and B creates huge differences.

The best strategy is to place the separator after 10, 20, 30.

Interleaved sequence:

10, 20, 30 | 100, 110, 120

Cost within A:

|20−10| + |30−20| = 20

Cost within B:

|110−100| + |120−110| = 20

Cost across the separator:

Total minimum cost:

20 + 20 = 40

Example 2

Input

Output

Explanation

Input is N = 2, M = 2, K = 0.

A = {1, 10}
B = {5, 15}

No magic separators are available.

Optimal interleaving:

1, 5, 10, 15

Cost:

text
|5−1| + |10−5| + |15−10|
= 4 + 5 + 5
= 14

Example 3

Input

text
4
1
1
1 2 100 101
50

Output

Explanation

Input is N = 4, M = 1, K = 1.

A = {1, 2, 100, 101}
B = {50}

Optimal sequence:

1, 2, 50 | 100, 101

Cost calculation:

Cost from 1 to 2 = 1
Cost from 2 to 50 = 48
Cost from 50 to separator = 0
Cost from separator to 100 = 0
Cost from 100 to 101 = 1

Total cost:

1 + 48 + 0 + 1 = 50

C++

Answer 1

Dynamic Programming

Let:

dpA[i][j][s] = minimum cost after using the first i elements of A and first j elements of B, using exactly s separators, where the last element is A[i-1].
dpB[i][j][s] = the same, but the last element is B[j-1].

From each state, append the next element from either sequence:

Pay the absolute difference normally.
Or spend one separator and pay 0.

The first element contributes no cost.

C++17 Implementation

cpp
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N;
    cin >> M;
    cin >> K;

    vector<int> A(N), B(M);

    for (int &x : A) cin >> x;
    for (int &x : B) cin >> x;

    // There are only N + M - 1 adjacent pairs.
    K = min(K, N + M - 1);

    const int S = K + 1;
    const int64 INF = numeric_limits<int64>::max() / 4;

    auto id = [M, S](int i, int j, int separators) -> size_t {
        return (static_cast<size_t>(i) * (M + 1) + j) * S
               + separators;
    };

    const size_t stateCount =
        static_cast<size_t>(N + 1) * (M + 1) * S;

    vector<int64> dpA(stateCount, INF);
    vector<int64> dpB(stateCount, INF);

    // The interleaving may start with A[0] or B[0].
    dpA[id(1, 0, 0)] = 0;
    dpB[id(0, 1, 0)] = 0;

    auto difference = [](int x, int y) -> int64 {
        return llabs(static_cast<int64>(x) - y);
    };

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            for (int used = 0; used <= K; ++used) {
                /*
                 * Current last element is A[i - 1].
                 */
                int64 currentA = dpA[id(i, j, used)];

                if (currentA != INF) {
                    // Append the next element from A.
                    if (i < N) {
                        int64 edgeCost = difference(A[i - 1], A[i]);

                        // Without a separator.
                        dpA[id(i + 1, j, used)] =
                            min(dpA[id(i + 1, j, used)],
                                currentA + edgeCost);

                        // With a separator.
                        if (used < K) {
                            dpA[id(i + 1, j, used + 1)] =
                                min(dpA[id(i + 1, j, used + 1)],
                                    currentA);
                        }
                    }

                    // Append the next element from B.
                    if (j < M) {
                        int64 edgeCost = difference(A[i - 1], B[j]);

                        // Without a separator.
                        dpB[id(i, j + 1, used)] =
                            min(dpB[id(i, j + 1, used)],
                                currentA + edgeCost);

                        // With a separator.
                        if (used < K) {
                            dpB[id(i, j + 1, used + 1)] =
                                min(dpB[id(i, j + 1, used + 1)],
                                    currentA);
                        }
                    }
                }

                /*
                 * Current last element is B[j - 1].
                 */
                int64 currentB = dpB[id(i, j, used)];

                if (currentB != INF) {
                    // Append the next element from A.
                    if (i < N) {
                        int64 edgeCost = difference(B[j - 1], A[i]);

                        // Without a separator.
                        dpA[id(i + 1, j, used)] =
                            min(dpA[id(i + 1, j, used)],
                                currentB + edgeCost);

                        // With a separator.
                        if (used < K) {
                            dpA[id(i + 1, j, used + 1)] =
                                min(dpA[id(i + 1, j, used + 1)],
                                    currentB);
                        }
                    }

                    // Append the next element from B.
                    if (j < M) {
                        int64 edgeCost = difference(B[j - 1], B[j]);

                        // Without a separator.
                        dpB[id(i, j + 1, used)] =
                            min(dpB[id(i, j + 1, used)],
                                currentB + edgeCost);

                        // With a separator.
                        if (used < K) {
                            dpB[id(i, j + 1, used + 1)] =
                                min(dpB[id(i, j + 1, used + 1)],
                                    currentB);
                        }
                    }
                }
            }
        }
    }

    int64 answer = INF;

    // We may use any number of separators from 0 through K.
    for (int used = 0; used <= K; ++used) {
        answer = min(answer, dpA[id(N, M, used)]);
        answer = min(answer, dpB[id(N, M, used)]);
    }

    cout << answer << '\n';
    return 0;
}

Correctness

Every valid partial interleaving ends with either an element from A or an element from B, which is exactly what the two DP states represent.

When adding the next element, there are precisely two possibilities for the new adjacent pair:

No separator is used, so its absolute difference is added.
A separator is used, so the added cost is zero.

Thus, every valid interleaving and separator placement is considered. Taking the minimum over states using 0 through K separators gives the optimal cost.

Complexity

Time: O(N × M × K)
Memory: O(N × M × K)

The implementation also supports K = 0, as used in Example 2.

## Question 3 – Minimum-Cost Interleaving of Two S...

質問