# Minimizing cost of a given sequence by partitoning [closed]

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  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.

I’m trying to solve it in nlog(n) complexity ideally or at most a fast n^2.

Posted on Categories proxies