3. Hurá leto! vzorové riešenie

3
0 1 2

1

4
2 2 2 2

2

Toto vzorové riešenie má dve časti. V prvej časti sa pozrieme, ako má Žaba ukladať škatule, aby vytvoril čo najmenej kôp. V druhej časti budeme riešiť, ako toto uloženie efektívne vypočítať.

Mohli by sme sa do toho pustiť intuitívne. Postavíme si najsilnejšiu škatuľu a začneme na ňu ukladať ostatné škatule. Tento prístup má ale svoje problémy. Napríklad, ak máme ďalšiu, rovnako pevnú škatuľu, nevieme, či ju máme položiť na tú prvú, alebo si ju máme šetriť do ďalšej kopy. Konkrétny príklad: ak máme iba dve škatule s pevnosťou \(1\), oplatí sa ich postaviť na seba. Na druhú stranu, ak máme navyše ešte dve škatule s pevnosťou \(0\), viac sa nám oplatí “jednotkové” škatule rozdeliť.

Austrália

Skúsme sa na to teda pozrieť opačne. Stavajme kopy “odvrchu”. Novú kopu začneme jej najslabšou škatuľou. Ďalej budeme pridávať čoraz silnejšie škatule, vždy na spodok kopy.

Teraz už k samotnému ukladaniu škatúľ. Berme škatule od najslabšej po najpevnejšiu a ukladajme ich do kôp. Vždy, keď ukladáme nejakú škatuľu, musíme sa rozhodnúť, či ňou začneme novú kopu, alebo ju pridáme pod nejakú už existujúcu. Ak sme sa rozhodli pridať škatuľu pod niektorú z už existujúcich kôp, musíme si navyše vybrať pod ktorú. Prirodzene sa nám núka položiť škatuľu pod najväčšiu kopu, ktorú je ešte schopná uniesť, aby sme “neplytvali pevnosťou”. Pokiaľ naša škatuľa nie je schopná uniesť žiadnu z existujúcich kôp, začneme novú kopu. Takýmto spôsobom vieme rozdeliť všetky škatule do niekoľkých kôp. Dostaneme ale zaručene najmenší možný počet kôp?

Zdôvodnenie správnosti

Treba si uvedomiť, že môže existovať viacero spôsobov, ako škatule rozdeliť na najmenší možný počet kôp. Tieto spôsoby budeme ďalej volať optimálne riešenia. My chceme ukázať, že náš postup rozdelí škatule jedným z nich. Nato si ukážeme, že po každej pridanej škatuli v našom postupe je ešte možné doplniť ostatné škatule tak, aby sme dostali jedno z optimálnych riešení. Ak toto bude platiť aj po pridaní poslednej škatule, znamená to, že sme vytvorili optimálne riešenie.

Predpokladajme, že sme už umiestnili prvých \(k\) škatúľ a ešte stále je možné doplniť ostatné škatule tak, aby vzniklo optimálne riešenie. Škatuľu, ktorú by náš algoritmus umiestnil ako ďalšiu (teda \(k+1\)-vú najslabšiu škatuľu) označme \(X\) a miesto, kam by ju dal, označme \(m\). Doplňme ostatné škatule tak, aby vzniklo optimálne riešenie a pozrime sa, kde v ňom je škatuľa \(X\). Ak náš algoritmus nechcel škatuľou \(X\) začať novú kopu, môžu nastať 3 prípady:

1. Škatuľa \(X\) sa nachádza na mieste \(m\).

2. Škatuľa \(X\) je niekde inde a na mieste \(m\) sa nachádza nejaká iná škatuľa \(Y\). Vieme, že všetky škatule slabšie než \(X\) sú umiestnené tam, kam ich dal náš algoritmus. To znamená, že škatuľa \(Y\) nemôže byť jedna z nich, a teda musí byť aspoň tak pevná, ako škatuľa \(X\). Ak teraz vymeníme škatule \(X\) a \(Y\), škatuľa \(Y\) určite bude schopná niesť záťaž, ktorú predtým niesla škatuľa \(X\). Škatuľa \(X\) sa tým ocitne na mieste \(m\), kam ju chcel dať aj náš algoritmus, a teda tiež určite unesie svoj náklad. Takto sme dostali iné riešenie Žabovej úlohy, ktoré je tiež optimálne (má rovnako veľa kôp) a navyše má škatuľu \(X\) na mieste \(m\).

