4
$\begingroup$

Given a sequence of positive integers of size N(let) divide it into at most K(K > N/C) disjoint parts/subsequences in order to minimize the "cost" of the entire sequence.

Partitions cannot overlap, for example [1,2,3,4,5] can be divided into [1,2], [3,4] and [5] but not [1,3] and [2,4,5].

The cost of a subsequence is computed as the number of repeated integers in it. The cost of the entire sequence is computed as the sum of costs of all the subsequences and a fixed positive integer cost C times the number of partitions/divisions of the original sequence.

How should I go about determining the position and number of partitions to minimize the total cost?

Some more examples:

The given list = [1,2,3,1] Without any partitions, its cost will be 2 + C, as 1 occurs two times and the original sequence is counted as one partition.

[1,1,2,1,2] Without any partitions, its cost will be 5, as 1 occurs three times and 2 occurs two times. If we divided the subsequence like so [1,1,2],[1,2] then the cost becomes 2 + 2*C, where C is the cost of partitioning.

I have actually solved the problem for the case of C = 1, but am having problems generalizing it to higher values of C.

For C = 1 it makes sense to partition the sequence while traversing it from one direction as soon as a repetition occurs as the cost of a single repetition is 2 whereas the cost of partitioning is 1.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

Let $f(x_1, x_2, \dots, x_N)$ denote the minimum cost of any partition of $x_1, \dots, x_N$; let $f(x_1, x_2, \dots, x_N; \ell)$ denote the minimum cost of a partition in which the last part has length $\ell$ (in other words, in which the last part is $[x_{N-\ell+1}, \dots, x_N]$.)

If we can compute $f(x_1, x_2, \dots, x_N; \ell)$ for all $\ell=1,\dots,N$, then $f(x_1, x_2, \dots, x_N)$ is just the minimum of those.

We can compute $f(x_1, x_2, \dots, x_N; \ell)$ for all $\ell=1, \dots, N$ at the same time recursively, in terms of $f(x_1, x_2, \dots, x_{N-1}; \ell)$. We have:

  • $f(x_1, x_2, \dots, x_N; 1) = f(x_1, x_2, \dots, x_{N-1}) + C$.
  • for $\ell>1$, $f(x_1, x_2, \dots, x_N; \ell) = f(x_1, x_2, \dots, x_{N-1}; \ell-1)$ if $x_N \notin \{x_{N-\ell+1}, \dots, x_{N-1}\}$.
  • for $\ell>1$, $f(x_1, x_2, \dots, x_N; \ell) = f(x_1, x_2, \dots, x_{N-1}; \ell-1) + 1 $ if $x_N \in \{x_{N-\ell+1}, \dots, x_{N-1}\}$.

If there is a limit $K$ to the number of parts, we would want to refine this function further; we could write $f(x_1, x_2, \dots, x_N; \ell, k)$ for the minimum cost of a partition in which the last part has length $\ell$ and there are $k$ parts total. The recurrence is similar, except with more values to keep track of and compute. But in your case, provided $K > N/C$, we don't need to do that; a solution with more than $K$ parts will have cost more than $N$, so it will never be optimal.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .