Yet Another Minimization Problem
Contest: Codeforces Round 438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 2500
Tags: divide and conquer, dp

You are given an array of n integers a1... an. The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into k non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.

Input format:
The first line contains two integers n and k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20))  — the length of the array and the number of segments you need to split the array into.

The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n) — the elements of the array.

Output format:
Print single integer: the minimum possible total cost of resulting subsegments.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example it's optimal to split the sequence into the following three subsegments: [1], [1, 3], [3, 3, 2, 1]. The costs are 0, 0 and 1, thus the answer is 1.

In the second example it's optimal to split the sequence in two equal halves. The cost for each half is 4.

In the third example it's optimal to split the sequence in the following way: [1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]. The costs are 4, 4, 1.

Example input:
7 3
1 1 3 3 3 2 1

Example output:
1

Example input:
10 2
1 2 1 2 1 2 1 2 1 2

Example output:
8

Editorial:
First, let us solve the problem in O(kn2) time with a simple DP. Let dpi, j be the smallest cost of a partition of first j elements into i parts. Clearly, dpi, j = minj' < jdpi - 1, j' + cost(j', j). We can optimize the cost computation by moving j' from right to left and maintaining frequency for each element, since by introducing an element x into the segment, we increase the cost by fx – the number of occurences of x.
To optimize this further, let us note that p(j) – the (leftmost) optimal value of j' for a particular j is monotonous in j on any step i. Indeed, suppose that j1 < j2, and dpi - 1, x + cost(x, j2) < dpi - 1, p(j1) + cost(p(j1), j2) for x < p(j1). But cost(x, j2) - cost(p(j1), j2) ≥ cost(x, j1) - cost(p(j1), j1), since introducing an element into a segment [l, j2] is at least as costly as introducing it into a segment [l, j1]. Finally, dpi - 1, p(j1) - dpi - 1, x > cost(x, j2) - cost(p(j1), j2) ≥ cost(x, j1) - cost(p(j1), j1), and dpi - 1, p(j1) + cost(p(j1), j1) > dpi - 1, x + cost(x, j1), which contradicts the optimality of p(j1).
We can now apply the "divide-and-conquer" DP optimization: suppose that for a segment [l, r] we know that $$p(j) \in [L, R]$$ for each $$j \in [l,r]$$. Choose m as the midpoint of [l, r] and find p(m) by explicitly trying all values in [L, R]. We now proceed recursively into segments [l, m - 1] with $$p(j) \in [L, M]$$, and [m + 1, r] with $$p(j) \in [M, R]$$. Assuming unit cost for cost(l, r) computation, one can show that the computation of all values of dpi, j for a particular i takes $$O(n \log n)$$ time.
The final detail is that the time needed to compute cost(l, r) can be made amortized constant (that is, $$O(n \log n)$$ in total per layer) if we store the value cost(p(m), m) from the parent segment, and add/remove segment elements one by one to obtain all subsequent values. The total complexity is now $${\mathcal {O}}(kn\log n)$$.