3. Škatuľa \(X\) je inde ako na mieste \(m\) a miesto \(m\) je prázdne. V takom prípade môžeme škatuľu \(X\) preniesť na miesto \(m\). Škatuľa \(X\) svoj nový náklad určite unesie, rovnako aj všetky ostatné škatule (škatuliam, ktoré boli pod \(X\) sa náklad odľahčil o škatuľu \(X\), ostatným sa nezmenil). Opäť sme dostali optimálne riešenie, kde je škatuľa \(X\) na mieste \(m\).

Ak náš algoritmus chcel škatuľou \(X\) začať novú kopu, znamená to, že by neuniesla žiadnu z kôp, ktoré existovali po umiestnení prvých \(k\) škatúľ. Aj v optimálnom riešení preto \(X\) musí byť v nejakej inej kope. Za miesto \(m\) teraz budeme považovať vrch kopy obsahujúcej škatuľu \(X\). Ak je \(X\) navrchu tejto kopy, situácia je rovnaká ako v prípade 1, ak nie je navrchu, situácia je rovnaká ako v prípade 2.

V každom prípade existuje optimálne riešenie, v ktorom je škatuľa \(X\) na mieste \(m\), teda aj keby sme nechali náš algoritmus umiestniť prvých \(k+1\) škatúľ, zvyšné škatule by sa určite dali doplniť do optimálneho riešenia.

Ak našu predošlú úvahu urobíme pre \(k=0\), dostávame, že prvú škatuľu náš algoritmus umiestni dobre, t.j. bude možné doplniť zvyšné škatule do optimálneho riešenia. Zopakovaním úvahy pre \(k=1\) dostávame, že aj druhú škatuľu náš algoritmus umiestni dobre. Úvahu postupne zopakujeme pre \(k = 2, 3, \dots, n-1\) a dostaneme, že aj keď necháme náš algoritmus umiestniť všetkých \(n\) škatúľ, bude možné doplniť zvyšných \(0\) škatúľ do optimálneho riešenia¹. To ale znamená, že náš algoritmus vytvoril optimálne riešenie.

Implementácia

Ukázali sme si algoritmus, ktorým Žaba môže ukladať škatule. Teraz ešte napísať program, ktorý to odsimuluje.

Jedno z pozorovaní, ktoré nám pomôžu pri implementácii je, že ono si nám vlastne netreba pamätať, čo v kope je, stačí nám vedieť veľkosť kopy. Prečo? Keď škatule vkladáme na spodok kopy, potrebujeme iba skontrolovať, či počet vecí na tejto kope nie je väčší, než pevnosť škatule. Toto nám o dosť zjednoduší programovanie nášho riešenia.

def pocet_kopok(skatule, n):
    kopky = [0] * n
    for sila in skatule:
        for i in range(n):
            if sila >= kopky[i]:
                kopky[i] += 1
                break
    # zoberieme len tie kôpky, ktoré sme použili
    return len(kopky) - kopky.count(0)

Ako vidíme, skutočne len pre každú škatuľu prechádzame všetky potenciálne kôpky a uložíme to na prvú, na ktorú má naša aktuálna škatuľa dosť pevnosti. Toto riešenie má ale časovú zložitosť \(O(n^2)\). Zoberme si napríklad, že všetky škatule čo dostaneme, by boli z papundekla, teda pevnosti 0. Pre každú škatuľu musíme prejsť všetky doteraz urobené kôpky a vyrobiť si novú.

Optimalizácia

Ďalšie z našej série pozorovaní je, že vyššie uvedený algoritmus má vedľajší efekt. V každom kroku nášho algoritmu sú všetky kôpky zoradené zostupne, podľa veľkosti! Ako správny KSP-áci toto predsa hneď musíme zneužiť. Čo vieme robiť na zoradenom poli? No predsa binárne vyhľadávanie!

