Táto úloha je teoretická. Ako svoje riešenie odovzdaj PDF súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil/a chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.
Ak máš hocijaké otázky k tejto úlohe, napíš Alici ([email protected]) alebo Štepimu ([email protected]).
Domorodci boli Miške veľmi vďační za pomoc s delením jedla, rozhodli sa jej preto venovať kopu suvenírov. Miška ale zistila, že na ne budú potrebovať nový batoh.
Suveníry, ktoré si chce zobrať, zaberajú isté množstvo priestoru a každý z batohov má taktiež svoj maximálny objem vecí, ktoré sa doň zmestia. Najlepšia možná batožina je taká, ktorá odnesie všetky suveníry od domorodcov a zároveň v nej zostane čo najmenej nevyužitého priestoru. Miška so Štepim majú na výber niekoľko batohov v rade. Ich presné veľkosti nevedia, ale vedia, že sú zoradené od najmenšieho po najväčší.
Pri hľadaní vhodného batohu vedia v jednom kroku naplniť vecami jeden batoh. Ak sa tam všetky veci nezmestia, tak im ostane ten zvyšok. Takto teda zistia, že im niečo zostalo, ale nevedia, koľko toho presne je. Zvyšok suvenírov ďalej môžu skúsiť dať do iných batohov bez toho, aby vyberali veci z plného batohu.
Predstavme si, že by Štepi a Miška mali dva batohy s veľkosťami $3$ a $10$ a k tomu $8$ vecí (vecí, ktoré dokopy zaberajú $8$ jednotiek priestoru). Potom ich môžu skúsiť dať do menšieho batohu, ale tam sa všetky nezmestia, ostane im $5$ vecí. Tak môžu týchto $5$ vecí skúsiť dať do väčšieho batohu, kde by sa už zmestili. Potom môžu napríklad vyprázdniť menší batoh a odložiť si tie veci na nejakú kôpku, a ďalej vybrať tých $5$ vecí z väčšieho batohu a skúsiť nimi naplniť ten menší. V menšom batohu teda budú $3$ veci a vo väčšom ostanú $2$.
Miška a Štepi ale tieto čísla nepoznajú, takže vedia len, že po tom, čo urobia tieto kroky, majú kôpku takej veľkosti, ako je ten menší batoh, potom ešte raz plný menší batoh a ešte nejaké veci vo väčšom batohu, menej ako je jeho kapacita, ale nevedia koľko presne.
Tento príklad nesúvisí s riešením úlohy, je tu len na to, aby ste si vedeli lepšie predstaviť, čo sa dá s batohmi a vecami robiť.
a. (30 bodov) Ak majú Štepi s Miškou vybrať jeden batoh pre všetky suveníry, ako vedia vybrať taký, ktorý bude najlepšie spĺňať podmienky? Mohli by zaradom prejsť všetky batohy, ale to by trvalo príliš dlho. Chcú si užiť čo najviac času v pralesoch s domorodcami, preto by mali použiť čo najmenej krokov.
b. (70 bodov) Po dlhej výprave ich však už bolia chrbty a výhodnejšie by bolo rozdeliť suveníry medzi Miškou a Štepim do dvoch batohov. Suveníry aj objem, ktorý zaberajú, sa môžu akokoľvek rozdeliť na dve časti. V tejto podúlohe môžete navyše predpokladať, že žiadny batoh nie je väčší ako všetky suveníry dokopy.
Ak majú vybrať dva batohy pre dve kôpky suvenírov, ako vedia vybrať tú najlepšiu dvojicu? Tiež nechcú skúšať každú dvojicu batohov osobitne.
Najprv chceme použiť iba jeden batoh. To znamená, že zo všetkých batohov, do ktorých sa naše veci zmestia, chceme zobrať ten najmenší. Vieme overiť, či sa do nejakého batohu všetky veci zmestia alebo nie – dáme ich tam a uvidíme, či nám nejaké ostanú. Chceme si teda rozmyslieť, ktoré batohy chceme skúšať, aby sme čo najrýchlejšie našli ten, ktorý chceme.
Predstavme si, že vyskúšame nejaký batoh a zistíme, že je príliš veľký. Potom určite nebudeme chcieť žiadny z tých väčších. Keďže batohy sú usporiadané podľa veľkosti, nemusíme teda skúšať tie napravo od neho. Podobne keď nájdeme príliš malý batoh, tak nemusíme skúšať tie naľavo.
Najlepšie je teda vyskúšať vždy ten batoh, ktorý je práve v strede, a tým sa zbavíme polovice potenciálnych batohov, ktoré by sme mohli chcieť (buď tie naľavo, alebo tie napravo). Keby sme si vybrali nejaký iný, mohlo by sa stať, že sa zbavíme tej strany, kde je batohov menej, a teda nám ich ostane viac, čo je pre nás horšie.
Keď toto budeme opakovať, nakoniec nám ostane len jeden batoh, a to bude ten, ktorý hľadáme.
Môžeme sa ešte zamyslieť nad tým, koľko krokov nám toto bude trvať, podľa toho, koľko máme batohov. V každom kroku vylúčime polovicu batohov, teda ich počet vydelíme dvomi. Skončíme, keď nám ostáva len jeden batoh. Keď máme $n$ batohov, pýtame sa teda, koľkokrát musíme vydeliť $n$ dvomi, aby sme dostali $1$, alebo inými slovami, koľkokrát musíme vynásobiť $2$ (so sebou), aby sme dostali aspoň $n$.
Tomu sa hovorí logaritmus (so základom $2$, lebo násobíme dvojku), a píše sa to ako $\log_2 n$ (tá dvojka sa tam niekedy nepíše). Dôležité je, že logaritmus rastie veľmi pomaly, takže takýto prístup je veľmi rýchly aj pre veľmi veľa batohov. Napríklad aj keby batohov bolo milión, tak by nám stačilo asi $20$ takýchto pokusov.
Tomuto prístupu sa hovorí binárne vyhľadávanie a často sa používa pri programovaní, keď potrebujeme nájsť odpoveď na nejakú otázku a vieme efektívne zisťovať, či je nejaký konkrétny tip príliš málo alebo príliš veľa.
Predstavme si, že si vyberieme jeden z batohov, ktoré budú tvoriť našu dvojicu. Potom vieme ľahko nájsť druhý postupom z prvej úlohy. Jedno možné riešenie je teda napríklad vyskúšať každý možný prvý batoh a takto nájsť druhý. To nám zaberie približne $n\log n$ krokov.
To už je samo o sebe celkom dobré, ale existuje aj trochu lepšie riešenie, na ktoré nám bude stačiť približne $n$ krokov. Predstavme si, že vyskúšame úplne prvý batoh v rade ako ten prvý z dvojice, a k nemu nájdeme najlepší druhý batoh (napríklad tak ako v prvej podúlohe, ale kľudne aj menej efektívne, napríklad tak, že ich zaradom všetky pozeráme). Čo keby sme teraz namiesto toho prvého batohu zobrali ten napravo od neho? Keďže sú usporiadané podľa veľkosti, tak ten prvý z dvojice teraz bude väčší, takže ten druhý nám určite stačí menší. Môžeme teda zase zaradom pozerať, ktoré batohy vyhovujú, ale stačí sa nám pozerať od toho posledného.
Môžeme si to predstaviť ako takých dvoch bežcov: každý bežec je pri nejakom batohu, začínajú úplne vľavo a úplne vpravo. Ten ľavý sa potom postupne posúva doprava a vždy keď sa pohne, ten pravý ide doľava, kým môže. Takto pokračujú, až kým sa nestretnú niekde v strede. Pri každom kroku bežcov musíme zistiť, či sa veci do tých dvoch batohov zmestia, takže to nám zaberie jeden krok hádania (možno dva, ak bude krok neúspešný, teda zistíme, že do tých dvoch batohov sa už veci nezmestia). Dokopy ale bežci prejdú najviac $n$ krokov (od ľavého konca do miesta stretnutia a potom odtiaľ do pravého konca sú to akurát všetky batohy), takže takto nám aj na hľadanie batohu stačí približne $n$ krokov (možno až $2n$, ale to je stále rádovo rovnako).
Takýto prístup sa tiež občas používa pri programovaní a je známy pod názvom dvaja bežci.
K riešeniu druhej podúlohy nám ešte chýba dôležitá časť: pomocou jedného z tých algoritmov, ktoré sme tam popísali, nájdeme niekoľko dvojíc batohov, ktoré by mohli byť tie najlepšie, ale ako vieme, ktorá z nich to je? Chceli by sme zobrať takú, kde ostalo dokopy čo najmenej prázdneho miesta, ale my nevieme priamo zistiť, koľko prázdneho miesta tam je.
V prvej podúlohe sme to, ktorý batoh je správny, rozoznali tak, že sme skúsili dať veci do toho vedľa a tam sa už nezmestili, tak sme vedeli, že ten to nemôže byť, a teda ten, ktorý sme vybrali, je naozaj ten najlepší. Tu máme ale viac takých dvojíc, do ktorých sa všetky veci zmestia, ale niektoré majú viac zbytočného miesta naviac. Chceli by sme to nejak vedieť porovnať iba pomocou toho, že budeme premiestňovať veci medzi batohmi a zisťovať, kedy sa zmestia a kedy už nie.
Majme v rade batohy (nie nutne hneď za sebou), ktoré majú kapacity postupne $a\leq b\leq c\leq d$. Dajme tomu, že sme zistili, že dvojica $a + d$ aj $b + c$ môžu byť tie dobré (teda veci sa tam zmestia), a chceli by sme zistiť, ktorá z nich je lepšia (teda ktorá má menší súčet).
Zaujíma nás teda, či platí nerovnosť $a + d < b + c$, čo vieme upraviť na $d < b - a + c$. Inými slovami, pýtame sa, či sa $b - a + c$ vecí zmestí do batohu $d$. Ak by sme teda vedeli “odmerať” presne $b - a + c$ vecí, potom ich vieme skúsiť dať do batohu $d$ a uvidíme, či sa zmestia.
No ale to vieme. $b - a$ dostaneme tak, že dáme do batohu $b$ toľko vecí, koľko sa tam zmestí. Potom ich vyberieme a dáme z nich do $a$ toľko, koľko sa zmestí. Ten ostatok, ktorý sa nezmestí, je $b - a$. Zvyšnými vecami naplníme batoh $c$ a tie veci pridáme k $b - a$, čím dostaneme $b - a + c$ vecí. Tie potom skúsime dať do batohu $d$ a uvidíme, či sa zmestia, čím zistíme, ktorá z tých dvojíc je lepšia.
Ešte jeden malý detail: mohlo by sa stať, že toto nemôžeme spraviť, lebo máme dokopy menej ako $b - a + c$ vecí a teda nevieme odmerať také množstvo. Zo zadania ale vieme, že do batohu $d$ sa nezmestia všetky naše veci, teda určite platí, že $d < b + a - c$, keďže $d$ je menej ako máme vecí a $b + a - c$ je viac.
Takto vieme postupne porovnávať možné dvojice, až kým nám nezostane len tá najlepšia. Na jedno porovnanie potrebujeme len konštantný počet krokov, takže dokopy potrebujeme len rádovo $n$ krokov aj na túto časť, a tým pádom aj na celé riešenie.