3. Obojstranná čokotuba vzorové riešenie

6 2 3
1 2 2 1 3 2
1 1
3 2

4

5 1 3
1 2 2 3 1
1 2

2

Iba jedna strana

Pozrime sa, ako by sa úloha zmenila, keby sme mohli brať čokolády iba zľava. Skúsme všetky možnosti a pre každú overme, či vyhovuje. Najskôr teda overíme, či nám stačí zobrať iba prvú čokoládu. Potom skúsime zobrať prvú a druhú, potom skúsime prvú, druhú a tretiu… Z vyhovujúcich možností zoberieme tú najkratšiu. Ako ale zistiť, či možnosť vyhovuje?

Pre každú testovanú možnosť si zrátame, koľko čokolád ktorej farby obsahuje. Majme pole \(p\) veľkosti \(f\) so samými nulami. Číslo \(p_i\) nám hovorí, koľko čokolád farby \(i\) momentálne máme. Ak zoberieme čokoládu farby \(u\), tak ku \(p_u\) pripočítame \(1\). Keď si teda napočítame čokolády v testovanom úseku, môžeme prejsť všetky požiadavky a pre každú požiadavku overiť, či je splnená. Takéto riešenie jednoduchšej úlohy bude fungovať v čase \(O(n(n + m + f))\), pretože pre každú z \(n\) možností prejdeme nanajvýš \(n\) políčok, vynulujeme pole \(p\) veľkosti \(f\) a prejdeme všetkých \(m\) požiadaviek.

Iba jedna strana, rýchlejšie

V pôvodnom riešení sme veľa vecí robili zbytočne. Napríklad, ak sme už poznali počty čokolád v úseku \([1,\,x]\) a chceli sme zistiť počty čokolád v úseku \([1,\,x+1]\), nemuseli sme nulovať celé pole \(p\). Úplne nám stačí pridať do poľa \(p\) čokoládu na pozícií \(x+1\). Všetky ostatné čokolády totiž budú tie isté, ako v starom úseku. Ku \(p_{c_{x+1}}\) teda iba pripočítame \(1\). Teraz, keď nezahadzujeme informácie zo skúmania predchádzajúcej možnosti, vieme každú novú možnosť spracovať v \(O(m)\). Možností je stále \(n\), takže časová zložitosť je \(O(f + nm)\). Stále totiž pre každú možnosť prechádzame cez všetky požiadavky. Pole \(p\) však nastavujeme už iba raz.

Iba jedna strana, ešte rýchlejšie

Asi je celkom očividné, že slabou časťou nášho doterajšieho riešenia je to, že pre každú možnosť prechádzame všetky požiadavky, aby sme overili, či sú splnené. Ako to zlepšiť?

Vieme, že keď sme ešte nezobrali žiadnu čokoládu, tak nie je splnená žiadna požiadavka. Majme teda počítadlo \(nesplnene\), ktoré bude hovoriť, koľko máme ešte nesplnených požiadaviek. Na začiatku, je samozrejme nastavené na \(m\). Postupne pridávame čokolády, až niekedy nastane zaujímavá udalosť. Pridaním čokolády farby \(w\) sa nám mohol zvýšiť počet týchto čokolád na minimálnu hranicu požadovanú Samom a Janom. To znamená, že požiadavka na čokolády farby \(w\) doteraz nebola splnená, ale teraz už splnená je. Môžeme teda od \(nesplnene\) odčítať \(1\).

Keď niekedy \(nesplnene\) dosiahne hodnotu \(0\), vieme, že už sú všetky požiadavky splnené. Nemusíme teda už ani skúšať brať ďalšie čokolády. Určite by sme tým už nenašli lepšie riešenie, ako máme teraz.

Ako ale zistiť, že nejaká požiadavka doteraz nebola splnená a teraz už je? Na začiatku si spravíme pole \(t\) veľkosti \(f\), ktoré nám pre každú farbu povie, koľko jej je žiadanej. To vieme spraviť už počas načítavania požiadaviek. Potom s týmito hodnotami vieme porovnávať hodnoty z poľa \(p\). Ak doteraz platilo, že \(p_i < t_i\) a zobratím nejakej čokolády farby \(i\) začalo platiť, že \(p_i = t_i\), tak požiadavka na farbu \(i\) je už splnená. Časová zložitosť teda bude \(O(n + m + f)\).