Medzi zoradenými kôpkami teda vieme pomocou binárneho vyhľadávania, v čase \(O(\log n)\), nájsť našu ideálnu kôpku pre aktuálnu škatuľu. Toto nám zlepší celkovú časovú zložitosť na \(O(n \log n)\).

def pocet_kopok(skatule, n):
    kopky = [0] * n
    for sila in skatule:
        vhodna_kopka = bin_najdi_kopku(kopky, n, sila)
        kopky[vhodna_kopka] += 1
    return len(kopky) - kopky.count(0)

Implementovanie samotnej funkcie bin_najdi_kopku nechávame ako cvičenie pre čítateľa.

Viac optimalizácií

Keď sa trochu zamyslíme nad vyššie spomínanou optimalizáciou, zistíme, že my vlastne vôbec nemusíme binárne vyhľadávať v takomto poli kôpok.

Predpokladajme, že prvých zopár škatúľ už máme nejako rozostavaných a teraz ideme umiestniť skupinu škatúľ s rovnakou pevnosťou. Kam by ich dal náš \(O(n \log n)\) algoritmus? Najskôr by ich dával pod prvú kôpku, ktorú sú schopné udržať. Následne by pokladal ďaľšie škatule pod túto istú kôpku, až dokedy by nebola príliš veľká pre našu silu škatúľ. Pokiaľ je už aktuálna kôpka príliš veľká, posunieme sa na ďaľšiu. Ďaľšia kôpka je zaručene dostatočne malá na to, aby sme pod ňu mohli umiestniť aspoň jednu škatuľu.

Keď prechádzame na škatule s väčšou pevnosťou, tieto pevnejšie škatule sú určite schopné uniesť všetky existujúce kopy. Má teda zmysel sa po tomto prechode vrátiť opäť na prvú kôpku a postup opakovať, teraz už ale so silnejšími škatuľami.

Tento algoritmus má časovú zložitosť \(O(n)\), keďže pre každú škatuľu nájdeme príslušnú kopu v konštantnom čase. Všetky doteraz spomínané riešenia majú pamätovú zložitosť \(O(n)\), pretože si potrebujeme pamätať iba dve polia dĺžky najviac \(n\): pevnosti škatúľ a veľkosti kôp.

def skatule_sily(skatule):
    """
    Zo síl zo vstupu vráti dvojice (sila, pocet).
    """
    posledna_sila = skatule[0]
    pocet = 0
    pocty_sil = []
    for sila in skatule:
        if sila == posledna_sila:
            pocet += 1
        else:
            pocty_sil.append([posledna_sila, pocet])
            posledna_sila = sila
            pocet = 1
    pocty_sil.append([posledna_sila, pocet])
    return pocty_sil


def pocet_kopok(skatule, n):
    sily = skatule_sily(skatule)
    kopky = [0] * n
    for sila, pocet in sily:
        aktualna_kopka = 0
        while pocet > 0:
            while sila >= kopky[aktualna_kopka] and pocet > 0:
                kopky[aktualna_kopka] += 1
                pocet -= 1
            aktualna_kopka += 1
    return len(kopky) - kopky.count(0)


n = int(input())
krabice = list(map(int, input().split()))
print(pocet_kopok(krabice, n))

Toto je naše optimálne riešenie a dostaneme zaň pekných 8 bodov.

Poznámka: Pochopiteľne, konverzia, ktorú funkcia skatule_sily vykonáva nie je vôbec potrebná ku korektnej funkčnosti nášho algoritmu. Tento upravený formát vstupu nám iba umožňuje mať prehľadnejší kód v pocet_kopok.

Exotika

Náš miestny zelovocár s exotickými riešeniami vymyslel aj riešenie, ktoré má časovú zložitosť \(O(n)\) a pamäťovú \(O(1)\). Funguje na trochu inom príncípe ako všetky naše riešenia, ktoré sú konštruktívne - snažia sa škatule naozaj rozdeliť na kopy. Toto riešenie je nekonštruktívne. Pre každú škatuľu na základe jej pevnosti a počtu slabších škatúľ vypočíta dolný odhad na počet všetkých kôp. Nájsť toto riešenie je pekným cvičením pre trochu skúsenejších riešiteľov.