Yet Another Minimization Problem (Codeforces 868F)
Tags: DP, divide and conquer

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: 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: Print single integer: the minimum possible total cost of resulting subsegments.

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.

Sample Inputs:
7 3
1 1 3 3 3 2 1

10 2
1 2 1 2 1 2 1 2 1 2

13 3
1 2 2 2 1 2 1 1 1 2 2 1 1

Sample Outputs:
1

8

9

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
buc = [0] * (n + 1)
dp_p = [n * (n - 1) // 2] * (n + 1)
dp_c = [0] * (n + 1)
dp_p[0] = 0
buc[a[1]] = 1
L = R = 1
ans = 0

def cal(l, r):
    global L, R, ans
    while L < l:
        ans += 1 - buc[a[L]]
        buc[a[L]] -= 1
        L += 1
    while L > l:
        L -= 1
        ans += buc[a[L]]
        buc[a[L]] += 1
    while R < r:
        R += 1
        ans += buc[a[R]]
        buc[a[R]] += 1
    while R > r:
        ans += 1 - buc[a[R]]
        buc[a[R]] -= 1
        R -= 1

def solve(lb, rb, l, r):
    global ans, L
    if lb > rb or l > r:
        return
    mid = (l + r) // 2
    d = 0
    res = 9223372036854775807
    cal(lb, mid)
    for i in range(lb, rb + 1):
        ans += 1 - buc[a[L]]
        buc[a[L]] -= 1
        L += 1
        if res > dp_p[i] + ans:
            res = dp_p[i] + ans
            d = i
    dp_c[mid] = res
    solve(lb, d, l, mid - 1)
    solve(d, rb, mid + 1, r)
for cur in range(1, m + 1):
    solve(0, n - 1, 1, n)
    (dp_p, dp_c) = (dp_c, dp_p)
print(dp_p[n])

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
buc = [0] * (n + 1)
dp_p = [n * (n - 1) // 2] * (n + 1)
dp_c = [0] * (n + 1)
dp_p[0] = 0
buc[a[1]] = 1
L = R = 1
ans = 0

def cal(l, r):
    global L, R, ans
    while L < l:
        ans += 1 - buc[a[L]]
        buc[a[L]] -= 1
        L += 1
    while L > l:
        L -= 1
        ans += buc[a[L]]
        buc[a[L]] += 1
    while R < r:
        R += 1
        ans += buc[a[R]]
        buc[a[R]] += 1
    while R > r:
        ans += 1 - buc[a[R]]
        buc[a[R]] -= 1
        R -= 1

def solve(lb, rb, l, r):
    global ans, L
    if lb > rb or l > r:
        return
    mid = (l + r) // 2
    d = 0
    res = 9223372036854775807
    cal(lb, mid)
    for i in range(lb, rb + 1):
        ans += 1 - buc[a[L]]
        buc[a[L]] -= 1
        L += 1
        if res > dp_p[i] + ans:
            res = dp_p[i] + ans
            d = i
    dp_c[mid] = res
    solve(lb, d, l, mid - 1)
    solve(d, rb, mid + 1, r)
for cur in range(1, m + 1):
    solve(0, n - 1, 1, n)
    (dp_p, dp_c) = (dp_c, dp_p)
print(dp_p[n])

Solution (Python):
from io import BytesIO, IOBase
import random
import sys
import os
import bisect
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(n, k) = MII()
nums = LII()
counts = [0] * (n + 1)
dp = [0] * n
curr = 0
for i in range(n):
    curr += counts[nums[i]]
    counts[nums[i]] += 1
    dp[i] = curr
for _ in range(k - 1):
    new_dp = [inf] * n
    new_dp[0] = 0
    froms = [None] * (n + 1)
    froms[0] = 0
    froms[n] = n
    seps = [0, n]
    while len(seps) != n + 1:
        new_seps = []
        counts = [0] * (n + 1)
        (l, r) = (0, 0)
        curr = 0
        for i in range(len(seps) - 1):
            new_seps.append(seps[i])
            mid = (seps[i] + seps[i + 1]) // 2
            if froms[mid] is None:
                new_seps.append(mid)
                while r <= mid:
                    curr += counts[nums[r]]
                    counts[nums[r]] += 1
                    r += 1
                maxi = min(froms[seps[i + 1]] + 1, mid)
                while l < maxi:
                    if l and dp[l - 1] + curr < new_dp[mid]:
                        new_dp[mid] = dp[l - 1] + curr
                        froms[mid] = l - 1
                    counts[nums[l]] -= 1
                    curr -= counts[nums[l]]
                    l += 1
                if l and dp[l - 1] + curr < new_dp[mid]:
                    new_dp[mid] = dp[l - 1] + curr
                    froms[mid] = l - 1
        new_seps.append(n)
        seps = new_seps
    dp = new_dp
print(dp[-1])