Dve strany, hrubá sila

Jednoduchým riešením pôvodnej úlohy je vyskúšať všetky možnosti pre zobratie prefixu a suffixu a každú takúto možnosť overiť. Podľa toho, ako dobre spravíme overovanie môže mať toto riešenie časovú zložitosť zhruba niekde medzi \(O(n^2)\) a \(O(n^3)\). Rôzne spôsoby overovania sme si popísali vyššie.

Dve strany, vzorové riešenie

Poďme sa ale pozrieť, ako môžeme riešenie úlohy, kde berieme čokolády iba zľava rozšíriť na obojstrannú verziu.

V jednoduchšej úlohe sme spravili pozorovanie, že ak vieme splniť požiadavky najľavejšími \(x\) čokoládami, tak už nemusíme skúšať brať ďalšie, pretože by sme tým určite nezískali lepšie riešenie. Ako toto pozorovanie využiť? Nuž, skúsme nezobrať žiadne čokolády sprava. Zľava teraz zoberieme iba toľko čokolád, koľko nám stačí na splnenie všetkých požiadaviek. Máme teda nejaké riešenie. Možno je najlepšie, možno nie, no určite spĺňa všetky požiadavky. No dobre, zľava už určite nechceme zobrať viac čokolád.

Čo ale sprava? Čo sa môže stať, keď zoberieme naviac ešte jednu čokoládu sprava? Ak to bola čokoláda, ktorej farba sa nijak nevyskytuje v požiadavkách, tak nič neriešime. Zhoršili sme si síce doterajšie riešenie, ale to nás nijak netrápi, pretože výsledok lepšieho riešenia si pamätáme ako doteraz najlepšie nájdené. Čo sa ale stane, ak sa farba najpravejšej čokolády nachádza niekde v požiadavkách na vyváženú stravu? Znamená to, že možno môžeme na ľavú stranu vrátiť čokoládu, ktorú sme odtiaľ zobrali ako poslednú. Môžeme ju vrátiť, ak má rovnakú farbu, ako tá, ktorú sme teraz zobrali sprava. No a aby sme sa z ľavej strany dostali k čokoláde, ktorú sme tam teraz vrátili, museli sme možno prejsť cez nejaké čokolády, ktoré sme vôbec nechceli. Môžeme tam teda vrátiť aj tie. A ľaľa, možno sme práve našli nové najlepšie riešenie.

Pozrime sa na to naopak. Máme riešenie, ktoré berie čokolády iba zľava. Vieme, že všetky požiadavky sú splnené. Skúsme vrátiť čokoládu, ktorú sme zobrali ako poslednú. Tým možno prestala byť splnená nejaká požiadavka. To znamená, že teraz budeme brať čokolády sprava, až kým neopravíme túto pokazenú požiadavku. Tento postup teda začne s riešením, ktoré berie iba čokolády zľava a opakuje dva jednoduché kroky:

1. Vráť na ľavú stranu čokoládu, ktorú si odtiaľ zobral ako poslednú
2. Ber čokolády sprava, kým opäť nie sú splnené všetky požiadavky

Môžeme si všimnúť, že niekedy nám vrátenie čokolády na ľavú stranu žiadnu požiadavku nepokazí. Vtedy teda nemusíme brať žiadne ďalšie čokolády sprava.

Akú to má celé časovú zložitosť? Najskôr nájdeme nejaké riešenie, ktoré berie čokolády iba zľava. To už vieme v \(O(n + m + f)\). Potom vždy vrátime jednu čokoládu na ľavú stranu a zoberieme niekoľko, možno aj 0, čokolád sprava. Každú čokoládu teda najviac raz zoberieme a najviac raz vrátime. Bude to teda celé v \(O(n + m + f)\). Vieme ale, že \(m\) ani \(f\) nikdy nebudú väčšie, ako \(n\). Môžeme teda povedať, že časová zložitosť je \(O(n)\).

Pamäťová vyzerá ako \(O(n + m + f)\). Požiadavky si ale nemusíme pamätať ako zoznam, takže sa dostávame na \(O(n + f)\) a stále platí, že \(f \leq n\), takže aj o pamäti môžeme povedať, že je \(O(n)\).