V tejto úlohe zisťujeme, koľko najmenej peňazí v daniach musí zaplatiť úbohý sedliak Matej. Každý deň k nemu príde vyberač daní, ktorý zisťuje prítomnosť kvalít od 0 vyššie a daň je rovná prvej kvalite, ktorú nenašiel. Potom sa sedliak jednej kravy zbaví. Ak mu neostanú žiadne kravy alebo kravy kvality 0, zjavne už nebude platiť dane. Hodnotu prvej chýbajúcej kvality budeme štandardne volať MEX (Minimum Excluded value). Naším cieľom je odstraňovať kravy tak, aby sme sumu hodnôt MEX za všetky dni minimalizovali.

Bruteforce

Najjednoduchší a zároveň najpomalší spôsob, ako túto úlohu vyriešiť, je vygenerovať všetky možné poradia, v akých sa môžeme kráv zbavovať. Keďže máme na vstupe $n$ kráv, existuje $n!$ rôznych poradí (permutácií), ako ich môžeme postupne odstraňovať. Pre každú permutáciu by sme prešli všetky dni, v každom dni by sme našli aktuálny MEX (čo trvá $O(n)$) a pripočítali ho k celkovej dani. Tento prístup by mal časovú zložitosť $O(n! \cdot n)$. Pre maximálny počet kráv $1 \leq n \leq 2\,001$ na vstupe by toto riešenie neprešlo v časovom limite pravdepodobne na žiadnej sade.

Niečo lepšie

Skúsme sa na problém pozrieť inak. Všimnime si, že keď odstránime kravu, hodnota MEX sa môže buď zmenšiť, alebo ostať rovnaká. Nikdy sa nemôže zväčšiť. Čo ak by sme si skúsili pamätať všetky možné podmnožiny kráv, ktoré nám ešte mohli ostať? Keďže máme $n$ kráv, existuje $2^n$ takýchto podmnožín. Mohli by sme použiť dynamické programovanie napríklad za pomoci bitmasiek, kde by stav bol určený tým, ktoré kravy ešte žijú, a prechod by bol odstránenie jednej z nich. Zložitosť tohto riešenia by bola $O(2^n \cdot n)$. Zlepšili sme sa, ale pre limit $n \leq 2\,001$ zadaný pre všetky štyri sady je to stále priveľa.

Zaujímavá myšlienka

Zamerajme sa na samotnú hodnotu MEX. Ak je aktuálny MEX rovný $M$, znamená to, že v našom stáde máme aspoň jednu kravu z každej kvality od $0$ po $M-1$. Aby sa daň, ktorú platíme, znížila na nejakú menšiu hodnotu $x$ ($x < M$), musíme urobiť jedinú vec: zbaviť sa všetkých kráv, ktoré majú kvalitu $x$. Kým sa nezbavíme poslednej z nich, $x$ bude stále v našom stáde prítomné a MEX klesnúť pod $x$ nemôže.

Ak máme $C_x$ kráv s kvalitou $x$, proces ich odstraňovania nám zaberie presne $C_x$ dní. Počas týchto $C_x$ dní sa naša daň nezníži pod $M$ (pretože $x$ tam stále je a všetky menšie čísla tiež). Každý z týchto dní teda zaplatíme daň $M$. Za odstránenie všetkých kráv kvality $x$ zaplatíme dokopy $M \times C_x$ peňazí a nová daň na ďalší deň klesne presne na hodnotu $x$. Kravy, ktoré majú kvalitu väčšiu ako počiatočný MEX, nás vôbec nezaujímajú – nikdy neovplyvnia hodnotu MEX, a preto ich môžeme odstraňovať, až keď bude daň $0$.

Optimálne riešenie

Vyššie spomenutá myšlienka nás priamo navádza na dynamické programovanie. Naším stavom bude aktuálna hodnota MEX. Chceme zistiť najmenšiu celkovú daň, ktorú musíme zaplatiť, aby sme sa postupným odstraňovaním vybraných kráv dostali do stavu, kedy je MEX rovný $0$.

Označme si $DP[i]$ ako minimálnu daň, ktorú nahromadíme počas procesu znižovania z počiatočného MEX na aktuálny MEX s hodnotou $i$. Základom je zistenie počiatočného MEX celého stáda, označme ho $M$. V tomto štartovacom bode uvažujeme zaplatenú sumu $DP[M] = 0$.

Z ľubovoľného stavu $i$ sa vieme dostať do nového stavu $j$ (kde $j < i$) tým, že obetujeme dni na odstránenie úplne všetkých kráv s kvalitou $j$. Ak počet kráv s kvalitou $j$ v pôvodnom stáde označíme $C_j$, proces ich odstraňovania nás bude stáť presne $i \times C_j$ dukátov, pretože počas týchto dní sa vyberá daň $i$. Preto môžeme hodnotu pre každý menší cieľový stav $j$ optimalizovať pomocou prechodu: $$DP[j] = \min(DP[j], DP[i] + i \times C_j)$$

Výsledná minimálna suma potrebná na to, aby sme už neplatili žiadne dane, bude logicky predstavovať finálnu hodnotu $DP[0]$.

Keďže celkový počet kráv $n$ neprekročí $2\,001$, počiatočný MEX $M$ nikdy neprekročí $n$. Počet možných stavov v našom dynamickom programovaní je tak lineárne závislý od počtu kráv. Z každého stavu vyhodnocujeme prechody do všetkých menších stavov, z čoho nám vyplýva celková časová zložitosť $O(n^2)$. Táto zložitosť je vzhľadom na maximálnu veľkosť $n \leq 2\,001$ dostatočne dobrá a riešenie získa plný počet bodov aj pre sadu 4, kde môžu kvality kráv nadobúdať hodnoty až $10^9$ (stačí uvážiť, že kravy s kvalitou ostro väčšou ako $n$ nikdy neovplyvnia hodnotu MEX keďže ak ich máme tak to znamená že jedno z čísiel 0 až $n$ musí chýbať, a preto ich kvalitu pre optimalizáciu zvažovať nemusíme). Pamäťová zložitosť je $O(n)$, keďže si potrebujeme pamätať len počty kráv jednotlivých kvalít a naše DP pole.

input()
pole = [int(i) for i in input().split()]
poc_pole = []
pole.sort()
i = 0
cislo = -1

while i < len(pole) and pole[i] == cislo+1:
    cislo += 1
    poc_pole.append(0)
    while i < len(pole) and pole[i] == cislo:
        poc_pole[-1] += 1
        i += 1

dynamic = [float('inf')]*(len(poc_pole))
dynamic.append(0)

for i in range(len(dynamic)-2, -1, -1):
    for j in range(i+1, len(dynamic)): dynamic[i] = min(dynamic[i], poc_pole[i]*j + dynamic[j])

print(dynamic[0])

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

int main() 
{
    long long n;
    cin >> n;

    vector<long long> kvalita(n + 1, 0);

    for (long long i = 0; i < n; i++)
    {
        long long k;
        cin >> k;

        if (k < kvalita.size()) kvalita[k]++;
    }

    long long m = 0;
    while (m < kvalita.size() && kvalita[m] != 0) m++;

    vector<long long> dp(kvalita.size(), 0);
    for (long long i = m - 1; i >= 0; i--)
    {
        dp[i] = m * kvalita[i];
        for (long long j = m - 1; j > i; j--)
        {
            dp[i] = min(dp[i], dp[j] + j * kvalita[i]);
        }
    }

    cout << dp[0] << '\n';
    return 0;
}